Python Dictionary Underlying Data Structure

Python dictionaries are implemented using an optimized, dynamic hash table. While conceptually a standard hash map that maps hashable keys to values using a hashing algorithm, modern Python (introduced in CPython 3.6 and standardized in Python 3.7) utilizes a compact, array-based layout. This architecture significantly reduces memory overhead, provides \(O(1)\) average-time complexity for lookups, insertions, and deletions, and inherently preserves the insertion order of elements.

The Compact Hash Table Layout

In classic implementations, a Python dictionary relied on a single sparse table where each entry contained the key hash, key pointer, and value pointer. Because the table had to remain mostly empty to avoid collisions, substantial memory was wasted on empty slots.

Modern CPython separates the storage into two distinct arrays:

1. Indices Array (Sparse): A sparse array containing integer indices. The size of this array is always a power of two (e.g., 8, 16, 32). The hashed key determines the index into this array.
2. Entries Array (Dense): A compact array of PyDictKeyEntry structures that grows sequentially. Each entry contains:
   • me_hash: The cached 64-bit hash of the key.
   • me_key: A pointer to the key object.
   • me_value: A pointer to the value object.

When a new key-value pair is inserted, it is appended to the next available position in the dense entries array. The sparse indices array is then updated to store the index of that newly added entry.

Lookup and Collision Resolution

Python handles hash collisions using an open addressing strategy with a custom pseudo-random probing mechanism, rather than separate chaining (linked lists).

The lookup process operates as follows:

1. Hashing: Python computes the key's hash using hash(key).
2. Indexing: The hash is masked against the size of the sparse indices array (hash & (size - 1)) to determine the starting bucket.
3. Collision Probing: If the bucket contains an index, Python inspects the corresponding entry in the dense table:
   • If both the hash and identity/equality (key is entry_key or key == entry_key) match, the value is returned.
   • If the bucket is occupied by a different key, a collision has occurred. Python computes the next index using the recurrence relation: perturb >>= 5; j = (5 * j + 1 + perturb) & mask
   • This recurrence guarantees that all slots in the table are eventually visited while pseudo-randomly distributing the probe sequence to prevent clustering.
4. Empty Slot: If the bucket contains an empty marker, the key does not exist in the dictionary.

Dynamic Resizing and Memory Management

To maintain average \(O(1)\) performance, the dictionary must prevent the hash table from becoming too crowded:

• Load Factor: The table resizes when it becomes roughly two-thirds full (a load factor of approximately 66%).
• Growth Strategy: When resizing occurs, the size of the indices array typically doubles (or quadruples for smaller dictionaries). A new sparse indices array is allocated, and the indices are recomputed.
• Deletions: When an item is deleted, the entry cannot simply be removed because doing so would break the probe sequence for colliding keys. Instead, the slot in the indices array is replaced with a dummy (tombstone) value. When the dictionary eventually resizes, dummy entries are purged and the dense array is compacted.