Or the hash table implementation should be resistant to collisions, falling back to another data structure in that case (as described below, using trees instead of lists in buckets with sufficiently many occupants.)