Hashable, immutable
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.
What the difference between hash-able and immutable?
Immutable means that the object, the top-level container for the item, cannot be changed. Note that this applies only to the top level; it may contain references to sub-objects that are mutable.
Hashable has a functional definition: Python's built-in
hash
function returns a value. This generally means that the object's closure (following all references to their leaf-node values) consists of immutable objects.Your premise is incorrect: a tuple can contain mutable items. Any such reference renders the tuple un-hashable.
For instance:
>>> b = [7]
>>> a = (b, 5)
>>> a
([7], 5)
>>> type(a)
<class 'tuple'>
>>> set(a)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> b[0] = 'b'
>>> a
(['b'], 5)
b
is a mutable list. The reference to b
can be held in the tuple a
. We can change the value of b[0]
(not it's object handle), and the display value of a
changes. However, we cannot make a set including a
, because the mutability of b
renders a
unhashable.
Continuing the example:
>>> b = False
>>> a
(['b'], 5)
>>> b = [14]
>>> a
(['b'], 5)
a
is immutable. Thus, when we change b
, only b
gets the reference to the new object. a
retains the original object handle, still pointing to ['b']
.
What does hashable mean in Python?
From the Python glossary:
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.Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.
All of Python’s immutable built-in objects are hashable, while no mutable containers (such as lists or dictionaries) are. Objects which are instances of user-defined classes are hashable by default; they all compare unequal, and their hash value is their
id()
.
Immutable objects are not hashable in python?
Tuples are very much hashable if the elements inside are hashable.
>>> hashable = (1,2,4)
>>> not_hashable = ([1,2],[3,4])
>>> hash_check = {}
>>> hash_check[hashable] = True
>>> hash_check
{(1, 2, 4): True}
>>> hash_check[not_hashable] = True
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>
Immutable hashable list with correct typings
The immutable equivalent to List[T]
is Tuple[T, ...]
.
From the Python documentation:
To specify a variable-length tuple of homogeneous type, use literal ellipsis, e.g.
Tuple[int, ...]
. A plainTuple
is equivalent toTuple[Any, ...]
, and in turn totuple
.
Python: why can I put mutable object in a dict or set?
Python doesn't test for mutable objects, it tests for hashable objects.
Custom class instances are by default hashable. That's fine because the default __eq__
implementation for such classes only tests for instance identity and the hash is based of the same information.
In other words, it doesn't matter that you alter the state of your instance attributes, because the identity of an instance is immutable anyway.
As soon as you implement a __hash__
and __eq__
method that take instance state into account you might be in trouble and should stop mutating that state. Only then would a custom class instance no longer be suitable for storing in a dictionary or set.
Is there any hashable built-in object is mutable in python?
>>> from collections.abc import Hashable
>>> mutable = [list, bytearray, set, dict]
>>> immutable = [int, float, complex, str, tuple, frozenset, bytes]
>>> all(isinstance(x(), Hashable) for x in immutable)
True
>>> any(isinstance(x(), Hashable) for x in mutable)
False
all mutable objects are unhashable.
Related Topics
Can't Get Argparse to Read Quoted String with Dashes in It
Converting String to Int Using Try/Except in Python
Selecting Multiple Slices from a Numpy Array at Once
First Non-Null Value Per Row from a List of Pandas Columns
Matching Nested Structures with Regular Expressions in Python
Python Replace Single Backslash with Double Backslash
Launch a Completely Independent Process
Append to a List Defined in a Tuple - Is It a Bug
Restart Cumsum and Get Index If Cumsum More Than Value
Python: Source Code String Cannot Contain Null Bytes
Grouping/Clustering Numbers in Python
How to Run Python Scripts Using Gimpfu from Command Line
Python Out of Memory on Large CSV File (Numpy)