IntermediateIn-depth4 min readUpdated 2 Oct 2026

How does a dictionary work internally in Python, and why must keys be hashable?

SHORT ANSWER

A dict is a hash table. Python calls hash() on the key to pick a slot, then uses == to confirm the match, which makes lookups O(1) on average. Keys must be hashable, meaning their hash never changes, otherwise the dict would look in the wrong slot and lose them. That is why lists cannot be keys but tuples of immutable values can.

Explain it simply

Think of a hostel with numbered lockers. Instead of searching every locker for Priya's bag, the warden uses a rule: take the roll number, do a quick calculation, and it gives a locker number. To find the bag later, the warden does the same calculation and goes straight there. No searching.

A Python dictionary does the same. The rule is the hash() function. It turns a key into a number, and that number decides where the value is stored. Looking it up later repeats the calculation, so it is fast no matter how many items the dict holds.

Now imagine the roll number could change after the bag was stored. The warden would calculate a different locker and never find the bag. That is why keys must be hashable: their hash must stay the same for as long as they are in the dict.

Example

python

fees = {"CSE": 150000, "ECE": 140000}
print(fees["CSE"])            # 150000, found in one step on average

print(hash("CSE") == hash("CSE"))    # True: same key, same hash

seat = {(3, "B"): "Rahul"}          # tuple of immutables: fine as a key
print(seat[(3, "B")])               # Rahul

bad = {}
bad[[3, "B"]] = "Rahul"             # TypeError: unhashable type: 'list'

d = {1: "one"}
d[True] = "true"
print(d)                            # {1: 'true'}  because 1 == True and hash(1) == hash(True)

How it works

Hash the key. hash(key) returns an integer.
Pick a slot. Python reduces that number to a position in an internal table.
Handle collisions. Two different keys can land on the same slot. CPython uses open addressing: if the slot is taken by a different key, it probes other slots in a fixed pattern until it finds the key or an empty slot.
Confirm with equality. A matching hash is not enough. Python also checks stored_key == key (it first checks identity, which is faster).
Resize. When the table gets too full, Python allocates a bigger one and reinserts everything. This is occasional, so inserts are still O(1) on average.

Since Python 3.7, dicts keep insertion order as a language guarantee. CPython does this by storing entries in a compact array in the order they were added, with a separate index table that holds the hash slots.

The hashable rule: an object is hashable if it has a __hash__ that never changes during its lifetime and an __eq__ to compare it. Also, objects that are equal must have equal hashes. Lists, dicts and sets are mutable, so Python sets their __hash__ to None. Ints, strings, frozensets and tuples whose items are all hashable can be keys.

Real-world use

Counting things: votes per candidate, orders per restaurant, words in a review.
Caches: storing a computed fare by (source, destination) so you do not recompute it.
Fast lookup tables: mapping a UPI ID to a user record, or a PIN code to a city.
Sets use the same hash table idea, which is why x in my_set is fast while x in my_list checks every item.

Common mistakes

Using a list as a key. Convert it to a tuple first.
Saying dict lookups are always O(1). They are O(1) on average; with many collisions the worst case is O(n).
Mutating an object after using it as a key in a custom class whose hash depends on that state. The dict can no longer find it.
Forgetting that 1, 1.0 and True are equal and hash the same, so they count as the same key.

What to say in the interview

"A Python dict is a hash table. When I insert a key, Python computes hash(key), maps it to a slot, and stores the key and value there, using probing if the slot is already taken. On lookup it repeats the hash, finds the slot and confirms with ==. That makes get, set and delete O(1) on average. Keys must be hashable, meaning the hash cannot change while the key is in the dict, otherwise Python would look in the wrong slot. That is why lists and dicts cannot be keys but strings, numbers and tuples of immutable values can. Since 3.7, dicts also preserve insertion order."

Follow-up questions

What is a hash collision and how does Python handle it?
How would you make objects of your own class usable as dict keys?
Why is x in set faster than x in list?
What is the worst-case time complexity of a dict lookup?

Go deeper

Read these once the basics above feel easy.

For your own classes, Python by default hashes by identity, so two separate objects with the same data are different keys. If you define __eq__, Python sets __hash__ to None unless you also define it, which makes the class unhashable. A clean fix is @dataclass(frozen=True), which generates matching __eq__ and __hash__ from the fields and blocks assignment to them.

String hashes are randomised per process (controlled by PYTHONHASHSEED). This protects web servers from attacks where someone sends many keys crafted to collide. It also means you should never rely on hash("abc") being the same across runs.

#python #dictionary #hashing #data-structures