What's a correct and good way to implement __hash__()? [closed]

John Millikin proposed a solution similar to this:

class A(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        return (isinstance(othr, type(self))
                and (self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))

    def __hash__(self):
        return hash((self._a, self._b, self._c))

The problem with this solution is that the hash(A(a, b, c)) == hash((a, b, c)). In other words, the hash collides with that of the tuple of its key members. Maybe this does not matter very often in practice?

Update: the Python docs now recommend to use a tuple as in the example above. Note that the documentation states

The only required property is that objects which compare equal have the same hash value

Note that the opposite is not true. Objects which do not compare equal may have the same hash value. Such a hash collision will not cause one object to replace another when used as a dict key or set element as long as the objects do not also compare equal.

Outdated/bad solution

The Python documentation on __hash__ suggests to combine the hashes of the sub-components using something like XOR, which gives us this:

class B(object):

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __eq__(self, othr):
        if isinstance(othr, type(self)):
            return ((self._a, self._b, self._c) ==
                    (othr._a, othr._b, othr._c))
        return NotImplemented

    def __hash__(self):
        return (hash(self._a) ^ hash(self._b) ^ hash(self._c) ^
                hash((self._a, self._b, self._c)))

Update: as Blckknght points out, changing the order of a, b, and c could cause problems. I added an additional ^ hash((self._a, self._b, self._c)) to capture the order of the values being hashed. This final ^ hash(...) can be removed if the values being combined cannot be rearranged (for example, if they have different types and therefore the value of _a will never be assigned to _b or _c, etc.).

Paul Larson of Microsoft Research studied a wide variety of hash functions. He told me that

for c in some_string:
    hash = 101 * hash  +  ord(c)

worked surprisingly well for a wide variety of strings. I've found that similar polynomial techniques work well for computing a hash of disparate subfields.

A good way to implement hash (as well as list, dict, tuple) is to make the object have a predictable order of items by making it iterable using __iter__. So to modify an example from above:

class A:

    def __init__(self, a, b, c):
        self._a = a
        self._b = b
        self._c = c

    def __iter__(self):
        yield "a", self._a
        yield "b", self._b
        yield "c", self._c

    def __hash__(self):
        return hash(tuple(self))

    def __eq__(self, other):
        return (isinstance(other, type(self))
                and tuple(self) == tuple(other))

(here __eq__ is not required for hash, but it's easy to implement).

Now add some mutable members to see how it works:

obj = A(2, 2.2, "cat")
hash(obj)  # 977171927842460677
dict(obj)  # {'a': 2, 'b': 2.2, 'c': 'cat'}
list(obj)  # [('a', 2), ('b', 2.2), ('c', 'cat')]
tuple(obj) # (('a', 2), ('b', 2.2), ('c', 'cat'))
assert obj == A(2, 2.2, "cat")
assert obj != A(2, 2.2, "cats")

things only fall apart if you try to put non-hashable members in the object model:

hash(A(2, 2.2, [1]))  # TypeError: unhashable type: 'list'

I can try to answer the second part of your question.

The collisions will probably result not from the hash code itself, but from mapping the hash code to an index in a collection. So for example your hash function could return random values from 1 to 10000, but if your hash table only has 32 entries you'll get collisions on insertion.

In addition, I would think that collisions would be resolved by the collection internally, and there are many methods to resolve collisions. The simplest (and worst) is, given an entry to insert at index i, add 1 to i until you find an empty spot and insert there. Retrieval then works the same way. This results in inefficient retrievals for some entries, as you could have an entry that requires traversing the entire collection to find!

Other collision resolution methods reduce the retrieval time by moving entries in the hash table when an item is inserted to spread things out. This increases the insertion time but assumes you read more than you insert. There are also methods that try and branch different colliding entries out so that entries to cluster in one particular spot.

Also, if you need to resize the collection you will need to rehash everything or use a dynamic hashing method.

In short, depending on what you're using the hash code for you may have to implement your own collision resolution method. If you're not storing them in a collection, you can probably get away with a hash function that just generates hash codes in a very large range. If so, you can make sure your container is bigger than it needs to be (the bigger the better of course) depending on your memory concerns.

Here are some links if you're interested more:

coalesced hashing on wikipedia

Wikipedia also has a summary of various collision resolution methods:

Also, "File Organization And Processing" by Tharp covers alot of collision resolution methods extensively. IMO it's a great reference for hashing algorithms.

A very good explanation on when and how implement the __hash__ function is on programiz website:

Just a screenshot to provide an overview: (Retrieved 2019-12-13)

As for a personal implementation of the method, the above mentioned site provides an example that matches the answer of millerdev.

class Person:
def __init__(self, age, name):
    self.age = age
    self.name = name

def __eq__(self, other):
    return self.age == other.age and self.name == other.name

def __hash__(self):
    print('The hash is:')
    return hash((self.age, self.name))

person = Person(23, 'Adam')
print(hash(person))

@dataclass(frozen=True) (Python 3.7)

This awesome new feature automatically defines a __hash__ and __eq__ method for you, making it just work as usually expected in dicts and sets without any need for tedious repetition:

dataclass_cheat.py

from dataclasses import dataclass, FrozenInstanceError

@dataclass(frozen=True)
class MyClass1:
    n: int
    s: str

@dataclass(frozen=True)
class MyClass2:
    n: int
    my_class_1: MyClass1

d = {}
d[MyClass1(n=1, s='a')] = 1
d[MyClass1(n=2, s='a')] = 2
d[MyClass1(n=2, s='b')] = 3
d[MyClass2(n=1, my_class_1=MyClass1(n=1, s='a'))] = 4
d[MyClass2(n=2, my_class_1=MyClass1(n=1, s='a'))] = 5
d[MyClass2(n=2, my_class_1=MyClass1(n=2, s='a'))] = 6

assert d[MyClass1(n=1, s='a')] == 1
assert d[MyClass1(n=2, s='a')] == 2
assert d[MyClass1(n=2, s='b')] == 3
assert d[MyClass2(n=1, my_class_1=MyClass1(n=1, s='a'))] == 4
assert d[MyClass2(n=2, my_class_1=MyClass1(n=1, s='a'))] == 5
assert d[MyClass2(n=2, my_class_1=MyClass1(n=2, s='a'))] == 6

# Due to `frozen=True` we can't modify objects.
o = MyClass1(n=1, s='a')
try:
    o.n = 2
except FrozenInstanceError as e:
    pass
else:
    raise 'error'

As we can see in this example, the hashes are being calculated based on the contents of the objects, and not simply on the addresses of instances. This is why something like:

d = {}
d[MyClass1(n=1, s='a')] = 1
assert d[MyClass1(n=1, s='a')] == 1

works even though the second MyClass1(n=1, s='a') is a completely different instance from the first with a different address.

frozen=True is mandatory, otherwise the class is not hashable, otherwise it would make it possible for users to inadvertently make containers inconsistent by modifying objects after they are used as keys. Further documentation: https://docs.python.org/3/library/dataclasses.html

@dataclass also provides other good things like __str__, it's awesome.

Tested on Python 3.10.7, Ubuntu 22.10.

Depends on the size of the hash value you return. It's simple logic that if you need to return a 32bit int based on the hash of four 32bit ints, you're gonna get collisions.

I would favor bit operations. Like, the following C pseudo code:

int a;
int b;
int c;
int d;
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F);

Such a system could work for floats too, if you simply took them as their bit value rather than actually representing a floating-point value, maybe better.

For strings, I've got little/no idea.

I will contend that because of the definition of __hash__ as it is known today you necessarily cannot have an implementation that is both "correct" -and- "good" at the same time. So instead, let's settle on "good" (since the accepted answer instead aims to be "correct"):

class Thing:
    def __hash__(self):
        return id(self)

    def __eq__(self, other):
        # it is advised to implement __eq__ when you implement __hash__
        # however this __eq__ impl has nothing to do with this being a 
        # "good" implementation of __hash__, it merely ensures correctness
        # of behavior for use in container types. you could obviously write
        # something more tailored to your class than this, this is merely
        # inheritance-friendly.
        if not isinstance(other, type(self)):            
            return False
        for aname in (set(dir(self)) | set (dir(other))):
            if aname.startswith('__'):
                continue
            if (not hasattr(self, aname)) or (not hasattr(other, aname)):
                return False
            atype = type(self.attr)
            if atype is types.MethodType or atype is types.FunctionType:
                continue
            if getattr(self, aname) != getattr(other, aname):
                return False
        return True

For this implementation __hash__ yields a value that is unique over the entire process for the lifetime of the object. For objects stored to a list or set (where reachability prevents object destruction) this is acceptable.

When used as a key for a dict, if the object is no longer reachable and is destroyed this key "may" collide. We must also consider that __hash__ results from other objects "may" collide as well due to differences in implementations. For these reasons implementations of containers typically check for object equality (both in Python and in other languages, as the notion of object hashes for container identity is not a uniquely Python concept.)

There are ways of defeating the problem of collision without depending on __eq__ but that is best reserved for another Q&A, and really deserves the consideration of container devs not the developers using their containers.

In any case, this implementation has the value of efficiency and simplicity, and does not suffer from collisions resulted from relying on the __hash__ of "correct" implementations such as that of Tuple. It is ideal that object identity is firstly resolved by __hash__ result comparison avoiding an additional dispatch for a __eq__ result.

To demonstrate this implementation, consider the following subclass and-also a unittest class for verification:

class SubThing(Thing):
    def __init__(self, val1, val2):
        if val1 != None:
            self.val1 = val1
        if val2 != None:
            self.val2 = val2

import unittest
class ThingTests(unittest.TestCase):
    def test_Things(self):
        t1 = Thing()
        t2 = Thing()
        self.assertEqual(t1, t2)
        set1 = set()
        set1.add(t1)
        set1.add(t2)
        set1.add(t1)
        set1.add(t2)
        self.assertEqual(2, len(set1))
        t3 = SubThing(1,2)
        t4 = SubThing(1,2)
        t5 = SubThing(2,3)
        t6 = SubThing(None,None)
        t7 = SubThing(None,5)
        t8 = SubThing(5,None)
        set2 = set()
        set2.add(t3)
        set2.add(t4)
        set2.add(t5)
        set2.add(t6)
        set2.add(t7)
        set2.add(t8)
        self.assertEqual(6, len(set2))
        self.assertEqual(t1, t2)
        self.assertEqual(t3, t4)
        self.assertNotEqual(t1, t3)
        self.assertNotEqual(t3, t4)
        self.assertNotEqual(t4, t5)
        self.assertNotEqual(t5, t6)
        self.assertNotEqual(t6, t7)
        self.assertNotEqual(t7, t8)

Test passes.

Conclusion

This implementation is "good" but it is not "correct", why?

Because the current Python spec defines __hash__ with the constraint that two objects which would return true in an equality test must also return the same hash value. Bad. This will likely plague Python until the end of time. That doesn't mean you need to write naive code. The above will comply with all but the worst container implementations (those which foolishly rely on object equality instead of object hashes), and if there is a container implementation that misbehaves because of the above __hash__ then that impl it deserves to be called out and fixed.