Under the hood: internals and concurrency · about 45 min

How dicts and sets work: hashing

Why this matters

Dicts are everywhere in Python: your variables in a module live in one, every object's attributes usually live in one, and keyword arguments arrive as one. Looking up a key takes about the same time whether the dict has ten entries or ten million. Knowing why explains rules that otherwise look arbitrary: why keys must be hashable, why your class stops working in a set as soon as you define __eq__, why set order looks random and changes between runs, and why dicts remember insertion order.

The problem: finding things fast

Suppose you stored key/value pairs in a list and searched it from the start. Each lookup costs time proportional to the number of entries: O(n). A million entries, up to a million comparisons.

A hash table avoids searching. It keeps an array of slots and computes, from the key itself, which slot to look in:

key "apple" --hash()--> 8413925047155734512 --% 8--> slot 0
key "pear"  --hash()--> -3109427781106151934 --% 8--> slot 2

slot: 0        1     2       3     4     5     6     7
      apple:3  .     pear:5  .     .     .     .     .

A hash function turns a key into an integer. The same key must always produce the same integer (during one run), and different keys should produce well-scattered integers. Taking that number modulo the table size gives a slot. Lookup = compute the hash, jump to the slot, compare the key there. That is O(1) on average: the cost does not grow with the size of the dict.

Python exposes the hash function as the built-in hash():

>>> hash(42)
42
>>> hash("apple")        # differs between runs, see below
8413925047155734512
>>> hash((1, "a"))
-1554613577937546183
>>> hash([1, 2])
TypeError: unhashable type: 'list'

Collisions

Two different keys can land in the same slot: a collision. With billions of possible hashes and only a few slots, collisions are unavoidable. Hash tables differ in how they cope:

Separate chaining: each slot holds a small list of entries; you search that short list. This is what you will build in an exercise.
Open addressing: every slot holds at most one entry; on a collision, you probe other slots in a fixed sequence until you find the key or an empty slot.

CPython uses open addressing. Its probe sequence is not just "the next slot"; it mixes in more bits of the hash at each step (roughly i = (5*i + 1 + perturb) % size, with perturb shifted right each time), so keys that collide once quickly diverge. A lookup stops at the first empty slot: if the key were in the table, the probing during insertion would have put it there or earlier.

That is why deleting cannot simply empty a slot, which would break the probe chain for keys inserted later. CPython marks deleted slots with a "dummy" marker that lookups skip over.

To keep probe chains short, the table never gets too full. When a dict is about two thirds full, CPython allocates a bigger table (roughly doubling) and re-inserts every entry. That copy is O(n), but it happens rarely enough that inserting is O(1) amortized, the same argument as for list.append.

Worst case: if many keys have the same hash, every lookup walks the same long chain and degrades to O(n). For built-in types this practically never happens by accident, and the hash randomization described below makes it hard to cause on purpose.

The compact dict: why order is preserved

Since Python 3.6 (guaranteed since 3.7) a dict remembers insertion order. The trick is to split the table in two:

indices (sparse, small ints):   [ 1, -, 0, -, -, 2, -, - ]
entries (dense, in order):      0: (hash, "pear",  5)
                                1: (hash, "apple", 3)
                                2: (hash, "fig",   7)

The hashed slots hold only a small integer index into a dense entries array, which is appended to in insertion order. Lookup goes hash -> slot -> index -> entry. Iteration just walks the entries array, so it yields keys in insertion order. Bonus: the sparse part stores tiny integers instead of three pointers per slot, so dicts got 20-25% smaller.

Sets

A set is a hash table with keys and no values. Membership tests (x in s) are O(1) on average, which is why turning a list into a set before many lookups is a classic speed-up. But sets do not use the compact layout: they iterate in slot order, which depends on the hash values. So:

>>> {"pear", "apple", "fig"}
{'fig', 'pear', 'apple'}   # some order; may differ next run

Never write code (or tests) whose output depends on set order. Sort first: sorted(s).

Hash randomization

Why would the order differ between runs? Because hashes of str and bytes are salted with a random key chosen when the interpreter starts:

$ python3 -c 'print(hash("apple"))'
-2207431064553394375
$ python3 -c 'print(hash("apple"))'
5306829961862717154

This defends web services against hash flooding: an attacker who knows the hash function could send thousands of keys (say, form field names) that all collide, turning each dict operation into O(n) and the server's CPU into a space heater. With a secret per-process salt (CPython uses SipHash), they cannot predict collisions.

You can fix the salt with the environment variable PYTHONHASHSEED (for example PYTHONHASHSEED=0 disables randomization) when you need reproducible behavior for debugging. Integers are not salted: hash(n) is n for small integers (except hash(-1), which is -2, because -1 signals an error inside CPython's C code).

The contract: eq and hash

A dict finds a key by hash first, then confirms with ==. That only works if:

If a == b, then hash(a) == hash(b).

The reverse is not required (collisions are fine). Break the rule and an equal key can sit in a different slot, invisible to lookups.

Consequences:

>>> {1: "a", 1.0: "b"}
{1: 'b'}

1 == 1.0, so their hashes must be equal (they are), so they are the same key.

Your own classes. By default an object is equal only to itself, and its hash comes from its identity. That is consistent. When you define __eq__ to compare by value, Python sets __hash__ = None for you, because the inherited identity hash would now break the contract:

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y
    def __eq__(self, other):
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

{Point(1, 2)}

TypeError: unhashable type: 'Point'

Fix it by hashing the same fields that equality compares, usually by hashing a tuple of them:

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

This is exactly what @dataclass(frozen=True) generates for you.

Mutability. If an object's hash depends on fields that can change, changing them after insertion strands the entry:

p = Point(1, 2)
s = {p}
p.x = 99
print(p in s)        # False: looks in the slot for hash((99, 2))
print(len(s))        # 1: the entry is still there, unreachable by lookup

That is why built-in mutable containers are unhashable, and why value-hashed classes should be immutable (frozen dataclasses, or simply never mutated).

Common mistakes

TypeError: unhashable type: 'list' when using a list as a key or set member. Use a tuple: d[tuple(coords)] = ....
TypeError: unhashable type: 'dict' when building a set of dicts. Use a tuple of sorted items, or a frozen dataclass, or rethink the structure.
Defining __eq__ without __hash__, then wondering why the class fails in sets.
Writing a __hash__ that uses fields __eq__ ignores: then equal objects can have different hashes. Hash a subset of the compared fields, never a superset.
Depending on set order in output or tests. It is a property of the hash values and table size, not of anything you control.

Recap

A hash table maps a key's hash to a slot; lookup is O(1) on average, O(n) in the pathological all-collide case.
CPython dicts use open addressing with perturbed probing, resize at about 2/3 full, and use a compact layout (sparse indices + dense entries) that preserves insertion order.
Sets are hash tables without values; their iteration order follows hashes, so never rely on it.
str/bytes hashes are randomized per process (SipHash, PYTHONHASHSEED) to resist hash flooding.
Equal objects must have equal hashes; defining __eq__ sets __hash__ = None unless you define it. Hash only immutable data.

Going further: read Raymond Hettinger's talk "Modern Python Dictionaries: A confluence of a dozen great ideas", and the comments at the top of Objects/dictobject.c in the CPython source, which explain the probing scheme in detail.

Exercises

Exercise 1 · quiz

Why lists cannot be keys

{[1, 2]: "x"} raises TypeError: unhashable type: 'list'. What is the real reason Python refuses?

Lists are too large to hash quickly
A list can change after insertion; its hash would change, and the dict would look for it in the wrong slot
Lists contain other objects, and dict keys may not contain objects
Only strings and numbers can ever be dict keys

Answer

A list can change after insertion; its hash would change, and the dict would look for it in the wrong slot

A dict stores each key in a slot chosen from its hash. If the key could change, its hash would change too, and a later lookup would probe a different slot and never find it, even though the entry is still in the table. So mutable built-ins (list, dict, set) set __hash__ to None. Tuples are hashable, but only if everything inside them is: (1, [2]) is not.

Exercise 2 · quiz

Equal keys collapse

What does this print? Type the exact output.

d = {1: "int", 1.0: "float", True: "bool"}
print(d)

Answer

1 == 1.0 == True, and Python guarantees that equal objects have equal hashes, so all three are the same key. The first insertion stores the key object 1; the later two find that slot, see an equal key, and only replace the value. The key stays 1 (the original key object is kept), the value ends up 'bool'.

Exercise 3 · write code

Make a class usable as a key

solution.py defines a Point class with x and y. Two points with the same coordinates should be equal and work as the same dict key / set member.

Add __eq__ and __hash__ so that:

Point(1, 2) == Point(1, 2) is True, Point(1, 2) == Point(2, 1) is False
comparing with a non-Point returns NotImplemented from __eq__ (so Point(1, 2) == (1, 2) is False)
len({Point(1, 2), Point(1, 2), Point(3, 4)}) == 2
{Point(0, 0): "origin"}[Point(0, 0)] == "origin"

Base the hash on the same data as equality: hash((self.x, self.y)).

File: solution.py

Starting point

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

    def __eq__(self, other):
        if not isinstance(other, Point):
            return NotImplemented
        return (self.x, self.y) == (other.x, other.y)

Hint 1

Run the starter: {Point(1, 2)} fails with unhashable type: 'Point'. Defining __eq__ alone sets __hash__ to None.

Hint 2

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

Reference solution

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

    def __eq__(self, other):
        if not isinstance(other, Point):
            return NotImplemented
        return (self.x, self.y) == (other.x, other.y)

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

Exercise 4 · write code

Build a hash table

Implement a small hash table with separate chaining (each slot holds a list of (key, value) pairs) in class HashMap:

HashMap(size=8) creates size empty buckets in self.buckets (a list of lists).
put(key, value): find the bucket hash(key) % len(self.buckets); if an equal key is already there, replace its value; otherwise append (key, value).
get(key, default=None): return the value for key, or default if absent.
__len__: the number of keys stored.
__contains__(key): True if the key is present.

Do not use a dict or set anywhere in the class. You do not need to resize.

File: solution.py

Starting point

class HashMap:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        pass

    def get(self, key, default=None):
        pass

    def __len__(self):
        return 0

    def __contains__(self, key):
        return False

Hint 1

All three operations start with bucket = self._bucket(key); equal keys always land in the same bucket.

Hint 2

In put, loop with enumerate(bucket) so you can replace bucket[i] = (key, value) when k == key.

Hint 3

__len__ is the sum of the bucket lengths.

Reference solution

class HashMap:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def __len__(self):
        return sum(len(b) for b in self.buckets)

    def __contains__(self, key):
        return any(k == key for k, _ in self._bucket(key))