Why can a Python dict have multiple keys with the same hash?
dictionary, equality, hash, python, set
Solution
For a detailed description of how Python's hashing works see my answer to Why is early return slower than else?
Basically it uses the hash to pick a slot in the table. If there is a value in the slot and the hash matches, it compares the items to see if they are equal.
If the hash matches but the items aren't equal, then it tries another slot. There's a formula to pick this (which I describe in the referenced answer), and it gradually pulls in unused parts of the hash value; but once it has used them all up, it will eventually work its way through all slots in the hash table. That guarantees eventually we either find a matching item or an empty slot. When the search finds an empty slot, it inserts the value or gives up (depending whether we are adding or getting a value).
The important thing to note is that there are no lists or buckets: there is just a hash table with a particular number of slots, and each hash is used to generate a sequence of candidate slots.
Problem
I am trying to understand the Python `hash` function under the hood. I created a custom class where all instances return the same hash value. ``` class C: def __hash__(self): return 42 ``` I just assumed that only one instance of the above class can be in a `dict` at any time, but in fact a `dict` can have multiple elements with the same hash. ``` c, d = C(), C() x = {c: 'c', d: 'd'} print(x) # {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'} # note that the dict has 2 elements ``` I experimented a little more and found that if I override the `__eq__` method such that all the instances of the class compare equal, then the `dict` only allows one instance. ``` class D: def __hash__(self): return 42 def __eq__(self, other): return True p, q = D(), D() y = {p: 'p', q: 'q'} print(y) # {<__main__.D object at 0x7f0823a9af40>: 'q'} # note that the dict only has 1 element ``` So I am curious to know how a `dict` can have multiple elements with the same hash.