How does python compute the hash of a tuple

Question

In python, if I have a tuple with many elements, is its hash calculated from its elements' ids or its elements' content?

In this example,

a = (1, [1,2])
hash(a)

It errors out saying list is unhashable. So I guess it's not computed by id, or probably there is a check on whether the element is mutable.

Now see this example

class A: pass
a0 = A()
ta = (1, a0)
hash(ta)  # -1122968024
a0.x = 20
hash(ta)  # -1122968024

Here it turns out the hash of ta does not change with the modification of its element, i.e., a0. So maybe a0's id is used for the hash calculation? Is a0 somehow considered as immutable? How does python know if a type is mutable?

Now consider this case

b = (1, 2)
id(b)  # 3980742764
c = (1, 2)
id(c)  # 3980732588
tb = (1, b)
tc = (1, c) 
hash(tb)  # -1383040070
hash(tc)  # -1383040070

It seems the content of b and c are used for the hash calculation.

How should I understand these examples?

Solution 1

If I have a tuple with many elements, is its hash calculated from its elements' ids or its elements' content?

Neither. It is calculated on the basis of the hashes of these elements, not their "contents" (values/attributes), nor IDs.

---

The basics: why hashes are used the way they are

Take a look at this paragraph in python's documentation glossary.

Whether something is hashable or not, and how it is hashed, depends on the implementation of its __hash__() method. By itself, Python has no idea about mutability of an object. It's the implementation that is expected to provide appropriate mechanisms and avoid pitfalls.

A hash is useful in identification of objects. For example, it speeds up data retrieval from a dict, identifying the arbitrary value of a key by a single numerical value from a finite interval - the key's hash.

A hash should remain unchanged throughout the lifetime of the object. Otherwise, one object could map to two different values in a dict, or be included into a set twice, as soon as its hash changes.

It's not enough to compare two objects by their hashes: at the end of the day, you may still need to perform equality checks, because there may be a collision between the hashes of two different objects. That's why hashable objects are required to have __eq__() implemented.

This ties back to the mutability: if a hashable object mutates such that it changes equality comparisons with hashables, especially the ones with the same hash - it breaks the contract, and may result in the same weirdness a mutating hash would. Hashable objects should not mutate comparisons between themselves.

Hashable objects that are equal to each other should have the same hash. This is a general contract that makes everything else simpler - it's natural to assume x == y implies that both x and y map to the same value in a dict.

---

Hash of a tuple

Consider your first example. The tuple hashes itself on the basis of its elements, while its second element, the list, doesn't have a hash at all - the __hash__ method is not implemented for it. And so the tuple.__hash__ method fails.

That's why a tuple with a list object inside of it is not hashable. As you can see, it is therefore also incorrect to say, that a tuple hash is based on the IDs of its elements.

Notice, that if the list was hashable here, and the hash was based on its elements, changing them would change the hash of the outer tuple, breaking the contract.

---

Why my custom class doesn't require a __hash__()?

Let's have a look at python data model documentation, and what it has to say on the topic:

User-defined classes have __eq__() and __hash__() methods by default; with them, all objects compare unequal (except with themselves) and x.__hash__() returns an appropriate value such that x == y implies both that x is y and hash(x) == hash(y).

Put simply, the default implementation compares objects identity, which has nothing to do with object attributes. That's why you can change the values "inside" the object of your custom class without changing its hash.

That's also why you don't have to define __hash__() for your classes - python does it for you in this case.

In this regard you're right - the default (CPython's) implementation of the hashing function for custom classes relies on the id() of an object (and not on the values "inside" of it). It is an implementation detail, and it differs between Python versions.

In more recent versions of Python, the relation between hash() and id() involves randomization. This prevents some forms of denial of service attacks, where creating arbitrary hash collisions could significantly slow down web applications. See PEP-456.

---

How does it actually hash itself?

While the details are quite complicated and probably involve some advanced math, the implementation of the hash function for tuple objects is written in C, and can be seen here (see static Py_hash_t tuplehash(PyTupleObject *v)).

The calculation involves XORing a constant with the hashes of each of the tuple's elements. The line responsible for hashing of the elements is this one:

y = PyObject_Hash(*p++);

---

So, to answer your original question: it does a bunch of XOR hokus-pocus with the hashes of each of its elements. Whether or not the contents and attributes of these elements are considered depends on their specific hash functions.

Solution 2

The core contract of hashing is that equal objects have equal hashes. In particular, hashing does not directly care about mutability or mutation; it only cares about mutation that affects equality comparisons.

---

Your first tuple is unhashable because mutating the nested list would change how the tuple behaves in equality comparisons.

Mutating a0 in your second example doesn't affect the hash of the tuple because it doesn't affect equality comparisons. a0 is still only equal to itself, and its hash is unchanged.

tb and tc in your third example have equal hashes because they are equal tuples, regardless of whether their elements are the same objects.

---

This all means that tuples cannot (directly) use id for hashes. If they did, equal tuples with distinct but equal elements could hash differently, violating the contract of hashing. Without special-casing element types, the only things tuples can use to compute their own hashes are their elements' hashes, so tuples base their hashes on their elements' hashes.

Solution 3

The answer to the question "Is the tuple's hash calculated based on the identity or the value?" is: Neither.

The correct answer is that the tuple's hash is calculated from the elements' hashes. How those hashes are calculated is (more or less) irrelevant.

An easy way to prove this is to see what happens when you put a list into a tuple:

>>> hash( (1, 2) )
3713081631934410656
>>> hash( (1, []) )
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

Because lists aren't hashable, a tuple containing a list isn't hashable either.

---

Let's take a closer look at this example you brought:

class A: pass
a0 = A()
ta = (1, a0)
hash(ta)  # -1122968024
a0.x = 20
hash(ta)  # -1122968024

Why doesn't setting a0.x = 20 affect the tuple's hash? Well, if we modify this code to output the hash of a0, you'll see that setting a0.x = 20 has no effect on a0's hash value:

a0 = A()
print(hash(a0))  # -9223363274645980307
a0.x = 20
print(hash(a0))  # -9223363274645980307

The reason for this is that python implements a default hash function for you. From the docs:

User-defined classes have __eq__() and __hash__() methods by default; with them, all objects compare unequal (except with themselves) and x.__hash__() returns an appropriate value such that x == y implies both that x is y and hash(x) == hash(y).

The default hash function ignores the object's attributes and calculates the hash based on the object's id. No matter what changes you make to a0, its hash will always stay the same. (Though it is possible to define a custom hash function for instances of your A class by implementing a custom __hash__ method.)

---

Addendum: The reason why lists aren't hashable is because they're mutable. From the docs:

If a class defines mutable objects and implements an __eq__() method, it should not implement __hash__(), since the implementation of hashable collections requires that a key’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket).

Lists fall into this category.

Solution 4

the hash of a tuple is based on the contents, not on the _id_s of the tuples. And the hashes are computed recursively: if one element isn't hashable (like a list element), then the tuple itself isn't hashable.

That's perfectly normal that if a and b are tuples and a == b, then hash(a) == hash(b) (if hashes can be computed of course), even if a is not b.

(on the contrary hash(a) == hash(b) doesn't mean that a == b)

The information conveyed by is is often not very useful, because of python object interning for example.

View more solutions

Comments

[Tushar Sadhwani]

short answer is that hash(tb) == hash(tc) because although id(a) and id(b) are not equal, hash(a) and hash(b) are the same.

[bartolo-otrit]

An interesting discussion about how this function evolved: Hash collisions for tuples. It was a simple x = (1000003 * x) ^ y, "but changed to the heart of the current scheme to address Source Forge bug #942952" (the problem was with hash( (X, (X, Y)) ) == hash(Y)), "So the complications were added for a reason, to address the showed-up-in-real-life pathological cases"