Not All Keys Fit: Python's Dictionary Limitations

Why Some Objects Can't Be Dictionary Keys and How to Work Around It

In coding problems, you might want to associate data with complex structures like lists or other dictionaries. While languages like Ruby or PHP allow almost any object to be a key, Python has specific requirements for dictionary keys.

Keys Must Be Immutable and Hashable

In Python, dictionary keys must be immutable and hashable. A hashable object has a hash value that doesn't change during its lifetime and can be compared to other objects. This ensures the key's hash value remains constant, allowing efficient data retrieval.

Common Immutable and Hashable Types:

Integers (int):

my_dict = {1: "one", 2: "two"}

Strings (str):

my_dict = {"name": "Alice", "age": 30}

Tuples (with immutable elements):

my_dict = {(1, 2): "coordinates"}

Frozen Sets (frozenset):

my_dict = {frozenset({1, 2, 3}): "a frozenset"}

User-Defined Classes (with proper __hash__() and __eq__() methods):

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

my_dict = {Point(1, 2): "A point"}

Mutable Types Cannot Be Dictionary Keys

Mutable objects are unhashable because their content can change, altering their hash value and compromising the dictionary's integrity.

Common Mutable and Unhashable Types:

Lists (list):

my_list = [1, 2, 3]
my_dict = {my_list: "list"} # Raises TypeError

Dictionaries (dict):

my_inner_dict = {"a": 1}
my_dict = {my_inner_dict: "dict"} # Raises TypeError

Sets (set):

my_set = {1, 2, 3}
my_dict = {my_set: "set"} # Raises TypeError

---

Understanding The Reason

Consistency Is Crucial

When you insert a key-value pair, Python computes the hash of the key to determine where to store the value. If the key's content changes after insertion, its hash value changes, and Python can't locate the key in the dictionary anymore.

Immutability Ensures Reliability

Immutability guarantees that the key remains the same throughout its lifetime, which is essential for maintaining data integrity and efficient retrieval.

Practical Tips for Coding Problems

• Use Immutable Types as Keys

  For composite keys, use tuples:

coordinates = (x, y)
my_dict[coordinates] = "value"

• Convert Mutable Objects to Immutable Equivalents

  Convert lists to tuples:

my_list = [1, 2, 3]
my_dict[tuple(my_list)] = "value"

• Ensure Custom Objects Are Hashable

  Implement __hash__() and __eq__() methods in your classes.

No Need to Memorize Specific Types

Focus on the principle:
If an object is immutable and hashable, it can be a dictionary key.

You can test if an object is hashable using the hash() function:

print(hash(42))          # Works
print(hash("hello"))     # Works
print(hash((1, 2, 3)))   # Works
print(hash([1, 2, 3]))   # Raises TypeError: unhashable type: 'list'

---

Conclusion

Understanding that dictionary keys must be immutable and hashable allows you to determine whether an object can serve as a key. This knowledge is essential when solving coding problems involving dictionaries or sets.

---

Stay curious and happy coding!
Nurbo

Need Help with Coding Interviews?

If you need one-on-one help with your tech interview preparation (coding, system design or behavioral) I can probably help you. Book a free introductory session with me here: https://link.faangshui.com/book.