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?

Answer 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.

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 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.

Answer 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.