[python] What does "hashable" mean in Python?

I tried searching internet but could not find the meaning of hashable.

When they say objects are hashable or hashable objects what does it mean?

Anything that is not mutable (mutable means, likely to change) can be hashed. Besides the hash function to look for, if a class has it, by eg. dir(tuple) and looking for the __hash__ method, here are some examples

#x = hash(set([1,2])) #set unhashable
x = hash(frozenset([1,2])) #hashable
#x = hash(([1,2], [2,3])) #tuple of mutable objects, unhashable
x = hash((1,2,3)) #tuple of immutable objects, hashable
#x = hash()
#x = hash({1,2}) #list of mutable objects, unhashable
#x = hash([1,2,3]) #list of immutable objects, unhashable

List of immutable types:

int, float, decimal, complex, bool, string, tuple, range, frozenset, bytes

List of mutable types:

list, dict, set, bytearray, user-defined classes

Let me give you a working example to understand the hashable objects in python. I am taking 2 Tuples for this example.Each value in a tuple has a unique Hash Value which never changes during its lifetime. So based on this has value, the comparison between two tuples is done. We can get the hash value of a tuple element using the Id().

For creating a hashing table from scratch, all the values has to set to "None" and modified once a requirement arises. Hashable objects refers to the modifiable datatypes(Dictionary,lists etc). Sets on the other hand cannot be reinitialized once assigned, so sets are non hashable. Whereas, The variant of set() -- frozenset() -- is hashable.

All the answers here have good working explanation of hashable objects in python, but I believe one needs to understand the term Hashing first.

Hashing is a concept in computer science which is used to create high performance, pseudo random access data structures where large amount of data is to be stored and accessed quickly.

For example, if you have 10,000 phone numbers, and you want to store them in an array (which is a sequential data structure that stores data in contiguous memory locations, and provides random access), but you might not have the required amount of contiguous memory locations.

So, you can instead use an array of size 100, and use a hash function to map a set of values to same indices, and these values can be stored in a linked list. This provides a performance similar to an array.

Now, a hash function can be as simple as dividing the number with the size of the array and taking the remainder as the index.

For more detail refer to https://en.wikipedia.org/wiki/Hash_function

Here is another good reference: http://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html

In python it means that the object can be members of sets in order to return a index. That is, they have unique identity/ id.

for example, in python 3.3:

the data structure Lists are not hashable but the data structure Tuples are hashable.

In my understanding according to Python glossary, when you create a instance of objects that are hashable, an unchangeable value is also calculated according to the members or values of the instance. For example, that value could then be used as a key in a dict as below:

>>> tuple_a = (1,2,3)
>>> tuple_a.__hash__()
2528502973977326415
>>> tuple_b = (2,3,4)
>>> tuple_b.__hash__()
3789705017596477050
>>> tuple_c = (1,2,3)
>>> tuple_c.__hash__()
2528502973977326415
>>> id(a) == id(c)  # a and c same object?
False
>>> a.__hash__() == c.__hash__()  # a and c same value?
True
>>> dict_a = {}
>>> dict_a[tuple_a] = 'hiahia'
>>> dict_a[tuple_c]
'hiahia'

we can find that the hash value of tuple_a and tuple_c are the same since they have the same members. When we use tuple_a as the key in dict_a, we can find that the value for dict_a[tuple_c] is the same, which means that, when they are used as the key in a dict, they return the same value because the hash values are the same. For those objects that are not hashable, the method hash is defined as None:

>>> type(dict.__hash__) 
<class 'NoneType'>

I guess this hash value is calculated upon the initialization of the instance, not in a dynamic way, that's why only immutable objects are hashable. Hope this helps.

Hashable = capable of being hashed.

Ok, what is hashing? A hashing function is a function which takes an object, say a string such as “Python,” and returns a fixed-size code. For simplicity, assume the return value is an integer.

When I run hash(‘Python’) in Python 3, I get 5952713340227947791 as the result. Different versions of Python are free to change the underlying hash function, so you will likely get a different value. The important thing is that no matter now many times I run hash(‘Python’), I’ll always get the same result with the same version of Python.

But hash(‘Java’) returns 1753925553814008565. So if the object I am hashing changes, so does the result. On the other hand, if the object I am hashing does not change, then the result stays the same.

Why does this matter?

Well, Python dictionaries, for example, require the keys to be immutable. That is, keys must be objects which do not change. Strings are immutable in Python, as are the other basic types (int, float, bool). Tuples and frozensets are also immutable. Lists, on the other hand, are not immutable (i.e., they are mutable) because you can change them. Similarly, dicts are mutable.

So when we say something is hashable, we mean it is immutable. If I try to pass a mutable type to the hash() function, it will fail:

>>> hash('Python')
1687380313081734297
>>> hash('Java')
1753925553814008565
>>>
>>> hash([1, 2])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> hash({1, 2})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'
>>> hash({1 : 2})
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>>
>>> hash(frozenset({1, 2}))
-1834016341293975159
>>> hash((1, 2))
3713081631934410656

In Python, any immutable object (such as an integer, boolean, string, tuple) is hashable, meaning its value does not change during its lifetime. This allows Python to create a unique hash value to identify it, which can be used by dictionaries to track unique keys and sets to track unique values.

This is why Python requires us to use immutable datatypes for the keys in a dictionary.