Python eq and hash: Custom Objects in Sets

This article explains how the __eq__ and __hash__ methods work together to allow custom Python classes to function correctly inside sets and as dictionary keys. Python sets rely on hash tables to achieve rapid lookups and enforce uniqueness. By understanding how __hash__ categorizes objects into memory buckets and how __eq__ resolves collisions and confirms value equivalence, you can design custom objects that behave predictably and safely in collection types.

How Python Sets Store Objects

Python sets are built on hash tables, a data structure that provides average \(O(1)\) time complexity for insertions, deletions, and membership tests. When you attempt to add an object to a set or check if it already exists using the in operator, Python does not sequentially scan every item. Instead, it follows a two-step verification process powered by __hash__ and __eq__:

1. Bucket Lookup (__hash__): Python calls the object's __hash__ method to generate an integer hash value. This value is converted into an array index (a "bucket") where the reference to the object should reside.
2. Equality Comparison (__eq__): If the target bucket is already occupied by another object, Python compares the incoming object to the existing one using the __eq__ method. If __eq__ returns True, the set recognizes the object as a duplicate and discards the incoming one. If it returns False, a hash collision has occurred, and the hash table handles it by searching for another slot.

The Hash Contract

To use custom objects in sets reliably, your implementation must adhere to a strict rule known as the Hash Contract:

• If two objects are considered equal according to __eq__, they must return the exact same integer from __hash__.
• If two objects have different hash values, they must never compare as equal.
• Objects that are not equal are permitted to share the same hash value (a hash collision), though minimizing collisions ensures optimal performance.

Violating this contract leads to subtle bugs. For example, if two objects are conceptually equal according to __eq__ but produce different hashes, they will be placed in different buckets. As a result, a set will fail to detect the duplicate and will store both objects simultaneously.

Default Behavior and Custom Overrides

By default, user-defined classes in Python inherit __eq__ and __hash__ from object:

• __eq__ compares instances by memory identity (is), meaning an instance is only equal to itself.
• __hash__ derives an integer directly from the object's memory address (id()).

When you override __eq__ to compare instances based on attributes rather than memory identity, Python automatically sets __hash__ = None. This safety mechanism prevents the class from being added to sets or used as dictionary keys until you explicitly define a matching __hash__ method.

class User:
    def __init__(self, user_id: int, name: str):
        self.user_id = user_id
        self.name = name

    def __eq__(self, other):
        if isinstance(other, User):
            return self.user_id == other.user_id
        return False

    def __hash__(self):
        return hash(self.user_id)

In this implementation, two distinct User instances with the same user_id will yield identical hashes and evaluate as equal, ensuring that only one instance per user_id can exist in a set.

Immutability and Hashing

Objects placed in sets must be hash-invariant throughout their lifetime. The fields used to calculate __hash__ and evaluated inside __eq__ should be immutable.

If an object’s attributes change after it has been added to a set, its hash value shifts. However, the set still retains the object in its original bucket based on the old hash. Consequently, searching for the object or attempting to remove it will fail, resulting in corrupted collection behavior. For this reason, custom hashable classes are typically designed as immutable structures, often using read-only properties or Python's @dataclass(frozen=True) decorator.