How does a Python dictionary achieve average O(1) lookup time internally?
Dict lookup: hash table with open addressing and compact storage
A dict is a hash table. On lookup, CPython computes hash(key), masks it to an index into a sparse indices array, and compares the key in the corresponding entry. If the slot is empty, lookup fails; if occupied, it compares hashes and then equality. Collisions are resolved with open addressing and a perturb-based probe sequence, not separate chaining. Modern CPython also uses a compact layout: a dense entries array stores keys and values in insertion order, and a sparse indices array maps hash slots to entry positions. This improves memory locality and preserves insertion order.
- 1
Average O(1) assumes a good hash function, low collision rate, and bounded load factor; CPython resizes when the table becomes too full.
- 2
Worst-case lookup is O(n) if many keys collide or if an attacker can force collisions.
- 3
Trade-off: custom objects need consistent hash and eq. If two objects are equal they must have the same hash; otherwise dict/set lookups break.
- 4
Common mistake: assuming dict lookup is always O(1) or that mutable keys are allowed. Keys must be hashable, and mutating a key after insertion corrupts lookup.
- 5
Version note: the compact dict layout landed in CPython 3.6 and insertion order became a language guarantee in 3.7. Hash randomization is enabled by default in modern Python for security.
Scenario Questions
0-2 years experience
- 1You have a list of user IDs and need fast membership checks. What structure and why?
- 2Why does using a list as a dict key fail?
2-5 years experience
- 1A custom object used as a dict key sometimes cannot be found even though equal objects are created. What do you check?
- 2You see many hash collisions in a service. How do you diagnose and mitigate?
5-8 years experience
- 1You are building an in-memory index for millions of records with high-cardinality string keys. How do you reason about load factor and resizing?
- 2Would you use dict or a database index for O(1) lookups? Discuss memory and persistence.
8+ years experience
- 1Design a custom hashable key type for a multi-tenant cache that avoids collisions across tenants and supports zero-downtime key rotation.
- 2You need deterministic iteration and O(1) lookup under adversarial input. How do you defend against hash-flooding?
Follow-up Questions
- What happens if you mutate an object after using it as a dict key?
- How does Python protect against hash-flooding attacks?