Hashing behavior in Python set

Question

I was trying to understand how sets function internally in Python.

I wrote a subclass of tuple as follows:

from random import random
class ball(tuple):
    def __hash__(self):
        a=super().__hash__()%4
        print("hash({0})={1}".format(str(self),a))
        return a
    def __eq__(self,other):
        a=random()>0.5
        print("eq({0},{1})=={2}".format(str(self),str(other),a))
        return a
    def __lt__(self,other):
        print("Called lt({0},{1})".format(str(self),self(other)))
        return super().__hash__(self,other)

Then I execute the following code

f=[ball([i]) for i in range(5)]
set(f)

The output is

hash((0,))=3

hash((1,))=2

hash((2,))=1

hash((3,))=0

hash((4,))=3

eq((0,),(4,))==False

eq((0,),(4,))==True

{(3,), (2,), (1,), (0,)}

Why does Python check for equality twice in the last situation? This happens quite often.

Update: The output is from Python 3.3. This behavior does not seem to be reproducible in 3.4 onwards.

Answer 1

The behaviour you see is due to the usage of open addressing in the set implementations prior to Python 3.4 (which uses a combination of open addressing and linear probing, which seems to have "solved" this problem).

First of all in your code both (0,) and (4,) have the same hash (3). When building the set the implementation has to check whether an element with the same hash exists or not, and whether it is equal (so that it avoids adding the same element more than once). This check is perfomed calling the set_lookkey function which is the internal function used by all other code to find elements of a set.

In particular (code a bit simplified to avoid irrelevant details):

i = (size_t)hash & mask;
entry = &table[i];

if (entry->hash == hash) {
    startkey = entry->key;
    Py_INCREF(startkey);
    cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
    Py_DECREF(startkey);
    if (cmp < 0)
        return NULL;
    if (table == so->table && entry->key == startkey) {
        if (cmp > 0)
            return entry;
    }
}

here you can see that the set uses the hash to obtain an index inside the inner table. Then it retrieves the entry at that index and checks for equality (PyObject_RichCompareBool). If the result (cmp) is < 0 then an error occurred and it returns NULL. If cmp == 0 then it means that the entry was not equal, when cmp > 0 (i.e. a true value) then we have found the entry which is immediately returned.

In our case hash = i = 3 and mask == PySet_MINSIZE - 1 == 7¹, so we are taking entry = &table[3].

Note that when cmp == 0 the execution continues after that block. In this case the set tries to check whether there was a collision and thus it checks every entry that is associated with that hash. The other entries are found by doing:

for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
        i = (i << 2) + i + perturb + 1;
        entry = &table[i & mask];

If we try to compute i again we get:

(3 << 2) + 3 + 3 + 1 == 19

And:

19 & 7 == 3

In other words we are checking the same entry again. This explains why __eq__ is called twice.

All this doesn't happen with Python 3.4+ because the checks are performed in a different way, which avoids re-checking the same entry.

---

Note that all this is an implementation detail. The set is free to call __eq__ however many times it wants, so don't rely on the number of calls to __eq__.

Also your __eq__ method breaks the invariants required from hashable objects: x == y ==> hash(x) == hash(y) but in your case this is not always true (see the glossary for hashable). In other words the instances of your class cannot be safely used with a set in a sane way.

---

¹ This is true because sets have a minimum size that can store more than 4 elements. PySet_MINSIZE is defined in Include/setobject.h in the sources. When creating a new set the INIT_NONZERO_SET_SLOTS macro is called which sets the mask to PySet_MINSIZE - 1. That macro is called by make_new_set which is used when building a set from an iterable.