Hashability

Hashability is the property of an object that allows it to be used as a key in a hash table or to be stored in a set. An object is hashable if it has a hash value that does not change during its lifetime and can be compared for equality. Hashing enables fast lookup, insertion, and deletion by mapping keys to buckets using a hash function. The hash function produces an integer from the object's value; due to finite buckets, different objects may share a hash value (collisions).

In many languages, including Python and Java, hashability is tied to immutability and the equality relation. In Python, an object is hashable if it implements __hash__ and __eq__ and remains immutable; mutable types such as lists and dicts are unhashable. Tuples are hashable if all their elements are hashable. Strings, integers, and frozensets are hashable. User-defined classes can be hashable by defining a __hash__ method consistent with __eq__.

General contract: if a == b, then hash(a) == hash(b). Hash values need not be unique; equal hash values for non-equal objects are acceptable but degrade performance. A well-designed hash function distributes values evenly to minimize collisions. Hashability is essential for data structures like dictionaries and sets, and is also relevant to memoization and caching strategies.

Beyond Python, many languages require immutability or properly defined equals and hashCode methods to ensure correct behavior of hash-based collections. In purely functional contexts, hash-consing and persistent hash maps exploit hashability to share structure efficiently.