8 — Hash maps and hash sets

A hash table stores keys (and, for a map, their values) so that insert, lookup and delete take O(1) time on average, whatever the number of keys. It does this by turning each key into an integer with a hash function and using that integer to pick a slot in an array. When two keys land in the same slot, a collision resolution scheme decides where the second one goes. Everything else in this chapter (load factors, probing sequences, tombstones, resizing) is detail about keeping those collisions rare and cheap.

Hash tables are the most used data structure after the array. Python’s dict holds every module’s globals, every object’s attributes and every keyword argument, and set turns “have I seen this?” into a constant-time question. Most of the problem patterns at the end of the chapter are a quadratic brute force rescued by a single dictionary.

Timings in this chapter were measured with Python 3.14 on one Mac. Exact numbers will differ on other machines; the ratios and growth patterns are what matter.

The idea

Take an array of m slots. To store a key, compute h(key), an integer, and reduce it to a slot index, usually h(key) mod m or, when m is a power of two, h(key) & (m - 1). To find the key later, compute the same index and look there.

m = 8 slots, h(k) = k

key 3   -> slot 3
key 12  -> slot 4
key 21  -> slot 5
key 11  -> slot 3   collision with 3

slot: 0    1    2    3    4    5    6    7
     [ ]  [ ]  [ ]  [3]  [12] [21] [ ]  [ ]

If every key landed in its own slot, every operation would be one array access. Collisions are unavoidable in general, though. With m slots and n keys there are $\binom{n}{2}$ pairs, each colliding with probability $1/m$ under a random hash, so collisions are expected once n reaches about $\sqrt{m}$. With 365 slots that is the birthday paradox: 23 keys give a better than even chance of a collision. A hash table therefore needs both a hash function that spreads keys evenly and a plan for the collisions that still happen.

The load factor is $\alpha = n/m$, the number of stored keys per slot. Every cost in a hash table is a function of α, not of n. That is the source of the O(1) claim: as long as the table grows to keep α below a fixed bound, the expected cost of an operation stays bounded by a constant.

What O(1) means here

Hash table O(1) is an expected bound under an assumption about the hash function: that it behaves like a random function on the keys being stored. It is not a worst-case bound. If every key hashes to the same slot, every operation is O(n) and building the table is O(n²). The worst case is real and can be triggered on purpose, as the section on hash flooding shows. Insertion is also O(1) amortized, not worst case, because an insert that triggers a resize rehashes everything.

Hash functions

A hash function for a table needs three properties:

1. Deterministic and consistent with equality. Equal keys must have equal hashes, every time, for the life of the table. In Python: if a == b then hash(a) == hash(b). Unequal keys may share a hash.
2. Uniform. Keys that actually occur should spread evenly over the hash values, so that each slot gets about n/m keys.
3. Fast. It runs on every operation. A table that spends more time hashing than probing has the wrong function.

Cryptographic properties (preimage resistance, collision resistance against a determined attacker) are not required for an ordinary table, and cryptographic hashes like SHA-256 are too slow for one. A related property sits in between: resistance to deliberately constructed collisions, which matters when keys come from untrusted input.

Avalanche

A good general-purpose hash has the avalanche property: flipping one input bit flips each output bit with probability about one half, so about half of the output bits change. Without it, similar keys produce similar hashes, and similar hashes land in the same or neighboring slots. Measured over 10,000 random single-bit changes:

hash(int)          mean output bits changed by a 1-bit input change: 1.00 of 64
hash(str)          mean output bits changed by a 1-bit input change: 31.97 of 64
blake2b, 64 bits   mean output bits changed by a 1-bit input change: 31.98 of 64

Python’s string hash avalanches perfectly. Python’s integer hash does not avalanche at all: flipping one bit of the input flips exactly one bit of the output. That is deliberate, as the next section explains.

Python’s hashes for numbers

>>> [hash(i) for i in range(5)]
[0, 1, 2, 3, 4]
>>> hash(-1), hash(-2)
(-2, -2)
>>> hash(2**61 - 1), hash(2**61)
(0, 1)
>>> hash(1.0), hash(True)
(1, 1)
>>> hash(1.5), hash(0.5)
(1152921504606846977, 1152921504606846976)

On 64-bit builds, the hash of an integer is its value modulo the Mersenne prime $P = 2^{61} - 1$ (sys.hash_info.modulus), with the sign kept. Floats, Fraction and Decimal use the same modular scheme on their exact rational value, so equal numbers of different types hash equally: 1, 1.0, True and Fraction(1) are the same dictionary key. hash(-1) is -2 because -1 is the error return value of the C-level hash function.

Identity-like hashes for small integers are fast and, as the CPython source comments put it, give “better-than-random behavior in common cases”: the keys 0 to 999 in a table of 1,024 slots land in 1,000 distinct slots with no collisions at all. The cost is that patterns in the keys survive into the slot indices. The source gives the example [i << 16 for i in range(20000)]: every key ends in sixteen zero bits, so in a table of $2^{15}$ slots, all of them have the same initial index. CPython’s answer is a collision-resolution scheme that mixes in the high bits of the hash (described below), rather than a slower hash function.

Strings, randomization and PYTHONHASHSEED

$ python3 -c "print(hash('apple'), hash(b'apple'), hash(42))"
3932752207311670483 3932752207311670483 42
$ python3 -c "print(hash('apple'), hash(b'apple'), hash(42))"
5183978361766030499 5183978361766030499 42

The hash of a str or bytes changes from one process to the next, while the hash of an integer does not. Since Python 3.3, string and bytes hashes are salted with a random per-process key, and since Python 3.4 the algorithm is SipHash (PEP 456), a keyed hash designed by Jean-Philippe Aumasson and Daniel J. Bernstein for this purpose; Python 3.14 uses the SipHash-1-3 variant (sys.hash_info.algorithm reports 'siphash13').

Two consequences follow:

• Iteration order of sets of strings varies between runs. Two runs of print({'apple', 'banana', 'cherry', 'date'}) here printed {'banana', 'date', 'cherry', 'apple'} and {'apple', 'date', 'banana', 'cherry'}. Code or tests that depend on set order are broken even if they pass today. Dicts are unaffected because they preserve insertion order.
• Hashes must never be persisted or sent between processes. A hash computed by one process is meaningless to another. For on-disk or network use, pick a specified function: hashlib (BLAKE2, SHA-256), or a fixed non-cryptographic function such as xxHash or MurmurHash from a third-party package.

Setting the environment variable PYTHONHASHSEED to an integer fixes the salt, making runs reproducible; PYTHONHASHSEED=0 disables randomization.

$ PYTHONHASHSEED=0 python3 -c "print(hash('apple'))"
-2003999543335776700
$ PYTHONHASHSEED=0 python3 -c "print(hash('apple'))"
-2003999543335776700

This is useful for reproducing a bug and harmful in production, because it brings back the attack the salt exists to prevent.

Hash flooding

If an attacker can choose many keys that all hash to the same slot, every insert must compare against every previous key in that slot, and building the table becomes quadratic. This was described as an algorithmic complexity attack by Scott Crosby and Dan Wallach in 2003, and in 2011 it was shown to take down web frameworks in many languages by posting a request body with thousands of crafted form-field names, all colliding in the framework’s parameter dictionary. Randomized string hashing was the industry’s response.

Python’s integer hashes are not randomized, so the attack is easy to demonstrate with them. Every multiple of $2^{61} - 1$ hashes to 0:

P = 2**61 - 1
normal = list(range(1, n + 1))
evil = [i * P for i in range(1, n + 1)]          # every one hashes to 0

Time to build set(normal) and set(evil):

Doubling n doubles the normal time and quadruples the colliding time. At 16,000 keys the colliding set is over 13,000 times slower. Any service that builds dicts or sets of integers parsed from untrusted input (JSON object keys are strings, but IDs in arrays are often integers) is exposed to this, and the usual mitigations are limits on input size and on the number of keys rather than a different hash. Some implementations add a structural fallback: Java’s HashMap converts a bucket that grows beyond about eight entries into a balanced tree, which bounds the worst case per bucket at O(log n) when keys are comparable.

Hashing user-defined objects

In Python, an object is hashable if it defines __hash__ and its hash never changes during its lifetime. Built-in mutable containers (list, dict, set) are unhashable for that reason; tuple and frozenset are hashable if their contents are. A class that defines __eq__ without __hash__ gets __hash__ = None and becomes unhashable, so that the equality-consistency rule cannot be broken by accident. A @dataclass(frozen=True) generates a matching __eq__ and __hash__ from its fields.

Mutating an object after using it as a key breaks the table silently:

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

p = Point(1, 2)
seen = {p}
p.x = 99                                   # mutate a key that is already stored
print(p in seen, Point(1, 2) in seen, Point(99, 2) in seen, len(seen))

False False False 1

The set holds one element and cannot find it under either its old value or its new one. The element sits in the slot chosen for hash (1, 2); lookups for (99, 2) go to a different slot, and the lookup for (1, 2) finds the stored object but compares it as unequal because it now says (99, 2).

Collision resolution

There are two families. Separate chaining stores, in each slot, a secondary container (traditionally a linked list) of all the keys that hash there. Open addressing stores every key in the array itself; on a collision, it follows a deterministic probe sequence of other slots until it finds a free one, and lookups follow the same sequence until they find the key or an empty slot.

Separate chaining

m = 8, keys 3, 11, 12, 19, 21 with h(k) = k

slot 0: -
slot 1: -
slot 2: -
slot 3: 3 -> 11 -> 19
slot 4: 12
slot 5: 21
slot 6: -
slot 7: -

class ChainedHashMap:
    """Separate chaining: each bucket is a Python list of (key, value) pairs."""

    def __init__(self, capacity=8, max_load=1.0):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0
        self._max_load = max_load

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

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

    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))
        self._size += 1
        if self._size > self._max_load * len(self._buckets):
            self._resize(2 * len(self._buckets))

    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = bucket[-1]     # order inside a bucket does not matter
                bucket.pop()
                self._size -= 1
                return
        raise KeyError(key)

    def _resize(self, capacity):
        old = self._buckets
        self._buckets = [[] for _ in range(capacity)]
        for bucket in old:
            for k, v in bucket:
                self._buckets[hash(k) % capacity].append((k, v))

All three map classes in this chapter were checked against a Python dict over 200 random sequences of up to 600 mixed inserts, overwrites, deletes and lookups, using keys chosen to collide often.

Under uniform hashing, a chain has α keys on average. An unsuccessful search examines the whole chain, about α keys; a successful search examines about half the chain before it, $1 + \alpha/2$ keys. Chaining degrades gracefully: at α = 1 lookups still examine about 1.5 keys, and α above 1 is legal (Java’s HashMap resizes at 0.75, but nothing breaks at 2). Deletion is simple, because removing a key from a chain does not affect any other key’s lookup.

The costs are a pointer chase per chain node (each node is a separate allocation, which is unfriendly to caches) and the memory for the nodes. Chaining is used by Java’s HashMap, by C++‘s std::unordered_map (the standard’s iterator and reference stability rules effectively require it), and by Redis’s main dictionary, which also rehashes incrementally into a second table to avoid long pauses (see Redis internals). PostgreSQL’s hash indexes use buckets with overflow pages, a disk-oriented form of chaining.

Linear probing

Open addressing with the simplest probe sequence: try h, then h + 1, h + 2, and so on, wrapping around.

m = 8, h(k) = k mod 8, insert 3, 11, 19, 4 in that order

insert 3:  slot 3 free                         [ . . . 3 . . . . ]
insert 11: slot 3 taken, slot 4 free           [ . . . 3 11 . . . ]
insert 19: slots 3, 4 taken, slot 5 free       [ . . . 3 11 19 . . ]
insert 4:  home slot 4 taken (by 11), 5 taken, slot 6 free
                                               [ . . . 3 11 19 4 . ]

Key 4 never collided with another key whose hash was 4. It ran into the cluster that keys hashing to 3 had built. That is primary clustering: occupied slots form runs, any key whose home slot falls anywhere in a run extends it, and long runs grow faster than short ones because they present a larger target. The expected cost of an operation therefore grows much faster than the load factor alone suggests.

Linear probing is still widely used, because a probe sequence that walks consecutive memory is ideal for CPU caches: the next few slots are usually in the same cache line. At moderate load factors, the cache advantage outweighs the extra probes.

Quadratic probing

Probe h + c1·i + c2·i² for i = 0, 1, 2, … The jumps grow, so a key escapes a cluster quickly. Two details matter:

• The sequence must reach enough slots. With a power-of-two table, the triangular-number sequence $h + i(i+1)/2$ visits every slot exactly once. With $h + i^2$ and a prime table size, only about half the slots are reachable, which is enough to guarantee an insert succeeds only while α ≤ 1/2.
• Keys with the same home slot still follow exactly the same sequence. That is secondary clustering, milder than primary clustering because keys with nearby (but different) home slots no longer share a path.

Double hashing

Use a second hash function for the step size: probe h1 + i·h2 for i = 0, 1, 2, … Keys that share a home slot usually have different steps, so they diverge immediately, which removes secondary clustering as well. The step must be coprime with m so that the sequence can reach every slot: with a power-of-two table, make h2 odd. Double hashing comes closest in practice to the idealized uniform hashing model, in which each key’s probe sequence is a random permutation of the slots. Its cost is a second hash computation and probes that jump around memory.

Measured probe counts versus Knuth’s formulas

Donald Knuth’s analysis of linear probing, from 1963 and included in The Art of Computer Programming, Volume 3, gives the expected number of probes for a table with load factor α (large-table approximations):

$\text{successful} \approx \tfrac{1}{2}\left(1 + \frac{1}{1-\alpha}\right) \qquad \text{unsuccessful} \approx \tfrac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$

For uniform hashing (the idealized model that double hashing approximates), the corresponding results are:

$\text{successful} \approx \frac{1}{\alpha}\ln\frac{1}{1-\alpha} \qquad \text{unsuccessful} \approx \frac{1}{1-\alpha}$

The experiment fills a table of $2^{16}$ slots to each load factor with random 64-bit hashes, counts probes for every stored key (successful search), and counts probes for 20,000 absent keys (unsuccessful search, which stops at the first empty slot). Formula values are in parentheses.

Separate chaining in the same experiment examined within 0.01 of $1 + \alpha/2$ keys per successful search at every load factor (1.13 at 0.25, 1.45 at 0.9), and within 0.01 of α keys per unsuccessful search.

What the numbers show:

• Knuth’s formulas predict linear probing closely up to α = 0.8. At 0.9 and 0.95 the measured unsuccessful cost falls below the formula, because the formula is an asymptotic expectation and the variance at high load is enormous (a single long cluster dominates), but the explosion is real: from 2.5 probes at α = 0.5 to 172 at 0.95.
• Double hashing matches the uniform hashing model almost exactly, which is the sense in which it “approximates random probing”.
• Quadratic probing sits between the two, the measurable cost of secondary clustering.
• Unsuccessful searches suffer far more than successful ones. Inserts of new keys are unsuccessful searches too.
• Below α = 0.5, every scheme is cheap. The differences that matter appear above about 0.7, which is why open-addressing tables keep their maximum load between 0.5 and about 0.9 depending on the scheme.

Primary clustering, seen directly

Probe counts are averages; clusters are easier to see by measuring the longest run of consecutive occupied slots in the same $2^{16}$-slot tables:

Double hashing leaves runs that occur by chance; linear probing merges them into much longer ones. At α = 0.9, a lookup whose home slot is near the start of the 500-slot run needs hundreds of probes.

Robin Hood hashing

Robin Hood hashing, introduced by Pedro Celis in 1986, is linear probing with one extra rule on insert: while probing, compare the incoming key’s distance from its home slot with the resident key’s distance from its own home. If the resident is closer to home (“richer”), the incoming key takes the slot and the resident continues probing instead. Keys that have traveled far are never pushed further by keys that have barely moved.

def put(self, key, value):
    if 10 * (self._size + 1) > 9 * len(self._slots):   # max load 0.9
        self._resize()
    mask = len(self._slots) - 1
    entry = (hash(key), key, value)
    i = entry[0] & mask
    d = 0                                 # distance of `entry` from its home slot
    while True:
        slot = self._slots[i]
        if slot is None:
            self._slots[i] = entry
            self._size += 1
            return
        if slot[0] == entry[0] and slot[1] == entry[1]:
            self._slots[i] = entry       # only the original key can match here
            return
        slot_d = self._dist(slot[0], i)
        if slot_d < d:                   # resident is richer: swap and carry it on
            self._slots[i], entry = entry, slot
            d = slot_d
        i = (i + 1) & mask
        d += 1

The rule does not change the average probe count at all, since it only redistributes the same total displacement among keys. It changes the variance, which is what decides the worst lookups. Probe counts for all stored keys:

The means are identical to two decimals and the maximum at α = 0.9 falls from 439 to 35. Robin Hood also allows early termination of unsuccessful lookups: once the probe distance exceeds the resident’s distance, the key cannot be further along, because it would have displaced that resident. And it permits backward-shift deletion: instead of a tombstone, shift the following displaced keys back by one slot until reaching an empty slot or a key at its home. The implementation used for these measurements does that. Rust’s standard HashMap used Robin Hood hashing until 2019, when it switched to a SwissTable design.

Comparing the schemes

Modern high-performance tables add a further idea: store a few bits of each key’s hash in a separate compact metadata array and use SIMD instructions to compare 16 of them at once, probing in groups. Google’s SwissTable (in Abseil) is the best-known design of this kind, and Go’s built-in map moved to a Swiss-table design in Go 1.24.

Deletion and tombstones

Deleting from an open-addressing table cannot just empty the slot. Lookups stop at the first empty slot they meet, so emptying a slot in the middle of a probe sequence makes every key beyond it unreachable. A demonstration with three keys that all hash to slot 0 of an 8-slot table (0, 32 and 64), deleting the middle one and then looking up the last:

class BrokenMap(LinearProbingMap):
    def delete(self, key):                 # wrong: mark the slot empty
        i, found = self._find(key)
        if not found: raise KeyError(key)
        self._keys[i] = _EMPTY
        self._values[i] = None
        self._size -= 1

for cls in (LinearProbingMap, BrokenMap):
    m = cls()
    for k in (0, 32, 64):
        m.put(k, str(k))
    m.delete(32)
    print(cls.__name__, m.get(64))

LinearProbingMap 64
BrokenMap None

The fix is a tombstone (also called a dummy or deleted marker): a third slot state that lookups treat as occupied (keep probing) and inserts treat as free (may reuse it).

_EMPTY = object()
_TOMBSTONE = object()

class LinearProbingMap:
    """Open addressing with linear probing and tombstone deletion."""

    def __init__(self, capacity=8):
        self._keys = [_EMPTY] * capacity     # capacity is a power of two
        self._values = [None] * capacity
        self._size = 0                       # live keys
        self._used = 0                       # live keys + tombstones

    def _find(self, key):
        """Return (slot, found). If not found, slot is where the key should go."""
        mask = len(self._keys) - 1
        i = hash(key) & mask
        first_tombstone = None
        while True:
            k = self._keys[i]
            if k is _EMPTY:
                return (i if first_tombstone is None else first_tombstone), False
            if k is _TOMBSTONE:
                if first_tombstone is None:
                    first_tombstone = i
            elif k == key:
                return i, True
            i = (i + 1) & mask

    def get(self, key, default=None):
        i, found = self._find(key)
        return self._values[i] if found else default

    def put(self, key, value):
        i, found = self._find(key)
        if not found:
            if self._keys[i] is _EMPTY:      # reusing a tombstone does not raise _used
                self._used += 1
            self._keys[i] = key
            self._size += 1
        self._values[i] = value
        if 3 * self._used >= 2 * len(self._keys):   # keep load (with tombstones) under 2/3
            self._resize()

    def delete(self, key):
        i, found = self._find(key)
        if not found:
            raise KeyError(key)
        self._keys[i] = _TOMBSTONE           # not _EMPTY: that would cut probe chains
        self._values[i] = None
        self._size -= 1

    def _resize(self):
        live = [(k, v) for k, v in zip(self._keys, self._values)
                if k is not _EMPTY and k is not _TOMBSTONE]
        capacity = 8
        while 3 * len(live) >= capacity:     # new load at most about 1/3
            capacity *= 2
        self._keys = [_EMPTY] * capacity
        self._values = [None] * capacity
        self._size = self._used = 0
        for k, v in live:
            self.put(k, v)

Three details are easy to get wrong:

• Insert must search the whole chain before reusing a tombstone. The key might already exist beyond the tombstone; writing it into the tombstone would create a duplicate. _find remembers the first tombstone and keeps going until it hits an empty slot.
• Tombstones count toward the load. A table that sees many inserts and deletes can fill up with tombstones while holding few live keys, and then unsuccessful lookups probe almost the whole table. The resize trigger above counts _used (live keys plus tombstones), and resizing discards all tombstones. The new capacity is chosen from the live count, so a table full of tombstones can rebuild at the same size or smaller.
• Never empty a slot after a lookup “finishes”. Only a rebuild may turn tombstones back into empty slots. CPython’s source says the same: “Dummy slots cannot be made Unused again else the probe sequence in case of collision would have no way to know they were once active.”

Linear probing also admits deletion without tombstones (Knuth’s Algorithm R): after emptying a slot, walk forward through the run and move back any key whose home slot is at or before the hole, since its probe sequence would otherwise skip it. The Robin Hood backward shift is a special case of this.

Resizing

A table that never grows has a load factor that rises without bound, so every implementation resizes once α passes a threshold: allocate a larger array and reinsert every key. Reinsertion is required, not just copying, because slot indices depend on the table size.

If the size is multiplied by a constant factor (usually 2) each time, the total resize work over n inserts is bounded by $n + n/2 + n/4 + \dots < 2n$ key moves, so the amortized cost per insert remains O(1). Growing by a constant amount instead (say, 1,000 slots) makes the total quadratic. The argument is the same as for dynamic arrays in Arrays.

The individual resize is still O(n). For latency-sensitive systems that is sometimes unacceptable, and incremental rehashing spreads the move over subsequent operations: keep the old and new tables both alive, look up in both, and move a few buckets on each operation until the old table is empty. Redis does this.

Watching CPython’s dict grow (sys.getsizeof after each insert, printing only when it changes):

len 0: 64 bytes
len 1: 224 bytes
len 6: 352 bytes
len 11: 632 bytes
len 22: 1,168 bytes
len 43: 2,264 bytes
len 86: 4,688 bytes
len 171: 9,304 bytes
len 342: 18,512 bytes
len 683: 36,952 bytes
len 1366: 73,808 bytes
len 2731: 147,544 bytes
len 5462: 294,992 bytes
len 10923: 589,912 bytes
len 21846: 1,310,800 bytes
len 43691: 2,621,528 bytes
len 87382: 5,242,960 bytes
len 174763: 10,485,848 bytes

An empty dict allocates no table. The first table has 8 index slots and room for 5 entries; each resize happens when the entry array fills (at 6, 11, 22, 43, … keys), and the size roughly doubles each time. The thresholds are two thirds of a power of two, plus one: the dict’s maximum load factor is 2/3.

Shrinking is less common. Many tables never shrink on deletes; CPython’s dict does not shrink when keys are deleted, only when it is rebuilt by a later insert-triggered resize (which sizes the new table from the number of live keys) or copied. If memory matters after a mass deletion, d = dict(d) builds a right-sized copy.

How CPython’s dict works

CPython’s dict, as of Python 3.14, is described in Objects/dictobject.c and Objects/dictnotes.txt in the CPython repository. It is an open-addressing table with three distinctive features.

The compact layout: indices and entries

Since Python 3.6, a dict stores two arrays instead of one:

d = {"b": 2, "a": 1, "c": 3}     table size 8

indices (the hash table, 1 byte per slot at this size)
slot:    0     1     2     3     4     5     6     7
       [ -1 ][ 1  ][ -1 ][ 0  ][ -1 ][ -1 ][ 2  ][ -1 ]      -1 = empty, -2 = dummy

entries (dense, in insertion order)
  0: hash("b"), "b", 2
  1: hash("a"), "a", 1
  2: hash("c"), "c", 3

(The slot positions above are illustrative; they depend on the randomized string hashes.)

• dk_indices is the real hash table. Each slot holds an index into the entries array, or DKIX_EMPTY (-1), or DKIX_DUMMY (-2, the tombstone). The index width depends on the table size: one byte for tables up to 128 slots, two bytes up to $2^{15}$, four bytes up to $2^{31}$, eight beyond.
• dk_entries is a dense array of (hash, key, value) records in insertion order, sized to two thirds of the table size (USABLE_FRACTION).

Two benefits follow. Memory: the sparse array is made of small integers instead of 24-byte records, so the empty third of the table costs a few bytes per slot instead of 24. And iteration: walking dk_entries yields keys in insertion order, which is why dicts became ordered. The design was proposed by Raymond Hettinger in 2012, implemented first in PyPy, adopted by CPython in 3.6, and insertion order became a language guarantee in Python 3.7.

Deleting a key writes DKIX_DUMMY into its index slot and clears its entry, leaving a hole in dk_entries. Holes are removed only when the dict is resized, so a dict that has had many deletions iterates over the holes too. The stored hash in each entry lets resizing and comparisons skip recomputing hashes, and lets lookups reject most non-matching keys by comparing hashes before calling __eq__.

Perturbation probing

The initial slot is the low bits of the hash, hash & mask, which is fast and collision-free for runs of consecutive integers. Collisions are resolved with this recurrence (from the source):

perturb >>= PERTURB_SHIFT;           /* PERTURB_SHIFT is 5 */
i = mask & (i*5 + perturb + 1);

perturb starts as the full hash. The 5*i + 1 part alone visits every slot of a power-of-two table exactly once in a scrambled order, so consecutive integer keys that collide do not follow each other along the same path. Adding perturb, which is shifted right five bits per step, brings the high bits of the hash into play within the first few probes, which defeats regular patterns such as keys that are all multiples of $2^{16}$. Once perturb reaches zero the recurrence is pure 5*i + 1, which is guaranteed to find an empty slot because the table is never full. The source comments record that the shift of 5 was chosen experimentally by Tim Peters, with 4 and 6 nearly as good.

Load factor and growth

• PyDict_MINSIZE is 8: a new table has 8 index slots and holds at most 5 entries.
• The maximum load is USABLE_FRACTION(n) = 2n/3. When the entries array is full, the dict resizes.
• The new size is the smallest power of two that is at least GROWTH_RATE = used * 3 (live keys times 3). With no deletions that doubles the table; with many deletions, the new table can be the same size or smaller, which reclaims tombstones without growing.

Other details

• Key-sharing (split) dictionaries. Instances of the same class usually have the same attribute names, so CPython can share one keys table among them and store only the values per instance. Recent versions go further and keep instance attributes in an inline values array when possible.
• String-only fast path. Dicts whose keys are all str use a smaller entry layout without a stored hash field (strings cache their own hash) and a specialized lookup.
• Equality check order. A lookup compares identity first (is), then the stored hash, and only then calls __eq__. That is why a key with a broken __eq__ can still be found by identity, and why float('nan'), which is not equal to itself, can still be found in a dict if the same object is used.

Sets are different

set (in Objects/setobject.c) is not a dict without values. It stores (key, hash) entries directly in a single open-addressing table with no separate index array, since sets do not preserve order. Its probing is a hybrid: at each step it first checks the next LINEAR_PROBES (9) adjacent slots, which are likely in the same cache line, and only then jumps using the same perturbation recurrence as dict. The source comments explain the reasoning: set lookups are often for keys that are absent, so both the hit and the miss path must be fast. Sets resize when 60 percent full (fill*5 >= mask*3), growing to the smallest power of two above four times the number of live keys, or twice for sets larger than 50,000.

Set algebra costs follow from the representation: a & b iterates the smaller set and probes the larger, O(min(len(a), len(b))); a | b is O(len(a) + len(b)); x in s is O(1) on average. frozenset is the hashable, immutable version, usable as a dict key or as an element of another set.

Patterns

Most hash-map problems reduce to one question asked in a loop: “have I seen something that pairs with this?” The hash map turns that question from an O(n) scan into an O(1) lookup, and the algorithm from O(n²) into O(n).

Frequency counting

collections.Counter is a dict subclass for counts:

>>> from collections import Counter
>>> Counter("mississippi").most_common(2)
[('i', 4), ('s', 4)]

Counting is O(n). Counters support arithmetic (c1 - c2 keeps positive counts only), total(), and comparison as multisets. Valid Anagram is Counter(s) == Counter(t). First Unique Character in a String counts in one pass and finds the first count of 1 in a second pass. Top K Frequent Elements counts in O(n) and then selects with a heap or bucket sort (see Heaps). For a small known alphabet, a list of 26 counters indexed by ord(ch) - ord('a') is faster than a dict and can itself serve as a hashable key once converted to a tuple.

Counting distinct elements and detecting duplicates

len(set(xs)) counts distinct elements in O(n) expected time and O(n) memory. Contains Duplicate is len(set(nums)) < len(nums), or an early-exit loop:

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

On a million distinct random integers, len(set(nums)) < len(nums) took 44 ms, the early-exit loop 67 ms (the loop runs in Python, and with no duplicates it never exits early), and sorting followed by a scan for equal neighbors 271 ms. Sorting uses O(1) extra space if done in place, which is the trade-off when memory is tight. Contains Duplicate II (two equal values within distance k) stores the last index of each value; Contains Duplicate III (values within t, indices within k) uses buckets of width t + 1, a hashing trick in its own right.

When the number of distinct elements is too large to hold in memory, exact counting is replaced by sketches. HyperLogLog estimates the number of distinct elements in a few kilobytes with about 1 to 2 percent error, and PostgreSQL extensions and Redis’s PFCOUNT provide it.

Grouping: Group Anagrams

Group Anagrams: group words that are anagrams of each other. Anagrams share a canonical form, so use it as the key:

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups["".join(sorted(w))].append(w)
    return list(groups.values())

>>> group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Sorting each word costs O(L log L), so the total is O(n · L log L) for n words of length L. Using a tuple of 26 letter counts as the key makes it O(n · L). The general pattern, “compute a canonical key and bucket by it”, covers grouping shifted strings (key: the differences between consecutive letters), isomorphic strings, and duplicate files (key: size, then content hash).

Two Sum

Two Sum: return indices of two numbers that add up to the target. For each element, the partner it needs is target - x; look it up among the elements already seen.

def two_sum(nums, target):
    index = {}                              # value -> index where it was seen
    for i, x in enumerate(nums):
        j = index.get(target - x)
        if j is not None:
            return j, i
        index[x] = i
    return None

>>> two_sum([2, 7, 11, 15], 9)
(0, 1)

Checking for the partner before inserting the current element prevents pairing an element with itself, and handles duplicates such as [3, 3] with target 6. O(n) expected time and O(n) space. On 5,000 random numbers with no solution (the worst case for both), the double loop took 357 ms and the hash map 0.32 ms. If the input is sorted, two pointers solve it in O(n) with O(1) space (see Arrays).

3Sum and 4Sum

3Sum asks for all unique triples summing to zero. The standard solution sorts and runs two pointers for each anchor, O(n²) time and O(1) extra space beyond the output, and deduplicates by skipping equal neighbors; it is covered in Arrays. A hash-set version anchors two elements and looks up the third:

def three_sum_hash(nums):
    nums = sorted(nums)
    found = set()
    for i in range(len(nums)):
        seen = set()
        for j in range(i + 1, len(nums)):
            need = -nums[i] - nums[j]
            if need in seen:
                found.add((nums[i], need, nums[j]))
            seen.add(nums[j])
    return sorted(found)

>>> three_sum_hash([-1, 0, 1, 2, -1, -4])
[(-1, -1, 2), (-1, 0, 1)]

It is also O(n²) expected, but deduplicating through a set of triples uses O(n²) memory in the worst case and runs slower than the two-pointer version. Sorting first makes each triple come out in sorted order, so equal triples are equal tuples.

4Sum (unique quadruplets with a given sum) extends the two-pointer approach with a second anchor, O(n³). 4Sum II is where hashing wins outright: count tuples (i, j, k, l) across four arrays with a[i] + b[j] + c[k] + d[l] == 0. Split into two halves, count all pairwise sums of the first two arrays in a Counter, and look up the negated pairwise sums of the other two:

def four_sum_count(a, b, c, d):
    pair_sums = Counter(x + y for x in a for y in b)
    return sum(pair_sums[-(x + y)] for x in c for y in d)

O(n²) time and space instead of O(n⁴). This meet in the middle idea, splitting a search into two halves that meet at a hash table, also solves subset-sum variants on up to about 40 elements by enumerating $2^{20}$ subsets of each half.

Subarray Sum Equals K

Subarray Sum Equals K: count contiguous subarrays summing to k, with negative numbers allowed (which rules out a sliding window). A subarray nums[i:j] sums to prefix[j] - prefix[i], so for each prefix sum p, the number of subarrays ending here with sum k equals the number of earlier prefix sums equal to p - k:

def subarray_sum(nums, k):
    count = 0
    prefix = 0
    seen = Counter({0: 1})                  # empty prefix
    for x in nums:
        prefix += x
        count += seen[prefix - k]           # earlier prefixes p with prefix - p == k
        seen[prefix] += 1
    return count

>>> subarray_sum([1, 2, 3, -3, 3], 3)
5

The seed {0: 1} counts subarrays that start at index 0. The lookup must happen before the current prefix is added, or k = 0 would count empty subarrays. O(n) time and space. Variants: storing the first index of each prefix sum instead of a count gives Maximum Size Subarray Sum Equals k; storing prefix sums modulo k gives Continuous Subarray Sum and Subarray Sums Divisible by K; mapping 0 to -1 turns Contiguous Array (equal numbers of 0s and 1s) into “longest subarray with sum 0”. The prefix-sum side is covered in Arrays.

Longest Consecutive Sequence

Longest Consecutive Sequence: the length of the longest run of consecutive integers in an unsorted array, in O(n). Sorting gives O(n log n). The hash-set solution starts counting only from numbers that begin a run, those whose predecessor is absent:

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:             # x starts a run
            y = x
            while y + 1 in values:
                y += 1
            best = max(best, y - x + 1)
    return best

>>> longest_consecutive([100, 4, 200, 1, 3, 2])
4

The inner while looks quadratic, but each number is visited by the inner loop only as part of the one run it belongs to, and only once, from that run’s start. Total work is O(n) expected. Two pitfalls: iterating over nums instead of values repeats the work for duplicated run starts (an input of n copies of the start of a long run becomes quadratic), and omitting the x - 1 not in values test makes the algorithm O(n²) on a single long run. A union-find over adjacent values also works, at more cost (see Graph algorithms).

When not to use a hash map

• Ordered queries. Hash tables cannot answer “smallest key above x”, range queries or sorted iteration. Use a sorted array with bisect, a balanced search tree or a B-tree (see Trees and PostgreSQL indexes).
• Small, dense integer keys. A list indexed by the key is faster and smaller.
• Very small collections. Linear search over a few elements is competitive, and a tuple of five items needs no hashing at all.
• Worst-case guarantees on adversarial input, where a balanced tree’s O(log n) bound may be worth more than a hash table’s expected O(1).
• Memory-constrained membership where false positives are acceptable: a Bloom filter (below).

Consistent hashing

Distributing keys across N servers by hash(key) mod N works until N changes. Going from 10 servers to 11 changes the result of mod N for almost every key, so almost every cached item is now looked up on the wrong server. Consistent hashing (Karger and colleagues, 1997) maps both servers and keys onto the same circular hash space; each key belongs to the first server clockwise from it. Adding a server takes over only the keys between it and its predecessor on the circle, about 1/N of them; removing one hands its keys to its successor.

positions on the circle, 0 at the top, increasing clockwise

                 0
          A  .  .  .  key1
         .             .         key1 -> B (next node clockwise)
        .               B        key2 -> C
        key3            .        key3 -> A
         .             .
          C  .  .  . key2

In practice, each server is placed at many points on the circle (virtual nodes), which evens out the arc lengths. An implementation with a sorted list of points and binary search:

import bisect, hashlib

def h64(s):
    return int.from_bytes(hashlib.blake2b(s.encode(), digest_size=8).digest(), "big")

class HashRing:
    def __init__(self, nodes=(), vnodes=100):
        self.vnodes = vnodes
        self._points = []            # sorted hash positions
        self._owner = {}             # position -> node
        for node in nodes:
            self.add(node)

    def add(self, node):
        for i in range(self.vnodes):
            p = h64(f"{node}#{i}")
            bisect.insort(self._points, p)
            self._owner[p] = node

    def remove(self, node):
        for i in range(self.vnodes):
            p = h64(f"{node}#{i}")
            self._points.pop(bisect.bisect_left(self._points, p))
            del self._owner[p]

    def node_for(self, key):
        i = bisect.bisect(self._points, h64(key)) % len(self._points)   # next point clockwise
        return self._owner[self._points[i]]

The hash must be stable across processes, so it uses hashlib, not Python’s randomized hash(). Lookup is O(log(N · vnodes)). Assigning 100,000 keys to 10 servers and then adding an eleventh:

consistent hashing: 11.4% of keys moved
hash mod N:         90.7% of keys moved

The ideal is 1/11, about 9.1 percent. Load balance depends on the number of virtual nodes per server:

With one point per server, the busiest has 55 times as many keys as the idlest; with 1,000 points, every server is within 8 percent of the ideal 10,000. Consistent hashing is used for partitioning in Amazon’s Dynamo design and its descendants (Cassandra, Riak), in memcached client libraries and in load balancers. Rendezvous (highest random weight) hashing and jump consistent hash are alternatives with no ring to store.

Bloom filters

A Bloom filter (Burton Bloom, 1970) answers set membership in a fixed, small amount of memory, at the price of occasional false positives. It never gives false negatives: “no” means definitely absent, “yes” means probably present.

The structure is a bit array of m bits and k hash functions. To add an item, set the k bits it hashes to. To query, check those k bits: if any is 0, the item was never added; if all are 1, it was probably added, or its bits were all set by other items.

m = 16 bits, k = 3

add "cat"  -> bits 2, 7, 13
add "dog"  -> bits 4, 7, 11
bits:  0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0

query "cow" -> bits 2, 9, 13: bit 9 is 0           -> definitely absent
query "emu" -> bits 4, 11, 13: all 1 (set by others) -> false positive

With n items, the probability that a given bit is still 0 is $(1 - 1/m)^{kn} \approx e^{-kn/m}$, so the false positive rate is approximately

$p \approx \left(1 - e^{-kn/m}\right)^k$

For a target rate p, the optimal sizes are $m = -\frac{n \ln p}{(\ln 2)^2}$ bits and $k = \frac{m}{n}\ln 2$ hash functions, which works out to about 9.6 bits per item for 1 percent and 14.4 for 0.1 percent, independent of the size of the items themselves.

import hashlib, math

class BloomFilter:
    def __init__(self, n_items, fp_rate):
        self.m = math.ceil(-n_items * math.log(fp_rate) / math.log(2) ** 2)  # bits
        self.k = max(1, round(self.m / n_items * math.log(2)))              # hash count
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item):
        digest = hashlib.blake2b(item.encode(), digest_size=16).digest()
        h1 = int.from_bytes(digest[:8], "little")
        h2 = int.from_bytes(digest[8:], "little") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for p in self._positions(item):
            self.bits[p >> 3] |= 1 << (p & 7)

    def __contains__(self, item):
        return all(self.bits[p >> 3] & (1 << (p & 7)) for p in self._positions(item))

The k positions come from two independent 64-bit halves of one BLAKE2 digest combined as $h_1 + i \cdot h_2$, a technique shown by Kirsch and Mitzenmacher (2006) to give the same asymptotic false positive rate as k independent hash functions. Filling filters with 100,000 items, confirming that all of them test positive, and querying 1,000,000 items that were never added:

The measured rates match the formula to within sampling noise. For comparison, a Python set of the same 100,000 strings measured 4.2 MB for the table alone (sys.getsizeof) plus 5.1 MB for the string objects; the 1 percent filter takes 117 KiB.

Limitations: standard Bloom filters cannot delete (clearing a bit could remove other items too; counting Bloom filters replace bits with small counters), cannot list their contents, and degrade quickly if more items are added than they were sized for. Cuckoo filters support deletion with similar space. Uses: LSM-tree databases keep a Bloom filter per on-disk file to skip files that cannot contain a key; PostgreSQL ships a bloom index extension and a Bloom-filter operator class for BRIN indexes; web browsers have used them to check URLs against malware lists before making a network request; and distributed joins send a Bloom filter of one side’s keys to filter the other side before shipping rows.

Summary