Understanding Python's Hash Table: How Dictionaries Achieve O(1) Lookups

Python's built‑in dict is a mapping container that stores key‑to‑value pairs. It is implemented with a hash table, giving average‑case O(1) time for insertion, deletion and lookup.

Creating a dict can be done with literal syntax, the dict() constructor, or by merging existing mappings. Code examples illustrate each method and show that keyword arguments must be valid identifiers.

A simple benchmark compares searching for a value in a list versus in a dict. As the number of look‑ups grows from 1 000 to 500 000, list look‑up time increases from 0.13 s to over 25 s, while dict look‑up remains near 0 s, demonstrating the constant‑time property.

The article explains the underlying hash‑table mechanism: a key is hashed, the hash value is reduced modulo the table capacity to obtain an index, and the key‑value pair is stored at that slot.

The image illustrates the mapping of keys to array indices.

Hash collisions are handled by probing: if the computed slot is occupied, Python re‑hashes or moves to the next free slot until an empty position is found. Updating an existing key simply overwrites the stored value.

Python resizes the table when the number of entries reaches two‑thirds of its capacity, allocating a larger array and re‑hashing existing keys to maintain low collision probability.

In summary, a hash table trades space for time: by using an array indexed by hashed keys, Python dictionaries achieve fast look‑ups independent of the total number of entries.