How do Set and Dictionary store keys with the same hash?

The point of Hashable is to quickly calculate keys so the container can store its elements in a numeric graph. So what happens when distinct elements share a hash value? Are they just stored in a randomly-ordered list?

If the Element is also Comparable, are the hash-sharing elements also stored in escalating order? If not, can we add that? This could provide a speed up via binary search.

You can see the implementation here. In particular,

Native storage is a hash table with open addressing and linear probing. The bucket array forms a logical ring (e.g., a chain can wrap around the end of buckets array to the beginning of it).

Though you obviously shouldn't rely on any implementation detail that isn't documented. If your hash function is so poor that a binary search of the list of collisions is an improvement, then I would suggest that you have bigger problems somewhere.

Terms of Service

Privacy Policy

Cookie Policy