Hashable, immutable

Question

From a recent SO question (see Create a dictionary in python which is indexed by lists) I realized I probably had a wrong conception of the meaning of hashable and immutable objects in python.

• What does hashable mean in practice?
• What is the relation between hashable and immmutable?
• Are there mutable objects that are hashable or immutable objects that are not hashable?

Answer 1

Immutable means that object will not change in any significant manner during its lifetime. It's a vague but common idea in programming languages.

Hashability is slightly different, and refers to comparison.

hashable An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() or __cmp__() method). Hashable objects which compare equal must have the same hash value.

All user-defined classes have __hash__ method, which by default just returns the object ID. So an object that meets the criteria for hashability is not necessarily immutable.

Objects of any new class you declare can be used as a dictionary key, unless you prevent it by, for example, throwing from __hash__

We could say that all immutable objects are hashable, because if the hash changes during the object's lifetime, then it means that the object mutated.

But not quite. Consider a tuple which has a list (mutable). Some say tuple is immutable, but at the same time it is somewhat not hashable (throws).

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

Hashability and immutability refer to object instancess, not type. For example, an object of type tuple can be hashable or not.

Answer 2

Hashable means that an variable's value can be represented (or, rather, encoded) by a constant -- string, number, etc. Now, something that is subject to change (mutable) cannot be represented by something that is not. Therefore, any variable that is mutable cannot be hashable and, by the same token, only immutable variables can be hashable.

Hope this helps ...

Answer 3

There is an implicit even if there is no explicit relationship forced between immutable and hashable due the interplay between

1. Hashable objects which compare equal must have the same hash value
2. An object is hashable if it has a hash value which never changes during its lifetime.

There is no problem here unless you redefine __eq__ so the the objects class defines equivalence on value.

Once you've done that you need to find a stable hash function which always returns the same value for objects which represent the same value (eg, where __eq__) returns True, and never changes during the lifetime of an object.

It hard to see an application where this is possible, consider a possible class A which meets these requirements. Although there is the obvious degenerate case where __hash__ returns a constant.

Now:-

>>> a = A(1)
>>> b = A(1)
>>> c = A(2)
>>> a == b
True
>>> a == c
False
>>> hash(a) == hash(b)
True
>>> a.set_value(c)
>>> a == c
True
>>> assert(hash(a) == hash(c)) # Because a == c => hash(a) == hash(c)
>>> assert(hash(a) == hash(b)) # Because hash(a) and hash(b) have compared equal 
                                 before and the result must stay static over the objects lifetime.

In fact this means at creation hash(b) == hash(c), despite the fact there are never compared equal. I struggle to see anyway to usefully define __hash__() for a mutable object which defines compare by value.

Note: __lt__, __le__ , __gt__ and __ge__ comparsions aren't affected so you can still define an ordering of hashable objects, mutable or otherwise based on their value.