In Python, the term \u201chashable\u201d refers to any object with a hash value that never changes during its lifetime. This hash value allows hashable objects to be used as dictionary keys or as members of sets, providing fast lookup and comparison operations.<\/p>\n\n\n\n
But what exactly does it mean for an object to be hashable, and why does it matter? Let\u2019s break it down step-by-step.<\/p>\n\n\n\n
\nA hashable object is one with a consistent hash value throughout its lifetime, enabling its use as dictionary keys or set members. Hashable objects include immutable types like integers, strings, tuples, while lists, dictionaries, and sets are non-hashable due to their mutability. Understanding hashability is crucial for efficient data storage and retrieval in Python, as it ensures fast and reliable access in data structures like hash tables.<\/em><\/p>\n<\/blockquote>\n\n\n\n
Exploring Python’s Hash Functions<\/h2>\n\n\n\n
A hash function<\/strong> is a function that takes input data of arbitrary size, and converts it into a fixed size value. This value is called the hash value or hash. A good hash function has some key properties:<\/p>\n\n\n\n
\n
- It generates very different hash values for similar input values – even a small change in the input results in a large change in the hash. This is called the avalanche effect<\/strong>.<\/li>\n\n\n\n
- It uniformly distributes hashes across the possible output range for the hash function.<\/li>\n\n\n\n
- It is deterministic – the same input value will always generate the same hash value.<\/li>\n<\/ul>\n\n\n\n
Python has a built-in
hash()<\/code> function that can generate hash values:<\/p>\n\n\n\n>>> hash("Python") \n7282735233108043601\n\n<\/pre><\/div>\n\n\nThe actual algorithm used by
hash()<\/code> can vary between Python versions, but the properties stay the same.<\/p>\n\n\n\nWhy Hashing is Useful<\/h2>\n\n\n\n
Generating hash values allows us to compare dictionary keys or set members quickly.<\/p>\n\n\n\n
For example, let\u2019s say we wanted to check if two lists contain the same elements. Without hashing, we would need to iterate through both lists and check each element, which takes linear time O(n).<\/p>\n\n\n\n
But if the lists contain hashable items like strings or tuples, we can simply hash each list and compare the hashes in constant O(1) time:<\/p>\n\n\n
\ndef list_equals(list1, list2):\n return hash(tuple(list1)) == hash(tuple(list2))\n\n<\/pre><\/div>\n\n\nBy using the hash, we no longer care if the lists are ordered differently. All we care about is whether they hash to the same value.<\/p>\n\n\n\n
This speedup via hashing applies to dictionaries and sets as well. Python actually stores set items and dictionary keys in a hash table internally to enable fast lookups.<\/p>\n\n\n\n
Hashable Objects in Python<\/h2>\n\n\n\n
For an object to be hashable, two key requirements must be met:<\/p>\n\n\n\n
1. It must have a\u00a0hash\u00a0method that returns an integer.<\/h3>\n\n\n\n
All Python objects inherit a
__hash__<\/code> method, but for mutable objects like lists and dicts,__hash__<\/code> returns a TypeError indicating that the object is unhashable.<\/p>\n\n\n\nFor immutable built-in objects like integers, strings and tuples,
__hash__<\/code> returns a unique integer derived from the object\u2019s value:<\/p>\n\n\n\n>>> hash("hello")\n1859319527393798429\n\n>>> hash( ("apple", "banana")) \n8424618783216606276\n<\/pre><\/div>\n\n\nCustom classes are hashable by default if you don\u2019t override
__hash__<\/code>, but best practice is to implement it explicitly if defining custom equality behavior with__eq__<\/code>.<\/p>\n\n\n\n2. Its hash value cannot change while it is in use by a dict or set.<\/h3>\n\n\n\n
That\u2019s why only immutable objects can be hashable – they guarantee their hash value will not change over their lifetime. A tuple object will always hash to the same value. But if a list was hashable, appending items would change its content while still expecting lookups based on the old hash value.<\/p>\n\n\n\n
An object is hashable if:<\/p>\n\n\n\n
\n
- It supports hash() via a hash<\/strong>() method<\/li>\n\n\n\n
- Its hash value is immutable and stays constant over the lifetime of the object<\/li>\n<\/ul>\n\n\n\n
The Challenge of Hashing Mutable Objects<\/h2>\n\n\n\n
If we try to get the hash value of a mutable object like a list, set, or dict<\/a>, we get a TypeError:<\/p>\n\n\n
\n>>> hash([1,2,3])\nTraceback (most recent call last):\n File "<stdin>", line 1, in <module>\nTypeError: unhashable type: 'list'\n\n>>> hash({1: "one"})\nTraceback (most recent call last):\n File "<stdin>", line 1, in <module>\nTypeError: unhashable type: 'dict' \n\n<\/pre><\/div>\n\n\nWe can even put a mutable list inside an immutable tuple, and it still won\u2019t be hashable because the internal list could be modified:<\/p>\n\n\n
\n>>> hash((1, [2,3]))\nTraceback (most recent call last):\n File "<stdin>", line 1, in <module>\nTypeError: unhashable type: 'list'\n\n<\/pre><\/div>\n\n\nThese mutable collections<\/a> can\u2019t be hashed directly:<\/p>\n\n\n\n