How Python Dictionaries Work Internally
Python does this by hashing the key and using the resulting number to identify a storage location.
Try it: How a dict Stores Keys
How a dictionary turns a key into a slot with a hash, what happens on a collision, why deleted keys leave a marker, and why the table grows.
How it works
- hash(key) gives a number; hash % table size gives the key's home slot.
- If that slot is taken by another key (a collision), probe the next slot.
- Deleting leaves a DELETED marker so lookups keep probing past it.
- When more than 2/3 of the slots are used, the table doubles and every key is re-inserted.
Default run (5 steps): A dict with 3 keys in 8 slots. Choose an operation. Example: d["mango"] = 5. … Done. 4 keys in 8 slots.
Simplified: Uses a small educational hash (Python's real string hash is randomised per run) and simple linear probing; CPython's probe order is more elaborate.
Loading the simulation…
A Lookup That Depends on Stability
A dictionary must be able to find a value from its key without searching through every entry. Python does this by hashing the key and using the resulting number to identify a storage location. This approach only works if the key produces the same hash value whenever Python hashes it.
Following the Hashing Process
When a key is placed in a dictionary, Python hashes that key and stores the associated value in a location based on the hash. Later, when you look up the key, Python hashes the key again and uses the result to locate the value. The first hash and the later hash must agree. If the key's contents have changed, its hash could change as well. Python would then look in a different location and fail to find the stored value.
Mutability Determines Key Eligibility
Hashability is the property that allows an object to be used as a dictionary key. A hashable object must produce the same hash value every time it is hashed.
Tuples are hashable because they are immutable: once a tuple is created, its contents cannot change. Because its contents are fixed, its hash value remains fixed. Lists are mutable: their contents can change after creation. Python therefore does not allow lists to be used as dictionary keys, because a changed list could produce a different hash and make its stored value impossible to locate reliably.
Building Composite Keys
A composite key combines multiple values into one dictionary key. This is useful when one value alone does not uniquely identify an entry. For example, a student ID might not be unique across different classes, so both the class ID and the student ID are needed.
Identifying a Student Across Classes
Create one dictionary key from a class ID and a student ID.
- 1Identify the required values
The class ID and student ID are both needed to identify the entry uniquely.
- 2Combine the values
Place the class ID and student ID together in a tuple, creating one composite key.
- 3Use the tuple as the key
The tuple can serve as the dictionary key because tuples are hashable and their contents cannot change after creation.
Use a tuple containing the class ID and student ID rather than a list containing those values.
When several values together identify one dictionary entry, combine them in a tuple for the key. Do not use a list for the combined values, because lists are mutable and unhashable.
Diagnosing Unhashable-Key Errors
Common mistake Trying to use a list as a dictionary key
What it looks likeUsing a list of multiple identifying values as the key instead of a tuple.
Why it failsA list is mutable, so its contents could change and its hash value would not be stable. Python prevents lists from being used as dictionary keys.
Do this insteadReplace the list with a tuple when the combined values should form one composite key.
Common mistake Treating hashability as a one-time property
What it looks likeAssuming that an object is suitable as a key merely because Python can hash it at one moment.
Why it failsA dictionary needs the key to produce the same hash value every time it is hashed, not just during insertion.
Do this insteadUse a key whose contents remain unchanged for the lifetime of the dictionary entry.
Common mistake Using only one identifier when several are needed
What it looks likeUsing a student ID alone when the same student ID can occur in different classes.
Why it failsOne value may not uniquely identify the dictionary entry.
Do this insteadCombine the class ID and student ID into a tuple and use that tuple as the composite key.
Check Your Reasoning
A dictionary must distinguish entries using both a region identifier and a device identifier. Should the combined key be represented by a tuple or a list? Explain your choice using mutability, hashability, and lookup reliability.
Hints
- Ask whether the combined object can change after it is created.
- A dictionary key must produce the same hash value whenever it is hashed.
- Choose the collection type that is hashable.
What do you think happens?
What should happen when a list is supplied as a dictionary key?
Reveal answer
Python rejects it because the list is unhashable.
Lists are mutable, so their contents could change and their hash value would not remain stable. Python prevents this kind of key from being used.
Key Takeaways
- Hashability means that an object can produce the same hash value every time it is hashed.
- Python uses a key's hash to identify a storage location for the associated dictionary value.
- Tuples are immutable and hashable, while lists are mutable and unhashable.
- A mutable key could change its hash after insertion, causing later lookup to search in the wrong location.
- Use a tuple as a composite key when multiple values together identify one dictionary entry.