Python Dict Hash Collision Resolution Explained

Python dictionaries rely on open addressing combined with a unique pseudo-random probing mechanism to resolve hash collisions during lookups. Rather than using separate chaining with linked lists, Python resolves conflicts by searching through alternative slots directly within its internal hash table. This design, paired with a compact array architecture introduced in Python 3.6, allows dictionaries to maintain high memory efficiency, preserve insertion order, and achieve amortized \(O(1)\) time complexity for key lookups.

Open Addressing and Probing

When a key-value pair is inserted into or fetched from a dictionary, Python computes the key's hash value using the built-in hash() function. This hash is masked against the size of the table to derive an initial index.

If that slot is already occupied by a different key—a hash collision—Python uses open addressing to locate the next available slot. Instead of basic linear probing (checking index \(+ 1\)) or quadratic probing, Python employs a custom recurrence relation that incorporates higher-order bits from the original hash:

perturb >>= 5
j = (5 * j + 1 + perturb) & mask

In this formula:

• j represents the current slot index.
• mask equals table_size - 1.
• perturb is initialized to the original hash value and is bit-shifted to the right by 5 bits on each iteration.

This algorithm prevents clustering (where consecutive slots become crowded) and ensures that all 64 bits of the hash code contribute to the probe sequence. Eventually, perturb shifts to zero, turning the sequence into a linear congruential generator that is mathematically guaranteed to visit every index in the table.

Two-Tier Compact Table Structure

Since Python 3.6 (standardized in Python 3.7), dictionaries use a two-array design:

1. Indices Array (Sparse): A hash table containing only small integer indices or markers representing empty slots.
2. Entries Array (Dense): An array that stores entries in the exact order they were inserted, with each record containing [hash, key, value].

When a collision occurs, probing takes place on the indices array. The probing sequence searches the indices array until it encounters an empty slot or a slot pointing to an entry in the dense table matching the search key.

Key Comparison: Identity Before Equality

When probing encounters an occupied slot, Python verifies whether the stored key matches the target key. It performs a two-step validation:

1. Identity Check (key1 is key2): Python compares memory addresses. If both keys refer to the same object in memory, the lookup succeeds immediately without evaluating equality.
2. Hash and Equality Check (hash1 == hash2 and key1 == key2): If the identity check fails, Python verifies that the stored hash matches the target hash, followed by evaluating the rich comparison __eq__ method.

If neither check succeeds, probing continues down the sequence.

Handling Deletions with Tombstones

When a key is deleted from a dictionary, removing it completely would break the probe chain for other keys that collided at that same initial index. Python handles this by marking the vacated slot in the indices array with a special dummy value (often referred to as a "tombstone"). During lookups, the probing algorithm treats dummy slots as occupied and continues traversing the probe sequence. When inserting a new key, Python can reuse these dummy slots, and during table resizes, dummy entries are discarded entirely to clean up the table.