Dictionary Creation and Manipulation
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.
The Key Must Stay Stable
A dictionary associates keys with values. To find a value quickly, Python uses a hash function to convert the key into a number that points to a storage location. This lookup method depends on the key remaining stable: the key must produce the same hash value every time it is hashed.
What do you think happens?
Which object is suitable as a dictionary key: a tuple containing two values, or a list containing the same two values?
Reveal answer
The tuple
A tuple is immutable, so its contents cannot change after creation. Lists are mutable, so their contents can change. Python therefore makes tuples hashable and lists unhashable for dictionary-key use.
From Key to Stored Value
Hashability is the property that allows an object to be used as a dictionary key. When Python stores a value, it hashes the key and uses the resulting number to select a storage location. When Python later looks up that key, it hashes the key again. The process works only if the key produces the same hash value both times.
Tuples Versus Lists
| Object | Can its contents change? | Hashable for dictionary-key use? | Reason |
|---|---|---|---|
| Tuple | No | Yes | Its contents are fixed after creation. |
| List | Yes | No | Its contents can change, so its hash could change. |
The key distinction is immutability: fixed contents support a stable hash, while mutable contents do not.
Tuples can be dictionary keys because they are immutable: once created, their contents cannot change. Their fixed contents support a fixed hash value. Lists cannot be dictionary keys because they are mutable. If a list's contents changed, the hash associated with those contents could change as well.
Choosing a key for a class record
A record must be identified by both a class identifier and a student identifier. Should the combined key be represented by a tuple or a list?
- 1Identify the key parts
The class identifier and student identifier are two related values that must be combined into one dictionary key.
- 2Check mutability
A list can have its contents changed, while a tuple has fixed contents after creation.
- 3Choose the hashable container
Use a tuple because dictionary keys must be hashable and the tuple's contents remain fixed.
Use a tuple containing the class identifier and student identifier as the composite dictionary key.
Composite Keys for Combined Identity
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 may identify a student within one class but not across several classes. Combining the class ID and student ID creates a key that represents both parts of the identity.
When several values together identify one dictionary entry, represent the composite key with a tuple rather than a list. The tuple preserves the relationship between the values while satisfying the dictionary's need for a hashable key.
Tracing an Unhashable-Key Failure
Common mistake Trying to use a list as a dictionary key.
What it looks likeUsing a list of a class identifier and a student identifier as the key.
Why it failsLists are mutable and therefore are not hashable.
Do this insteadUse a tuple containing the same values as the composite key.
Common mistake Treating hashability as unrelated to mutability.
What it looks likeAssuming any container can serve as a key because it contains the needed values.
Why it failsA dictionary needs a key whose hash remains stable, and mutable contents can change that hash.
Do this insteadCheck whether the proposed key is immutable and hashable before using it.
Common mistake Expecting a mutable key to remain findable after its contents change.
What it looks likeImagining that a dictionary could safely keep locating a key after the key's internal contents changed.
Why it failsThe changed key could hash to a different location, so the dictionary could lose track of the stored value.
Do this insteadUse an immutable key whose contents remain fixed for the lifetime of the dictionary.
Python prevents lists from being used as dictionary keys rather than allowing a dangerous lookup situation. If a mutable key were stored and then changed, Python could hash it differently during a later lookup. The dictionary would search at a different location and fail to find the value associated with the original contents.
Practice and Diagnosis
A dictionary must distinguish records using both a department identifier and an employee identifier. Decide whether the composite key should be a tuple or a list. Then explain what property makes your choice suitable and predict what kind of problem occurs if the other container is used as the key.
Hints
- Ask whether the container's contents can change.
- Connect fixed contents with a stable hash value.
- An unsuitable key fails because dictionary keys must be hashable.
Diagnosing the container choice
A learner chooses a list to combine a department identifier and an employee identifier for use as a dictionary key. What should be diagnosed?
- 1Inspect the proposed key
The proposed key is a list, and lists are mutable.
- 2Apply the key rule
Dictionary keys must be hashable and must produce the same hash value every time they are hashed.
- 3Locate the problem
The list is unhashable, so the dictionary cannot use it as a key.
- 4Repair the design
Replace the list with a tuple containing the department and employee identifiers.
The tuple is the appropriate composite key because its contents are immutable and its hash remains stable.
Reliable Dictionary Keys
- 1Hashability is the property that allows an object to be used as a dictionary key.
- 2A hashable key must produce the same hash value every time it is hashed so that dictionary lookup can locate the associated value.
- 3Tuples are hashable because they are immutable; lists are unhashable because they are mutable.
- 4Use a tuple as a composite key when multiple values together identify one dictionary entry.
- 5When an unhashable object is proposed as a key, diagnose the problem by checking mutability and replace it with an appropriate immutable key.
Key Takeaways
- Dictionary lookup uses hashing to connect a key with a storage location and its associated value.
- Keys must be hashable, which means they produce the same hash value every time they are hashed.
- Tuples can be keys because their contents cannot change, while lists cannot be keys because their contents can change.
- Tuples are the correct choice for composite keys that combine multiple values into one dictionary identity.
- An unhashable-key failure is diagnosed by checking whether the proposed key is mutable.