How Python Sets Guarantee Unique Elements

Python sets are built-in collections designed to hold distinct, unordered items, making them an ideal tool for eliminating duplicates and performing fast membership lookups. This article explores the internal mechanisms that Python uses to enforce uniqueness, focusing on hash table architecture, hash value computation, and object equality checks.

The Underlying Hash Table Architecture

Under the hood, Python sets are implemented as hash tables, very similar to Python dictionaries but containing only keys without associated values. A hash table maps keys to specific memory locations (known as buckets or slots) based on numerical values derived from the keys themselves.

When you insert an item into a set, Python does not compare the new item to every existing item individually. Instead, it determines where the item should live in memory using hashing algorithms, achieving an average time complexity of \(O(1)\) for additions and lookups.

The Role of the Hash Function

For an object to be stored in a set, it must be hashable. An object is hashable if it has a hash value that remains constant throughout its lifecycle and can be compared to other objects. In Python, immutable types such as strings, numbers, and tuples of immutable objects are hashable by default.

When an element is passed to a set:

  1. Python calls the object's __hash__() method to compute an integer hash value.
  2. The hash value is masked to produce an index pointing to a specific bucket within the set's underlying table.

If the target bucket is empty, Python immediately inserts the element, confirming that no duplicate exists in that position.

Resolving Collisions and Verifying Equality

Because different objects can occasionally produce the same hash value or map to the same bucket index (a phenomenon known as a hash collision), Python cannot rely solely on the hash to guarantee uniqueness.

To determine whether an item is truly a duplicate, Python uses a two-step validation:

  1. Hash Comparison: It first checks if the stored object has the same hash value as the incoming object. If the hashes differ, the objects are fundamentally different.
  2. Equality Comparison: If the hashes match, Python falls back to checking equality using the __eq__() method (evaluating existing_item == new_item).

If both the hash and the equality check evaluate to true, Python considers the incoming element a duplicate. The set will simply ignore the new addition or overwrite the existing reference, leaving the total count unchanged.

If the hash or equality check fails despite occupying the same bucket index, Python detects a collision. It uses an open addressing scheme with a pseudo-random probing sequence to search for the next available slot in the table, repeating the verification process until it finds either a matching duplicate or an empty bucket to place the new element.

Requirements for Custom Objects

When creating custom classes, you can control how instances behave inside a set by overriding __hash__() and __eq__(). To maintain the uniqueness guarantee, custom implementations must satisfy the Python hashing contract: