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
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. |
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?
Identify the key parts: The class identifier and student identifier are two related values that must be combined into one dictionary key.
Check mutability: A list can have its contents changed, while a tuple has fixed contents after creation.
Choose 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
Trying to use a list as a dictionary key.
Lists are mutable and therefore are not hashable.
Fix:
Use a tuple containing the same values as the composite key.Treating hashability as unrelated to mutability.
A dictionary needs a key whose hash remains stable, and mutable contents can change that hash.
Fix:
Check whether the proposed key is immutable and hashable before using it.Expecting a mutable key to remain findable after its contents change.
The changed key could hash to a different location, so the dictionary could lose track of the stored value.
Fix:
Use 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?
Inspect the proposed key: The proposed key is a list, and lists are mutable.
Apply the key rule: Dictionary keys must be hashable and must produce the same hash value every time they are hashed.
Locate the problem: The list is unhashable, so the dictionary cannot use it as a key.
Repair 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
- Hashability is the property that allows an object to be used as a dictionary key.
- A hashable key must produce the same hash value every time it is hashed so that dictionary lookup can locate the associated value.
- Tuples are hashable because they are immutable; lists are unhashable because they are mutable.
- Use a tuple as a composite key when multiple values together identify one dictionary entry.
- When 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.