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

Hashing is the process of converting some large amount of data into a much smaller amount (typically a single integer) in a repeatable way so that it can be looked up in a table in constant-time (O(1)), which is important for high-performance algorithms and data structures.

Immutability is the idea that an object will not change in some important way after it has been created, especially in any way that might change the hash value of that object.

The two ideas are related because objects which are used as hash keys must typically be immutable so their hash value doesn't change. If it was allowed to change then the location of that object in a data structure such as a hashtable would change and then the whole purpose of hashing for efficiency is defeated.

To really grasp the idea you should try to implement your own hashtable in a language like C/C++, or read the Java implementation of the HashMap class.

Answer 2

• Are there mutable objects that are hashable or immutable objects that are not hashable?

In Python, tuple is immutable, but it is hashable only if all its elements are hashable.

>>> tt = (1, 2, (30, 40)) >>> hash(tt) 8027212646858338501 >>> tl = (1, 2, [30, 40]) >>> hash(tl) TypeError: unhashable type: 'list' 

Hashable Types

• The atomic immutable types are all hashable, such as str, bytes, numeric types
• A frozen set is always hashable(its elements must be hashable by definition)
• A tuple is hashable only if all its elements are hashable
• User-defined types are hashable by default because their hash value is their id()