Hash maps, from first idea to production

At a coat check you hand over your coat and get a ticket with a number on it. When you come back, the attendant doesn’t walk the rail asking every coat whether it’s yours. They read the number and go to that hook. It takes the same few seconds whether there are ten coats or a thousand.

A hash map is that coat check, built out of an array and a bit of arithmetic. It’s the data structure I use most in backend work, by a distance: caches, sessions, rate limiters, deduplication, joining rows in memory, counting things. Python’s objects, modules and keyword arguments are hash maps underneath. If you understand one data structure deeply, this is the one that pays back fastest.

By the end of this article you’ll be able to use dictionaries and sets fluently, explain exactly what happens inside them, solve the classic interview problems that depend on them, reason about the costs most tutorials skip (resizing, deletion, memory, attackers), and recognize where they hold real systems together. Start at Beginner if the word “hash” is new to you. If you already use dicts every day, jump to Intermediate or further with the level bar above.

Beginner: the lookup problem

Finding things is the expensive part

Most programs spend their time looking things up. Is this email already registered? What’s the price of product 4411? Which customer sent this message? The question is always the same shape: given a key, find the matching thing.

The simplest way to store things is a list. Here’s the coat check as a list of (ticket, coat) pairs:

coats = [(101, "black wool coat"), (102, "red raincoat"), (103, "denim jacket")]

def find_coat(ticket):
    for number, coat in coats:      # walk the rail, one hanger at a time
        if number == ticket:
            return coat
    return None

print(find_coat(103))
# denim jacket

That works, and with three coats it’s instant. But look at what find_coat does: it checks every pair from the start until it finds a match. With 1,000 coats, a ticket near the end takes about 1,000 checks. A ticket that isn’t there at all always takes all 1,000, because you can only say “no” after looking at everything.

Here’s the same data as a dictionary, Python’s hash map:

rail = {101: "black wool coat", 102: "red raincoat", 103: "denim jacket"}
print(rail[103])                    # go straight to hook 103
# denim jacket

rail[103] doesn’t loop. It computes where 103 lives and looks there. That’s the whole idea, and the rest of this article is about how “computes where it lives” works and what it costs.

Dictionaries: keys and values

A dictionary stores entries. Each entry is a key (what you look up by) and a value (what you get back). Keys are unique: storing a second value under the same key replaces the first.

stock = {"apple": 12, "banana": 0}

stock["cherry"] = 40            # insert a new key
stock["apple"] = 11             # update an existing key
print(stock["apple"])           # read
print("banana" in stock)        # is the key there?
print(stock.get("durian"))      # missing key: None instead of an error
print(stock.get("durian", 0))   # ...or a default you choose
del stock["banana"]             # delete
print(len(stock), stock)

for fruit, count in stock.items():
    print(fruit, count)
# 11
# True
# None
# 0
# 2 {'apple': 11, 'cherry': 40}
# apple 11
# cherry 40

Five operations matter, and all of them are fast no matter how big the dictionary gets:

Two things trip people up early. First, in checks keys, not values: "apple" in stock is fast, while 11 in stock.values() walks every value one by one. Second, d[key] on a missing key raises KeyError. Use .get when “missing” is a normal case rather than a bug.

Counting with a dictionary

The single most common thing I do with a dictionary is count. Here’s a word count, by hand and then with the standard library:

text = "the cat sat on the mat the end"

counts = {}
for word in text.split():
    counts[word] = counts.get(word, 0) + 1
print(counts)

from collections import Counter
print(Counter(text.split()).most_common(2))
# {'the': 3, 'cat': 1, 'sat': 1, 'on': 1, 'mat': 1, 'end': 1}
# [('the', 3), ('cat', 1)]

counts.get(word, 0) + 1 reads “the count so far, or zero if this is the first time, plus one”. Counter is a dictionary subclass that does the same thing and adds helpers like most_common. Counting votes, errors per endpoint, messages per customer, letters in a word: it’s all this loop.

Sets: a dictionary with only keys

Sometimes there’s no value to store. You only want to know whether you’ve seen something. That’s a set: a collection of unique keys with the same fast membership test.

seen = {"ali", "ben"}
seen.add("chen")
seen.add("ali")                  # already there: nothing changes
print(len(seen), "chen" in seen)

a = {"python", "sql", "aws"}
b = {"python", "go"}
print(a & b)                     # in both
print(a | b == {"python", "sql", "aws", "go"})   # in either
print(a - b == {"sql", "aws"})   # in a but not b

emails = ["x@a.com", "y@b.com", "x@a.com", "z@c.com", "y@b.com"]
print(list(dict.fromkeys(emails)))   # dedupe, keep first-seen order
# 3 True
# {'python'}
# True
# True
# ['x@a.com', 'y@b.com', 'z@c.com']

A set has no order you can rely on, which is why I compared sets with == above instead of printing them. When you want to remove duplicates and keep the original order, dict.fromkeys(items) does it, because dictionaries remember insertion order (more on why in Advanced).

The bug hiding in in

Here’s the mistake I see most in code reviews. It reads perfectly well, passes every test with small data, and falls over in production:

import time

staff_ids = list(range(0, 200_000, 2))      # 100,000 even numbers
senders = list(range(0, 20_000))            # 20,000 incoming senders

start = time.perf_counter()
internal = [s for s in senders if s in staff_ids]          # list: a hidden loop
list_seconds = time.perf_counter() - start

staff_set = set(staff_ids)                                  # built once
start = time.perf_counter()
internal_fast = [s for s in senders if s in staff_set]     # set: one jump each
set_seconds = time.perf_counter() - start

print(internal == internal_fast, len(internal))
print(f"list: {list_seconds:.2f} s   set: {set_seconds * 1000:.2f} ms")
# True 10000
# list: 5.97 s   set: 0.82 ms

Same answer, about seven thousand times faster, on my laptop. s in staff_ids looks like one step, but on a list it’s a loop over up to 100,000 items, and it runs 20,000 times. That’s up to two billion comparisons. On a set, each in is one hash and one or two slot checks.

Race the two yourself. Both machines hold the same 16 numbers:

The cost of the list version is senders × staff, an area. The cost of the set version is senders + staff, a line: one pass to build the set, one pass to check. Areas grow much faster than lines:

The rule to keep: when you see in inside a loop, look at what’s on the right of it. A list there means a second, hidden loop.

When a list is still the right choice

Hash maps aren’t free, and sometimes a list is better:

• The collection is tiny and the check isn’t in a hot loop. status in ("pending", "sent", "failed") scans three items. That costs nothing.
• You only check once. Building a set walks the whole list anyway, so for a single in, the list is just as fast.
• You need order, duplicates or positions. Sets have none of those, and dictionaries only remember insertion order.
• The items can’t be hashed, like lists or dictionaries. More on that in Intermediate.

def first_repeat(items):
    seen = set()
    for item in items:
        if item in seen:
            return item
        seen.add(item)
    return None

print(first_repeat(["x@a.com", "y@b.com", "z@c.com", "y@b.com", "x@a.com"]))
print(first_repeat([1, 2, 3]))
# y@b.com
# None

from collections import Counter

def is_anagram(a, b):
    return Counter(a) == Counter(b)

print(is_anagram("listen", "silent"), is_anagram("rat", "car"))
# True False

Intermediate: how a hash map works inside

You’ve seen what a dictionary does. Now for how: how does rail[103] know where to look?

Step 1: turn the key into a number

A hash map is built on an ordinary array, and arrays are indexed by position: slot 0, slot 1, slot 2. So the first job is to turn any key, a string, a number, a tuple, into a number. That’s the hash function. A good one has three properties:

1. Deterministic. The same key always gives the same number, at least for the life of the program. Otherwise you’d store something and never find it again.
2. Fast. It runs on every single lookup.
3. Spreads keys out. Similar keys (“cat”, “act”, “cab”) should get very different numbers, so they don’t all crowd into the same place.

Here’s a real, simple hash function. It’s the recipe Java uses for strings: start at 0, and for each character multiply by 31 and add the character’s code.

def toy_hash(key: str) -> int:
    h = 0
    for ch in key:
        h = (h * 31 + ord(ch)) % 2**32   # the same recipe as Java's String.hashCode
    return h

for word in ["cat", "dog", "act", "Aa", "BB"]:
    h = toy_hash(word)
    print(f"{word:>4}  hash={h:>6}  slot={h % 8}")
#  cat  hash= 98262  slot=6
#  dog  hash= 99644  slot=4
#  act  hash= 96402  slot=2
#   Aa  hash=  2112  slot=0
#   BB  hash=  2112  slot=0

“cat” and “act” have the same letters but different hashes, because multiplying by 31 at each step makes position matter. Keep an eye on “Aa” and “BB”: different strings, identical hash. That matters a lot in the Expert section.

Step 2: squeeze the number into a slot

The hash can be any size, and the array has only a few slots, so the second step squeezes the hash into range with the remainder operator: slot = hash % capacity. With 8 slots, 98262 % 8 = 6, so “cat” lives in slot 6.

Storing is: hash the key, find the slot, put the entry there. Looking up is: hash the key, find the slot, check what’s there. Neither step depends on how many other keys exist. That’s where the speed comes from.

Collisions are guaranteed

There are far more possible keys than slots, so two keys will sooner or later land in the same slot. That’s a collision, and it isn’t rare. It’s the birthday problem: with 23 people in a room, there’s a better than even chance two share a birthday. With 8 slots and only 4 keys, the chance that at least two collide is 1 − (8 × 7 × 6 × 5) / 8⁴ = 1 − 1,680 / 4,096, about 59%.

So every hash map needs a plan for collisions. There are two families.

Separate chaining. Each slot holds a small list (a “chain”) of every entry that landed there. Insert appends to the chain; lookup walks the chain comparing keys. Java’s HashMap and Go’s maps work this way.

Open addressing. There are no lists: the array itself holds the entries. If the slot is taken, try another slot by a fixed rule and keep going until you find the key or an empty slot. The simplest rule is linear probing: try the next slot, then the next. Python’s dict and set use open addressing, with a cleverer rule we’ll see in Advanced.

Notice what probing did to elk: it got pushed into slot 7, and it had to step past cat, which had nothing to do with slot 4. Keys that collide form a cluster, and clusters attract more collisions. That’s linear probing’s weakness. Its strength is that one flat array is very friendly to the CPU cache: the next slot is usually already in memory.

Build one yourself

The best way to own this is to write it. Here’s a complete hash map with separate chaining, in about forty lines. It uses Python’s built-in hash() for step 1 and grows when it gets crowded (the _resize part is explained in Advanced).

class ChainedHashMap:
    """A hash map that keeps colliding keys in a list per bucket (separate chaining)."""

    def __init__(self, capacity=8, max_load=0.75):
        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 put(self, key, value):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:                  # key already here: overwrite
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size / len(self.buckets) > self.max_load:
            self._resize(len(self.buckets) * 2)

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

    def remove(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

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

m = ChainedHashMap()
for i, word in enumerate(["cat", "dog", "owl", "fox", "elk", "bee", "ant"]):
    m.put(word, i)
print(m.get("fox"), m.get("yak"), m.size, len(m.buckets))
m.put("fox", 99)
m.remove("cat")
print(m.get("fox"), m.get("cat"), m.size)
# 3 None 7 16
# 99 None 6

Notice that get compares keys with == after finding the bucket. The hash only narrows the search to one bucket. Two different keys can share a hash, so the final word always belongs to equality.

Now play with one. The demo below uses the toy_hash recipe from above, so you can check its arithmetic by hand:

Things to try: press “Add a colliding key” a few times in chaining mode and watch one chain grow. Insert until the load factor passes 0.75 and watch every key move. Switch to linear probing, delete a key from the middle of a cluster, and then look up a key that sat after it.

Why it’s O(1) on average, and when it isn’t

“O(1)” means the cost doesn’t grow with the number of items. Here’s the reasoning for a hash map, without hand-waving.

Call the number of keys n and the number of slots m. The ratio α = n / m is the load factor: how full the table is on average. If the hash function spreads keys evenly, each chain has about α entries. A lookup does one hash, jumps to a slot, and walks one chain. A successful lookup walks about half a chain plus one; an unsuccessful lookup walks the whole chain. So the cost is about 1 + α.

The trick is that hash maps never let α get big. When α passes a threshold (0.75 in Java, about two-thirds in CPython), they double the array, which halves α. Since α stays below a fixed number, 1 + α stays below a fixed number, no matter whether you have a hundred keys or a hundred million. That’s O(1).

Now the worst case. If every key lands in the same slot, one chain holds all n keys and every lookup walks it: O(n), no better than a list. That happens with a broken hash function, or with an attacker choosing keys on purpose. Remember “Aa” and “BB”.

What can be a key

Not everything can be a key. A key’s hash must not change while it’s stored, because the table filed it under that hash. If it changed, the entry would sit in a slot nobody looks in.

That’s why Python refuses mutable built-ins as keys:

location = {(3, 4): "warehouse", (0, 0): "office"}   # tuples are fine as keys
print(location[(3, 4)])

try:
    {[3, 4]: "warehouse"}
except TypeError as e:
    print("TypeError:", e)

tags = frozenset({"vip", "late"})
print({tags: "follow up"}[frozenset({"late", "vip"})])
# warehouse
# TypeError: unhashable type: 'list'
# follow up

A list can be changed after you store it, so it has no hash. A tuple can’t be changed, so it can be a key. Same for frozenset versus set. The rule of thumb: use immutable things as keys: strings, numbers, tuples of those, frozen dataclasses. When you need a composite key, like “this user on this date”, use a tuple: visits[(user_id, day)].

Patterns that come up again and again

Nearly every hash map problem is one of a handful of moves: remember what you’ve seen, count, group by a computed key, or look up a complement. These five exercises cover them. Try each before opening the solution.

def two_sum_slow(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

print(two_sum_slow([2, 7, 11, 15], 9))
# [0, 1]

def two_sum(nums, target):
    index_of = {}                       # value -> index where we saw it
    for i, n in enumerate(nums):
        need = target - n
        if need in index_of:            # have we already seen the partner?
            return [index_of[need], i]
        index_of[n] = i
    return None

print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 2, 4], 6))
print(two_sum([3, 3], 6))
print(two_sum([1, 2], 7))
# [0, 1]
# [1, 2]
# [0, 1]
# None

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = [0] * 26                  # letter counts: same for every anagram
        for ch in w:
            key[ord(ch) - ord("a")] += 1
        groups[tuple(key)].append(w)    # lists can't be keys, tuples can
    return list(groups.values())

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

def subarray_sum(nums, k):
    count = 0
    running = 0
    seen = {0: 1}                       # prefix sum -> how many times we've had it
    for n in nums:
        running += n
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

print(subarray_sum([1, 1, 1], 2))
print(subarray_sum([1, 2, 3], 3))
print(subarray_sum([3, 4, 7, 2, -3, 1, 4, 2], 7))
# 2
# 2
# 4

def longest_consecutive(nums):
    present = set(nums)
    best = 0
    for n in present:
        if n - 1 in present:            # not the start of a run: skip it
            continue
        length = 1
        while n + length in present:
            length += 1
        best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))
print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]))
print(longest_consecutive([]))
# 4
# 9
# 0

from collections import Counter

def first_unique(s):
    counts = Counter(s)                 # pass 1: count every character
    for i, ch in enumerate(s):          # pass 2: first one seen exactly once
        if counts[ch] == 1:
            return i
    return -1

print(first_unique("leetcode"), first_unique("loveleetcode"), first_unique("aabb"))
# 0 2 -1

Advanced: the costs tutorials skip

Average O(1) is true, but it’s hiding three costs: growing the table, deleting from it, and the memory it eats. And every language makes different choices about them.

Load factor and resizing

As keys arrive, the load factor climbs and chains (or probe sequences) get longer. At a threshold the table resizes: it allocates an array twice as big and re-inserts every key. Every key has to be re-placed, because its slot was hash % 8 and is now hash % 16, a different number for about half the keys.

Most implementations keep the capacity a power of two. Then hash % capacity is the same as hash & (capacity - 1), a single bitwise AND instead of a division, and after doubling, each key either stays in its slot or moves up by exactly the old capacity. You can see that in the diagram: cod moves from 0 to 8, dog from 4 to 12, fox from 7 to 15, and the rest stay.

Why resizing is still O(1): amortized cost

Resizing a table of a million keys copies a million keys. How can insert be O(1) if some inserts cost a million steps?

Because those expensive inserts are rare, and they get rarer as the table grows. Doubling at sizes 8, 16, 32, … means the copies cost 6 + 12 + 24 + … and every term is half the next one. A sum like that is always less than twice its last term, and the last term is less than n. So n inserts cost fewer than n + 2n steps in total: a constant number of steps per insert, on average over the whole sequence. That’s what amortized O(1) means.

You don’t have to take the algebra on trust. Count it:

def count_work(n, grow=2, start=8, max_load=0.75):
    capacity, size, copies = start, 0, 0
    for _ in range(n):
        if (size + 1) / capacity > max_load:
            copies += size          # re-insert every existing key
            capacity *= grow
        size += 1
    return copies, capacity

for n in (1_000, 1_000_000):
    copies, cap = count_work(n)
    print(f"{n:>9,} inserts: {copies:>9,} extra copies, {(n + copies) / n:.2f} steps per insert, final capacity {cap:,}")
#     1,000 inserts:     1,530 extra copies, 2.53 steps per insert, final capacity 2,048
# 1,000,000 inserts: 1,572,858 extra copies, 2.57 steps per insert, final capacity 2,097,152

A thousand times more inserts, and the work per insert barely moves. Growing by a fixed amount instead of a fixed factor (say, 1,000 slots at a time) breaks this: the copies become 1,000 + 2,000 + 3,000 + …, which grows with n², and insert stops being O(1).

Amortized isn’t the same as “every insert is fast”, though. The insert that triggers the resize really does take a million steps, all at once. For most code that’s invisible. For a latency-sensitive server holding a huge table, it’s a pause. Redis avoids it with incremental rehashing: during a resize it keeps both the old and new tables and moves a few buckets on every operation, so no single request pays for the whole move. Go’s maps grew incrementally in the same spirit.

Deleting under open addressing: tombstones

With chaining, delete is easy: remove the entry from its chain. With open addressing it’s a trap. A lookup stops at the first empty slot, because “empty” means “the key would have been here”. If you delete by emptying a slot in the middle of a probe sequence, you cut the sequence, and keys after the hole become invisible.

EMPTY, TOMBSTONE = object(), object()

class ProbingSet:
    """Open addressing with linear probing: one array, no lists."""

    def __init__(self, capacity=8):
        self.slots = [EMPTY] * capacity

    def _probe(self, key):
        i = hash(key) % len(self.slots)
        while True:                     # the table is never full in this demo
            yield i
            i = (i + 1) % len(self.slots)

    def add(self, key):
        reuse = None
        for i in self._probe(key):
            slot = self.slots[i]
            if slot is EMPTY:
                self.slots[reuse if reuse is not None else i] = key
                return
            if slot is TOMBSTONE:
                reuse = i if reuse is None else reuse   # remember the first grave
            elif slot == key:
                return                                    # already present

    def __contains__(self, key):
        for i in self._probe(key):
            slot = self.slots[i]
            if slot is EMPTY:
                return False            # a true gap ends the search
            if slot is not TOMBSTONE and slot == key:
                return True

    def remove_wrong(self, key):
        for i in self._probe(key):
            if self.slots[i] == key:
                self.slots[i] = EMPTY   # punches a hole in the probe chain
                return

    def remove(self, key):
        for i in self._probe(key):
            if self.slots[i] is EMPTY:
                return
            if self.slots[i] == key:
                self.slots[i] = TOMBSTONE   # "something was here, keep looking"
                return

# 1, 9 and 17 all land on slot 1 in an 8-slot table (hash(n) == n for small ints).
s = ProbingSet()
for n in (1, 9, 17):
    s.add(n)
s.remove_wrong(9)
print("wrong delete, is 17 still there?", 17 in s)

s = ProbingSet()
for n in (1, 9, 17):
    s.add(n)
s.remove(9)
print("tombstone delete, is 17 still there?", 17 in s)
# wrong delete, is 17 still there? False
# tombstone delete, is 17 still there? True

The fix is a tombstone: a marker that says “something used to be here, keep searching”. Lookups walk past tombstones; inserts may reuse them. The catch is that tombstones still make searches longer, so they count toward the load factor, and a table with lots of deletes slowly fills with graves until a resize clears them. CPython’s dict does exactly this; its tombstones are called “dummy” entries. You can watch it in the demo above: switch to linear probing, delete a key, and the † stays until the next resize.

Inside CPython’s dict

Python’s dict is one of the most heavily tuned hash tables in common use, and knowing its layout explains several behaviors that otherwise look like magic.

Since Python 3.6 the dict is compact: instead of one big array of (hash, key, value) slots, it keeps two arrays. A small, sparse indices array holds positions, and a dense entries array holds the actual (hash, key, value) triples, appended in insertion order.

Three consequences fall out of that layout:

1. Insertion order is free. Iterating a dict walks the dense entries array, which is in insertion order. It started as an implementation detail in 3.6 and became a language guarantee in 3.7.
2. Less memory. Empty slots cost only one small index (1 byte each while the table has fewer than 256 slots, growing to 2, 4 or 8 bytes for larger tables) instead of a whole 24-byte triple.
3. Faster iteration. Walking a dense array touches no empty slots.

CPython keeps the table at most about two-thirds full. You can watch it grow with sys.getsizeof (Python 3.13 on my machine):

import sys
d = {}; last = sys.getsizeof(d)
for i in range(1, 100):
    d[i] = i
    if sys.getsizeof(d) != last:
        last = sys.getsizeof(d)
        print(f"after {i} keys -> {last} bytes")
# after 1 keys -> 224 bytes
# after 6 keys -> 352 bytes
# after 11 keys -> 632 bytes
# after 22 keys -> 1168 bytes
# after 43 keys -> 2264 bytes
# after 86 keys -> 4688 bytes

An 8-slot table holds 5 keys, so the 6th triggers a resize; 16 slots hold 10, so the 11th does; then 21, 42, 85. Two-thirds every time.

For collisions, CPython doesn’t use plain linear probing. Small integers hash to themselves, so keys like 1, 2, 3, … would sit in neighboring slots, and linear probing would turn them into one long cluster. Instead it mixes in the higher bits of the hash as it probes:

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

Early probes are steered by bits of the hash that & mask threw away, so keys that collided on the low bits quickly diverge. Once perturb reaches zero, i*5 + 1 alone still visits every slot of a power-of-two table, so the search always terminates.

A few behaviors that follow from how Python hashes, all verified on 3.13:

print(hash(1), hash(1.0), hash(True))        # equal values must hash equally
d = {1: "int", True: "bool", 1.0: "float"}
print(d)                                      # one key: they're all "equal"

print(hash(-1), hash(-2))                     # -1 is reserved as an error code in C

d = {}
d["b"] = 1; d["a"] = 2; d["c"] = 3
print(list(d))                                # insertion order, guaranteed since 3.7
# 1 1 1
# {1: 'float'}
# -2 -2
# ['b', 'a', 'c']

1, 1.0 and True compare equal, so they must hash equal, so they’re the same key: the dict keeps the first key object and the last value. And hash(-1) is -2 because CPython’s C functions return -1 to signal an error, so no real hash is allowed to be -1.

Sets aren’t dicts

Python’s set has its own implementation. It has no values and doesn’t remember order, and it’s tuned differently: it probes a run of neighboring slots linearly before jumping (cheap, because neighbors share a cache line), and it resizes at about 60% full, growing four times larger while small. That’s why a set of a million integers is a little smaller than a dict of the same keys, and why you should never rely on a set’s iteration order: it can change between runs and versions.

Java and Go make different choices

Java’s HashMap uses separate chaining over a power-of-two array (default capacity 16, load factor 0.75). Because hash & (capacity - 1) only looks at the low bits, it first mixes the high bits down with h ^ (h >>> 16). Its most interesting feature is a defense: since Java 8, when one bucket’s chain reaches 8 entries (and the table has at least 64 slots), the chain is converted into a balanced red-black tree. The worst case for that bucket drops from O(n) to O(log n). It shrinks back to a list at 6, so it doesn’t flip back and forth at the boundary.

Go’s maps were, until Go 1.24, arrays of buckets that each held 8 entries plus 8 one-byte “tophash” values (the top bits of each key’s hash), with overflow buckets chained on when full, and growth spread across later operations. Go also randomizes iteration order on purpose, so nobody can accidentally depend on it. Go 1.24 replaced the implementation with Swiss tables, which are in the Expert section.

The hash and equality contract

When you put your own objects in a dict or set, you’re promising two things:

1. If a == b, then hash(a) == hash(b). Equal keys must land in the same slot, or the table looks in the wrong place.
2. The hash doesn’t change while the object is a key.

Python enforces part of this for you: define __eq__ without __hash__ and your class becomes unhashable. Break rule 2 and you get the nastiest kind of bug, an entry that’s still in the dict but can’t be found by any key:

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)

try:
    {Point(1, 2): "home"}
except TypeError as e:
    print("TypeError:", e)       # defining __eq__ removes the default __hash__

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

p = MutablePoint(1, 2)
places = {p: "home"}
p.x = 5                          # mutate the key after storing it
print(p in places)               # looks in the bucket for (5, 2): not there
print(MutablePoint(1, 2) in places)   # right bucket, but the stored key now equals (5, 2)
print(len(places), "entry still in the dict, unreachable by any key")
# TypeError: unhashable type: 'Point'
# False
# False
# 1 entry still in the dict, unreachable by any key

The stored entry was filed under the hash of (1, 2). After the mutation, looking up p hashes (5, 2) and searches the wrong slot. Looking up a fresh (1, 2) searches the right slot but finds a key that now equals (5, 2). The fix is to make keys immutable. A frozen dataclass gets a correct __eq__ and __hash__ and refuses mutation:

from dataclasses import dataclass

@dataclass(frozen=True)          # frozen: fields can't change, so the hash can't drift
class Point:
    x: int
    y: int

places = {Point(1, 2): "home"}
print(places[Point(1, 2)])
try:
    Point(1, 2).x = 5
except Exception as e:
    print(type(e).__name__)
# home
# FrozenInstanceError

cache = {}
def report(filters):            # filters is a dict like {"country": "MY", "year": 2026}
    key = str(filters)
    if key not in cache:
        cache[key] = build_report(filters)
    return cache[key]

key = tuple(sorted(filters.items()))   # order-independent and hashable

import sys
n = 1_000_000
print('list', sys.getsizeof(list(range(n))), 'set', sys.getsizeof(set(range(n))), 'dict', sys.getsizeof(dict.fromkeys(range(n))))
# list 8000056 set 33554648 dict 41943128

Expert: attacks, modern designs and concurrency

At this level the questions change. Not “how does it work” but “what happens when someone hostile picks the keys”, “why are the fastest tables built the way they are”, and “what breaks when many threads share one”.

Hash flooding: turning O(1) into a denial of service

In December 2011, at the 28th Chaos Communication Congress (28C3), Alexander Klink and Julian Wälde showed that the hash tables inside PHP, Java, Python, Ruby and ASP.NET could be attacked with nothing but a crafted HTTP request. Web frameworks parse form fields and JSON into hash maps automatically. If the attacker picks field names that all collide, every insert walks an ever-longer chain, and building the table costs O(n²). A single request of a couple of megabytes could keep a server core busy for minutes. The underlying idea had been published by Crosby and Wallach in 2003; 28C3 showed how widely it still worked.

The Java version is beautiful. “Aa” and “BB” have the same String.hashCode (2112). And because the hash is computed left to right, any string built from those two blocks collides with any other string of the same length built from them: “AaAa”, “AaBB”, “BBAa” and “BBBB” all share one hash. With six blocks you get 2⁶ = 64 colliding keys; with sixteen, 65,536. Try it:

You don’t need Java to see the cost. In Python, give every key the same hash and time the inserts:

import time

class Evil:
    """Every instance has the same hash, like keys an attacker crafted to collide."""
    def __init__(self, n):
        self.n = n
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return self.n == other.n

for n in (1_000, 2_000, 4_000):
    start = time.perf_counter()
    d = {i: None for i in range(n)}
    normal = time.perf_counter() - start

    start = time.perf_counter()
    d = {Evil(i): None for i in range(n)}
    evil = time.perf_counter() - start
    print(f"{n:>5} keys: normal {normal * 1000:6.2f} ms   colliding {evil * 1000:8.1f} ms")
#  1000 keys: normal   0.04 ms   colliding     21.5 ms
#  2000 keys: normal   0.10 ms   colliding     86.6 ms
#  4000 keys: normal   0.19 ms   colliding    381.8 ms

Double the keys and the colliding version takes about four times as long: the n² signature. At 4,000 keys it’s already 2,000 times slower than normal.

The defenses came in layers:

• Keyed hashing. If the hash mixes in a secret random number chosen when the process starts, an attacker can’t predict which keys collide. The standard choice became SipHash, designed by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012 to be fast on short inputs and hard to collide without the key. Python randomized string hashing by default from 3.3, adopted SipHash in 3.4 (PEP 456), and uses the faster SipHash-1-3 variant today: sys.hash_info.algorithm reports siphash13 on 3.13. Rust’s default HashMap hasher is SipHash-1-3 for the same reason.
• Bounding the worst case. Java’s treeified buckets (Advanced) cap a flooded bucket at O(log n).
• Bounding the input. PHP added max_input_vars (default 1,000 form fields); servers like Tomcat cap parameter counts.

You can see Python’s randomization from the shell. Each process gets a new secret, unless you pin it with PYTHONHASHSEED:

$ python3 -c "print(hash('cat'))"
5265544399956307645
$ python3 -c "print(hash('cat'))"
8365802510015252210
$ PYTHONHASHSEED=0 python3 -c "print(hash('cat'))"
692052486964499043
$ PYTHONHASHSEED=0 python3 -c "print(hash('cat'))"
692052486964499043

That’s also why you must never persist hash() of a string, or use it to pick a shard: it changes every time the process restarts. Use a stable hash like hashlib.sha256 or zlib.crc32 when a hash has to mean the same thing tomorrow.

Robin Hood hashing: take from the rich

Linear probing’s problem is variance: most keys sit in their home slot, a few are pushed far away, and lookups for those are slow. Robin Hood hashing (Pedro Celis, 1986) evens that out. Every entry remembers how far it is from its home slot, its probe distance. When inserting, if you meet an entry that’s closer to home than you are, you take its slot and carry it onward instead. Rich entries (close to home) give up their place to poor ones (far from home).

The effect is that probe distances become nearly uniform, so the worst lookup is much closer to the average. It also enables an early exit on misses: if you’ve probed further than the entry you’re looking at is from its home, your key can’t be further along. And deletion doesn’t need tombstones: you remove the entry and shift the following entries back one slot until you hit one that’s already home (backward-shift deletion). Rust’s standard HashMap used Robin Hood hashing until version 1.36 in 2019.

Swiss tables: let the CPU do sixteen probes at once

The modern answer to “what’s the fastest general-purpose hash table” is the Swiss table, presented by Google engineers at CppCon 2017 and shipped as Abseil’s flat_hash_map. Rust’s standard HashMap switched to it (through the hashbrown crate) in 1.36, and Go’s maps moved to it in Go 1.24.

The insight is that on modern hardware, the expensive part of a lookup isn’t arithmetic; it’s cache misses from touching key memory. So a Swiss table keeps a separate array of one-byte control bytes, one per slot. The hash is split in two: most of the bits (H1) choose a group of 16 slots, and the remaining 7 bits (H2) are stored in the slot’s control byte. A control byte is either “empty”, “deleted” or “full, and here are 7 bits of my hash”.

A lookup loads the 16 control bytes of a group into one SIMD register and compares all of them against H2 with a single instruction. Out comes a bitmask of candidate slots, usually zero or one of them, and only those keys are actually compared. A miss usually touches no key memory at all: the group contains an “empty” byte and no H2 match, and the search is done. It’s open addressing, but probing 16 slots per step for the price of one.

Cuckoo hashing: a guaranteed two-slot lookup

Cuckoo hashing (Rasmus Pagh and Flemming Friche Rodler, 2001) gives every key exactly two possible homes, from two different hash functions, often in two separate tables. A lookup checks those two slots and nothing else: worst-case O(1), not just average. Insert puts the key in one of its homes; if that’s taken, it evicts the occupant (like a cuckoo chick pushing out an egg), which moves to its other home, possibly evicting someone else. If evictions go round in a cycle, the table rehashes with new functions. The price is a lower usable load (around 50% for two tables with one slot each, much higher with small buckets) and expensive, occasionally failing inserts. It shines where reads dominate and worst-case lookup time matters, and its fingerprint variant, the cuckoo filter, competes with Bloom filters.

Concurrency: what breaks when threads share a table

A hash table is a pile of invariants (counts, chains, the resize in progress) and concurrent writers can corrupt any of them. Java’s plain HashMap is famous for this: before Java 8, two threads resizing at once could turn a chain into a cycle, and a later get would loop forever at 100% CPU.

Java’s ConcurrentHashMap is the classic design for doing it properly. Java 7 used lock striping: the table was split into 16 segments, each with its own lock, so threads writing different segments didn’t block each other. Java 8 went finer: an insert into an empty bin uses a lock-free compare-and-swap, an insert into an occupied bin locks only that bin’s first node, reads take no lock at all, and the size is kept in a set of counters that threads update without contending. Resizing is done cooperatively, with threads helping move bins.

Python has a different story. In CPython with the GIL, a single dict operation like d[k] = v or d.get(k) happens atomically, so the dict itself can’t be corrupted. But counts[word] += 1 is three operations, read, add and write, and another thread can run between them and lose an update. Free-threaded CPython (3.13+, PEP 703) protects dicts with per-object locks internally, which keeps the dict consistent but still doesn’t make your compound operations atomic. Either way, guard read-modify-write with a lock:

import threading
from collections import defaultdict

counts = defaultdict(int)
lock = threading.Lock()

def record(word, times):
    for _ in range(times):
        with lock:                     # read-add-write as one step
            counts[word] += 1

threads = [threading.Thread(target=record, args=("hit", 100_000)) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print(counts["hit"])
# 400000

Across processes and servers there’s no shared memory at all, so the shared hash map moves out of the process: Redis is, at heart, a networked hash map with atomic operations like INCR, HINCRBY and SET key value NX. You’ll see that in production below.

Memory: the price of speed

Every fast lookup above is paid for with spare slots and stored hashes. Measured on Python 3.13, a set of 100,000 short strings costs about 4 MiB for the table plus another 5 MiB for the string objects. A list of the same strings needs under 1 MiB for its pointers. When the set doesn’t fit (in a cache, in RAM, in every server), you trade exactness or speed for space. The next two structures are both built from hash functions, and both show up constantly in system design.

Structures built on hash maps

LRU cache. A cache with a size limit needs to evict the least recently used entry, and both “find entry” and “mark as recently used” have to be O(1). A hash map alone can find but doesn’t track order; a linked list tracks order but can’t find. Together they do both: the map points from key to a node in a doubly linked list ordered by recency.

Python’s OrderedDict is exactly that pairing (and functools.lru_cache is implemented the same way in C), so an LRU cache is a few lines:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = OrderedDict()            # a dict plus a doubly linked list

    def get(self, key):
        if key not in self.items:
            return None
        self.items.move_to_end(key)           # O(1): unlink and relink at the end
        return self.items[key]

    def put(self, key, value):
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            self.items.popitem(last=False)    # O(1): drop the least recently used

cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2)
cache.get("a")                                # "a" is now the most recent
cache.put("c", 3)                             # evicts "b"
print(list(cache.items))
# ['a', 'c']

Bloom filter. Sometimes you only need “definitely not seen” or “probably seen”, for example “has this user possibly visited this URL before?” A Bloom filter answers that in a tiny fraction of a set’s memory. It’s an array of m bits and k hash functions. Adding an item sets the k bits its hashes point to; checking an item looks at those k bits. If any is 0, the item was never added. If all are 1, it probably was, but other items might have set those bits: a false positive. It never gives false negatives. The standard sizing formulas say about 9.6 bits per item buys a 1% false-positive rate, with 7 hash functions:

import hashlib, math

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

    def _positions(self, item):
        digest = hashlib.sha256(item.encode()).digest()
        h1 = int.from_bytes(digest[:8], "big")
        h2 = int.from_bytes(digest[8:16], "big")
        return [(h1 + i * h2) % self.m for i in range(self.k)]   # double hashing

    def add(self, item):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def __contains__(self, item):
        return all(self.bits[p // 8] & (1 << (p % 8)) for p in self._positions(item))

bf = BloomFilter(expected=100_000, fp_rate=0.01)
for i in range(100_000):
    bf.add(f"user-{i}")
print(bf.m, "bits =", bf.m // 8 // 1024, "KiB,", bf.k, "hash functions")
print("user-42" in bf)
false_hits = sum(f"stranger-{i}" in bf for i in range(100_000))
print(f"false positive rate: {false_hits / 100_000:.2%}")
# 958506 bits = 117 KiB, 7 hash functions
# True
# false positive rate: 1.03%

117 KiB instead of about 9 MiB for the set of the same 100,000 strings, at the cost of being wrong 1% of the time, and only in one direction. The two-hash trick in _positions (Kirsch and Mitzenmacher’s double hashing) gets k positions out of one digest. Databases use Bloom filters to skip disk reads for keys that aren’t in a file, and CDNs to avoid caching one-hit wonders.

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value, self.prev, self.next = key, value, None, None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.nodes = {}                          # key -> Node
        self.head, self.tail = Node(), Node()    # sentinels: no empty-list special cases
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)                   # now the most recently used
        return node.value

    def put(self, key, value):
        if key in self.nodes:
            self._unlink(self.nodes[key])
        node = Node(key, value)
        self.nodes[key] = node
        self._push_front(node)
        if len(self.nodes) > self.capacity:
            lru = self.tail.prev                 # least recently used
            self._unlink(lru)
            del self.nodes[lru.key]

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
print(c.get(1))      # 1, and key 1 becomes most recent
c.put(3, 3)          # evicts key 2
print(c.get(2))      # -1
c.put(4, 4)          # evicts key 1
print(c.get(1), c.get(3), c.get(4))
# 1
# -1
# -1 3 4

In production: hash maps in a multi-tenant backend

I’m the primary engineer of ezychat.io, a multi-tenant platform where AI answers customers on WhatsApp, Instagram, Messenger and web chat. It’s Python (FastAPI and Celery), PostgreSQL and Redis. Hash maps are everywhere in it, but a few uses carry real design decisions, and each maps back to a level above. These are trimmed excerpts from the codebase.

Load once, index by ID, diff with sets

When a user schedules a social post to several accounts, the API receives a list of account IDs. The naive version queries each account in a loop: one database round trip per ID. Instead, the code loads them all in one query, indexes them in a dictionary, and uses a set difference to find any IDs that didn’t come back:

async def _load_org_accounts_by_id(session, org_id, account_ids):
    if not account_ids:
        return {}
    unique_ids = set(account_ids)
    rows = (await session.execute(
        select(SocialAccount).where(
            SocialAccount.org_id == org_id, SocialAccount.id.in_(unique_ids)
        )
    )).scalars().all()
    found = {row.id: row for row in rows}
    missing = unique_ids - found.keys()
    if missing:
        raise HTTPException(422, {"error_code": "unknown_target_account", ...})
    return found

Three hash structures in eight lines. set(account_ids) drops duplicates before they reach the database. {row.id: row} turns the result into O(1) lookups for the rest of the request. And unique_ids - found.keys() (dict key views support set operations) answers “which IDs were bad?” in one expression. The security detail is the org_id filter: an account belonging to another tenant simply isn’t returned, so it shows up in missing and the request is rejected, without ever revealing that the account exists.

A dictionary keyed by event loop

Python’s async Redis client has a subtle rule: a connection belongs to the event loop that opened it. The API runs on one long-lived loop, but Celery task bodies each run their own short-lived loop. A single process-wide client, created on one loop, silently breaks on the next one, and because the Redis paths are written to fail open (a cache miss rather than an error), nothing visibly fails; caches and the circuit breaker just stop working.

The fix is a hash map whose keys are event loop objects:

# One client per event loop: an async Redis connection belongs to the loop
# that opened it, and Celery task bodies each run on their own short-lived loop.
_redis_by_loop: "WeakKeyDictionary[asyncio.AbstractEventLoop, Redis]" = WeakKeyDictionary()

def get_redis() -> Redis:
    loop = asyncio.get_running_loop()
    client = _redis_by_loop.get(loop)
    if client is None:
        client = _new_client()
        _redis_by_loop[loop] = client
    return client

Two hash-map ideas meet here. An event loop has no meaningful value equality, so it’s hashed by identity: each loop object is its own key. And WeakKeyDictionary holds its keys weakly. When a task’s throwaway loop is garbage collected, its entry disappears instead of keeping a dead loop and its client alive forever. An ordinary dict here would be a slow memory leak.

Tuples as composite keys

Publishing validation collects issues from several checks, which can repeat. Deduplicating them uses exactly the Intermediate rule about composite keys:

def _dedupe(issues):
    seen: set[tuple[str, str, str]] = set()
    result = []
    for issue in issues:
        key = (issue.code, issue.message, issue.severity)
        if key in seen:
            continue
        seen.add(key)
        result.append(issue)
    return result

The Issue objects themselves aren’t used as keys; a tuple of the fields that define “the same issue” is. Choosing those fields is the design: add severity to the key and a warning and an error with the same message both survive.

Redis: one hash map shared by every server

The API runs as several containers, so per-process dictionaries can’t hold anything that must be shared, like rate-limit counters. Those live in Redis, which is a hash map reachable over the network. The rate limiter’s keys show how much design lives in a key:

current_key = f"rl:{bucket}:{identity}:{window}"
previous_key = f"rl:{bucket}:{identity}:{window - 1}"

bucket names the limit (login attempts, API calls per organization), identity is who’s being counted (an IP address, a user ID, an organization ID) and window is the time slot. Every server computes the same key for the same caller in the same minute, so they all increment the same counter. The full algorithm, a sliding-window estimate computed atomically inside Redis, is in the rate limiter article.

“Send once” latches, and what belongs in the key

SET key value NX sets a key only if it doesn’t exist and reports whether it did: a distributed if key not in seen: seen.add(key) in one atomic step. ezychat uses it as a latch for “do this at most once”. The billing worker notifies an organization when it reaches its plan’s limit of monthly active customers, and the latch stops the same notice going out again on every run:

# The limit is part of the latch, not just the period. Keyed on the period
# alone, an org that hit 200, bought an MAC pack, and then hit the new 250
# in the same period would get silence: the latch was already set, so the
# second time they lost auto-replies nobody would be told.
if not redis.set(
    f"usagelimit:{org_id}:{period_key}:mac:{limit}", 1, nx=True, ex=metering.KEY_TTL_SECONDS
):
    return None

The comment is the lesson. The first version keyed the latch on the organization and the billing period. That’s “notify once per period”, which sounds right until a customer raises their limit mid-period: the second time they hit it, the latch was already set, and they lost auto-replies with nobody told. Adding the limit to the key changes the meaning to “notify once per period per ceiling”. What you put in a key decides what counts as the same thing. That’s the hash contract from Advanced, applied to business logic. The ex= expiry matters too: the latch cleans itself up instead of growing forever.

The database is a set too

The same “have I seen this?” question appears at the storage layer. Messaging providers retry webhooks, so the same inbound message can arrive twice. Each message has the provider’s own ID, and the insert is deduplicated on (org_id, channel_msg_id):

stmt = (
    pg_insert(Message)
    .values(org_id=org_id, channel_msg_id=channel_msg_id, ...)
    .on_conflict_do_nothing(
        index_elements=["org_id", "channel_msg_id"],
        index_where=Message.channel_msg_id.isnot(None),
    )
    .returning(Message.id)
)

A unique index plus ON CONFLICT DO NOTHING is set membership that survives restarts: a retried delivery returns no new row, and the pipeline stops there. (PostgreSQL’s unique indexes are B-trees, not hash tables, but the semantics are the set’s: one entry per key.) The key again carries the design: including org_id means two tenants can never collide, even if two providers happened to issue the same message ID.

What production adds to the textbook

• The key is the design. In every example above, the interesting decision was what goes into the key: which tenant, which window, which ceiling, which fields.
• Shared state moves out of the process. A dict is per process. Anything several servers must agree on (counters, latches, dedupe) needs Redis or the database, with an atomic operation, not a read-then-write.
• Give entries a lifetime. Weak keys, expiries and unique indexes all answer “when does this entry go away?” A hash map that only grows is a memory leak with good performance.
• Batch, then index. Loading many rows in one query and building a dict beats N lookups every time it’s possible.

Cheat sheet