Hash Tables & Dictionaries — the most-used structure

A hash table turns linear O(n) searches into direct O(1) lookups on average. It is the quiet “engine” behind almost every piece of software — from databases and caches to the dict variable you reach for every day.

Core idea

A hash table stores data as key–value pairs, e.g. "Alice" → 25. Its heart is a hash function that takes a key and computes a bucket index into a backing array.

A hash function is like a filing clerk: hand it a name and it instantly tells you which drawer the document is in — no need to open every drawer.

The set and get steps:

1. Compute index = hash(key) % array_size
2. Jump straight to that bucket and store or read the value

Because jumping to a computed bucket takes constant time, get and set are O(1) on average — no matter whether you hold ten items or ten million.

Anatomy of a hash function

A hash function must satisfy three properties:

1. Deterministic — the same key always produces the same hash (within one run of the program).
2. Fast to compute — O(1) relative to key size, otherwise the whole point is lost.
3. Uniform — it should spread keys evenly across buckets, so no bucket gets far more than its share.

A bad hash function still “works” (it always returns some integer), but a bad one clusters keys together and quietly turns your O(1) table into an O(n) linked list. This is why production languages don’t let you casually write your own string hash — Python’s hash() for strings uses SipHash, a cryptographically-informed mixing function, precisely to avoid clustering.

hash(key) % table_size is only as good as hash(). The modulo is the easy part; a good hash() is the hard part.

Worked example 1 — tracing hash → bucket by hand

To see collisions form, let’s use a deliberately weak toy hash function so the arithmetic is easy: h(s) = sum(ord(c) for c in s). Table size = 8.

key	sum of char codes	% 8	bucket
"cat"	312	0	0
"dog"	314	2	2
"bird"	417	1	1
"fish"	426	2	2 ← collides with "dog"
"lion"	434	2	2 ← collides with "dog", "fish"

Resulting table (chaining):

bucket 0: [ ("cat", ...) ]
bucket 1: [ ("bird", ...) ]
bucket 2: [ ("dog", ...) ] -> [ ("fish", ...) ] -> [ ("lion", ...) ]
bucket 3..7: [ ]

Notice bucket 2 now holds three entries — a lookup for "lion" must walk past "dog" and "fish" first. That’s the cost of a weak hash function: summing characters ignores their order and position, so many different words land on nearby sums. A real hash function (SipHash, MurmurHash, FNV) mixes bits with multiplication and shifts specifically to avoid this kind of clustering. The lesson: never invent your own hash function for production code — use the language’s built-in one.

Collision resolution: chaining vs. open addressing

A hash function squeezes a huge space of keys into a limited number of indices, so collisions are mathematically guaranteed once you have enough keys (this is the same math behind the “birthday paradox” — collisions appear far sooner than intuition suggests). There are two standard strategies for handling them.

Chaining — each bucket holds a small list (or linked list) of the pairs that landed there. On lookup you only scan that one short list. This is what Worked Example 1 above shows.

Open addressing — there are no lists at all. If a bucket is taken, you probe forward (by a fixed rule) to find the next empty slot, and store the value there instead.

Worked example 2 — open addressing with linear probing

Table size = 8, hash is the identity function (h(k) = k), probing rule: “if the slot is taken, try the next slot” (linear probing). Insert 3, 11, 19, 8 in that order:

insert	h(k) % 8	slot tried	result
3	3	3 (empty)	placed at index 3
11	3	3 (taken by 3) → probe 4 (empty)	placed at index 4
19	3	3 (taken) → 4 (taken) → probe 5 (empty)	placed at index 5
8	0	0 (empty)	placed at index 0

Final array: [8, _, _, 3, 11, 19, _, _]

Lookup for 19 has to redo the same probe sequence (3 → 4 → 5) to find it — that’s the cost open addressing pays for having no lists.

	Chaining	Open addressing
Extra memory per bucket	small list/pointer overhead	none — reuses the array
Load factor can exceed 1.0?	yes	no, must stay < 1.0
Cache locality	worse (linked structures scattered in memory)	better (contiguous array, cache-friendly)
Deletion	straightforward (remove from list)	tricky — needs a “tombstone” marker, not a true empty slot
Worst case	O(n) to walk one long chain	O(n) to probe the whole table

CPython’s actual dict and set use open addressing internally (with a pseudo-random probing sequence, not simple linear probing) — that’s part of why Python dicts are so cache-friendly and fast in practice.

Load factor and resizing (rehashing)

Load factor α = number of items ÷ number of buckets. It’s the single number that predicts how fast your hash table is right now.

• Low load factor (e.g., 0.25) → buckets mostly empty, chains almost always length 0 or 1 → fast, but wasting memory.
• High load factor (e.g., approaching 1.0 or above) → chains get long → lookups degrade toward O(n).

Most implementations trigger a resize once α crosses a threshold (commonly 0.66–0.75): allocate a bigger array (typically double the size) and rehash every existing key into the new array, since index = hash(key) % new_size gives different results at a different size.

Resizing is itself O(n) — but it happens rarely (only every ~doubling), so its cost, spread out (“amortized”) over all the inserts that led up to it, adds only O(1) on average per insert. This is the same amortized-analysis trick used for dynamic array (list) growth.

Worked example 3 — resizing in action

Table size = 4, identity hash, insert 1, 2, 3, 4:

insert	h(k) % 4	bucket
1	1	1
2	2	2
3	3	3
4	0	0

So far so good — 4 items, 4 buckets, α = 1.0, no collisions yet, but we’re in the danger zone. Insert 5:

5 % 4 = 1 → collides with key 1.

α is now 5/4 = 1.25, past the resize threshold → the table resizes to size 8 and every key is rehashed:

key	h(k) % 8	new bucket
1	1	1
2	2	2
3	3	3
4	4	4
5	5	5

All five keys now land in distinct buckets — the collision is gone, and α dropped to 5/8 = 0.625. This is why resizing “restores” O(1) performance: it isn’t magic, it’s literally giving the hash function more room to spread keys out.

Note: resizing helps only if the hash function mixes bits well to begin with. Go back to Worked Example 1 — a weak “sum of characters” hash tends to cluster the same keys together no matter how big the table gets, because the underlying sums stay close together regardless of the modulus. Resizing fixes load, not a bad hash function.

Why O(1) is average, not worst case

The O(1) claim rests on an assumption CLRS calls simple uniform hashing: every key is equally likely to hash to any bucket, independent of other keys. Under that assumption, with load factor α kept constant (via resizing), the expected number of keys examined per lookup is O(1 + α) = O(1).

But that’s an average over random inputs, not a guarantee for every possible input:

• Worst case is always O(n). If every key happens to hash to the same bucket, you’ve built an expensive linked list. This can’t be ruled out in the abstract — only made astronomically unlikely by a good hash function.
• Adversaries can break the assumption. If an attacker knows (or can guess) your hash function, they can craft input keys that all collide on purpose — a hash-flooding attack. Feeding such keys to a naive hash table turns an O(n) request handler into an O(n²) denial-of-service. This is a real, historical vulnerability class (multiple language runtimes, including early PHP, Java, and Python, were patched around 2011–2012 after this was published) — it’s why Python randomizes string hashing per process by default (PYTHONHASHSEED), so the same string hashes differently across runs and an attacker can’t precompute colliding keys offline.

“Average case O(1)” is a statement about typical inputs under a good hash function — not a law of physics. Judging whether it holds requires checking both conditions.

When hashing degrades to O(n)

Concretely, watch for these failure modes:

1. Weak or biased hash function — clusters keys regardless of table size (Worked Example 1).
2. Load factor allowed to grow unchecked — an implementation (or a custom one you wrote) that never resizes will see chains grow linearly with n.
3. Adversarial / attacker-controlled keys — hash-flooding, described above.
4. Broken __eq__/__hash__ contracts on custom objects — Python requires that if a == b then hash(a) == hash(b). If you override __eq__ on a class but forget __hash__, equal-looking objects can land in different buckets (or Python makes the class unhashable entirely, which is actually the safer failure).
5. Mutable keys — this is why Python won’t let you use a list as a dict key or set member: if you mutated it after insertion, its hash would change, and the table would look in the wrong bucket forever. Only immutable types (str, int, tuple of immutables, frozenset) are hashable by default.

Worked example 4 — an adversarial worst case

Suppose (hypothetically) a service hashes incoming request IDs with a broken function h(k) = len(k) % 8 — it only looks at string length, ignoring content entirely. An attacker sends IDs "aaaaaaaa", "bbbbbbbb", "cccccccc", … — all length 8 — and every single one hits the same bucket:

bucket 0 (len % 8 == 0): [aaaaaaaa] -> [bbbbbbbb] -> [cccccccc] -> ... (n items, one giant chain)

Every lookup now walks the entire chain: O(n) per request. A server that expected O(1) request routing has just been pushed to O(n) per request, O(n²) total for n requests — the exact profile of a hash-flooding denial-of-service. The fix is never “add more buckets” — it’s “use a hash function that actually mixes the key’s content, not a derived property of it.”

Python in practice

In Python, dict, set, Counter, and defaultdict are all built on the same underlying hash table.

# dict — key-value pairs
ages = {}
ages["Alice"] = 25        # set: O(1) average
ages["Bob"] = 30
print(ages["Alice"])      # get: O(1) average -> 25
print("Alice" in ages)    # membership: O(1) -> True

# set — fast membership testing
seen = set()
seen.add("a")
seen.add("b")
print("a" in seen)        # O(1) -> True
print("z" in seen)        # O(1) -> False

Compare this to a list, where x in my_list must scan element by element at O(n) — a set is dramatically faster once the data grows.

collections.Counter (a dict subclass) counts things without any manual bookkeeping:

from collections import Counter

counts = Counter(["a", "b", "a", "c", "a", "b"])
print(counts)                  # Counter({'a': 3, 'b': 2, 'c': 1})
print(counts.most_common(1))   # [('a', 3)]

collections.defaultdict removes the “check if the key exists first” boilerplate, which is exactly where beginners accidentally reintroduce an O(n) list scan or a KeyError:

from collections import defaultdict

groups = defaultdict(list)          # missing key -> starts as []
groups["fruit"].append("apple")     # no KeyError, no manual init check
groups["fruit"].append("banana")
groups["veg"].append("carrot")
print(dict(groups))
# {'fruit': ['apple', 'banana'], 'veg': ['carrot']}

A few practical notes worth knowing:

• Since Python 3.7, dict preserves insertion order as a language guarantee (a side effect of the compact dict implementation) — but this is not the same as being sorted, and it doesn’t change the O(1) average complexity.
• Only hashable (effectively immutable) objects can be dict keys or set members: str, int, float, tuple (of hashable elements), frozenset. list and dict are unhashable by design — for the mutability reason from the “when hashing degrades” section above.
• Custom classes are hashable by default (hashed by identity), but if you define __eq__, you must also define a consistent __hash__, or Python will make the class unhashable to protect you from silently breaking the dict/set contract.

The O(n²) → O(n) win

Suppose we want to know whether a list contains any duplicates. The naive approach compares every pair — very slow.

# Naive: nested loops -> O(n^2)
def has_duplicate_slow(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

If nums has 1,000,000 items, this performs roughly 500 billion comparisons — far too slow for real use.

# Hash table: single pass -> O(n)
def has_duplicate_fast(nums):
    seen = set()
    for x in nums:
        if x in seen:        # membership O(1)
            return True
        seen.add(x)          # insert O(1)
    return False

# Frequency count with dict / Counter
from collections import Counter
counts = Counter(nums)       # O(n) single pass

Where is the difference? The first version asks “which other element does this match?” and must scan them all. The second reframes the question as “have I seen this before?”, which a set answers in O(1). We trade a little extra memory for an enormous speedup. This “hash something instead of scanning for it” reframing is the single most common way a naive O(n²) solution becomes O(n) — watch for it anywhere you see a loop nested inside another loop just to check membership or find a match.

Complexity

Operation	Average	Worst case
get	O(1)	O(n)
set	O(1)	O(n)
delete	O(1)	O(n)
contains	O(1)	O(n)

The worst case happens only when all keys collide into one bucket — practically never with a good hash function and a controlled load factor. So in practice we treat these as O(1). But as Worked Example 4 shows, “practically never” assumes the hash function isn’t broken and the input isn’t adversarial.

Real-world problem

Counting word frequency in a large document — for example, finding which word appears most often across a 500-page book.

We model it with a dict whose keys are words and values are counts:

from collections import Counter

def top_words(text, k=10):
    words = text.lower().split()
    counts = Counter(words)        # O(n), one pass over all words
    return counts.most_common(k)

Why a dict? We repeatedly update the count of words we have already seen. With a list, checking “have I counted this word yet?” is O(n) per word, making the whole job O(n²). A dict makes each update O(1), so the whole job is O(n) — fast enough to process millions of words in an instant.

Exercises

1. Two Sum — given a list nums and a target, return the indices of two numbers that add up to target (use a hash map for O(n)).

Solution

def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:            # O(1)
            return [seen[need], i]
        seen[x] = i
    return None
# two_sum([2, 7, 11, 15], 9) -> [0, 1]

Instead of comparing every pair at O(n²), we remember each value we have passed in a dict and ask “is the complement target - x already seen?” in O(1).

2. First Non-Repeating Character — given a string, return the first character that appears exactly once.

Solution

from collections import Counter

def first_unique(s):
    counts = Counter(s)             # O(n)
    for ch in s:                    # O(n)
        if counts[ch] == 1:
            return ch
    return None
# first_unique("aabbcdd") -> "c"

Count every character first with a dict, then walk in original order to find the first with count 1. Total O(n).

3. Group Anagrams — given a list of words, group those that are anagrams of one another, e.g. ["eat","tea","tan","ate","nat"].

Solution

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))    # anagrams share the same sorted key
        groups[key].append(w)
    return list(groups.values())
# -> [["eat","tea","ate"], ["tan","nat"]]

Use the “sorted letters” as the dict key; anagrams automatically fall into the same bucket.

4. Find the Missing Number — a list should contain 1..n but is missing one. Find it using a set for O(n).

Solution

def find_missing(nums, n):
    present = set(nums)             # O(n)
    for i in range(1, n + 1):
        if i not in present:        # O(1)
            return i
    return None

5. Predict the Bucket — using the toy hash function from Worked Example 1 (h(s) = sum(ord(c) for c in s)) and a table of size 8, which bucket does "ant" land in? Would it collide with any key already in that table (cat, dog, bird, fish, lion)?

Solution

s = "ant"
total = ord("a") + ord("n") + ord("t")   # 97 + 110 + 116 = 323
bucket = total % 8                        # 323 % 8 = 3

"ant" hashes to bucket 3, which was empty in the original table — no collision this time. (Try "tan" too: same characters, same sum, same bucket as "ant" — a reminder that this toy hash function doesn’t even care about character order, which would be a red flag for a real hash function.)

6. Spot the Bug — a teammate wrote this to deduplicate a stream of user IDs while preserving order:

def dedupe(ids):
    result = []
    for uid in ids:
        if uid not in result:      # bug is here
            result.append(uid)
    return result

It gives the correct output. What’s wrong with it, and how would you fix it while keeping the order?

Answer

uid not in result checks membership in a list, which is O(n) — so the whole function is O(n²). Fix by tracking membership in a set alongside the ordered list:

def dedupe(ids):
    result = []
    seen = set()
    for uid in ids:
        if uid not in seen:      # O(1)
            seen.add(uid)        # O(1)
            result.append(uid)
    return result

Now membership checks are O(1), and the whole function is O(n). (In Python 3.7+, dict.fromkeys(ids) is an even shorter way to dedupe while preserving order, since dict preserves insertion order.)

7. Pick the Right Structure — you’re building a web crawler that must never visit the same URL twice, and doesn’t care about the order URLs were visited in. Which structure: list, set, or dict? What if you also needed to remember, for each URL, the HTTP status code it returned?

Answer

For “never visit twice” with no ordering need: a set of visited URLs — O(1) membership check before crawling each new link, versus O(n) for a list.

If you also need to store a status code per URL, upgrade to a dict ({url: status_code}) — it gives you both the O(1) membership check (url in visited_dict) and a place to store the associated value, so you don’t need two separate structures.

8. Load Factor & Resize — a hash table with 16 buckets currently holds 11 items, and its implementation resizes (doubling the bucket count) whenever the load factor would exceed 0.75. If you insert two more items, will it resize? What is the load factor immediately after the resize (if any)?

Answer

Current load factor: 11 / 16 = 0.6875. After inserting one more item: 12 / 16 = 0.75 — right at the threshold. After inserting the second item (13 items, still 16 buckets before resizing, 13 / 16 = 0.8125), it has definitely crossed 0.75, so a resize to 32 buckets happens: new load factor = 13 / 32 = 0.40625.

AI Code Critique

You ask an AI to write a function that finds duplicate emails in a list of user records. It replies:

def find_duplicate_emails(users):
    duplicates = []
    for i in range(len(users)):
        for j in range(i + 1, len(users)):
            if users[i]["email"] == users[j]["email"]:
                if users[i]["email"] not in duplicates:
                    duplicates.append(users[i]["email"])
    return duplicates

Your turn to judge: the result is correct, but the nested loops make it O(n²), and not in duplicates on a list adds another O(n). With a million users it becomes unusable. Rewrite it with a set to get O(n).

Solution

def find_duplicate_emails(users):
    seen = set()
    duplicates = set()
    for u in users:
        email = u["email"]
        if email in seen:          # O(1)
            duplicates.add(email)  # O(1)
        else:
            seen.add(email)
    return list(duplicates)

A single pass O(n): seen remembers emails encountered, duplicates collects repeats. Every check and insert is O(1) — turning O(n²) into O(n).

🎮 Game Dev: Spatial Hash for Collision Detection

A hash table is how a real game engine avoids checking every sprite against every other sprite for collisions. Instead of hashing a string or a number, you hash a position: bucket sprites by which grid cell they occupy, so a collision check only has to look at the handful of sprites sharing that cell (or a neighbouring one). The same “hash a key straight to its bucket” trick also backs entity lookup by id (entities[entity_id]) and tile-type lookup (tile_types[tile_id]) — no engine wants to scan a list just to answer “what’s at this id?”

Worked example — from O(n²) collision checks to a spatial hash

from collections import defaultdict

CELL_SIZE = 64  # roughly one sprite's width

class SpatialHash:
    """Buckets sprites by grid cell so 'what's nearby' stays cheap."""
    def __init__(self, cell_size: int = CELL_SIZE):
        self.cell_size = cell_size
        self.buckets = defaultdict(list)      # (cx, cy) -> [sprites]

    def _cell(self, x, y):
        return (int(x // self.cell_size), int(y // self.cell_size))

    def insert(self, sprite):
        self.buckets[self._cell(sprite.x, sprite.y)].append(sprite)

    def nearby(self, sprite):
        cx, cy = self._cell(sprite.x, sprite.y)
        found = []
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                found.extend(self.buckets.get((cx + dx, cy + dy), []))
        return found

# Naive: every sprite checked against every other sprite -> O(n^2)
def collisions_naive(sprites):
    pairs = []
    for i in range(len(sprites)):
        for j in range(i + 1, len(sprites)):
            if sprites[i].overlaps(sprites[j]):
                pairs.append((sprites[i], sprites[j]))
    return pairs

# Spatial hash: only check sprites sharing a cell (or a neighbour) -> ~O(n)
def collisions_hashed(sprites, cell_size=CELL_SIZE):
    grid = SpatialHash(cell_size)
    for s in sprites:
        grid.insert(s)
    pairs = []
    for s in sprites:
        for other in grid.nearby(s):
            if other is not s and s.overlaps(other):
                pairs.append((s, other))
    return pairs

With 500 sprites on screen, collisions_naive runs roughly 125,000 overlap checks every single frame. collisions_hashed buckets all 500 sprites into cells first (O(n)), then each sprite only tests the sprites in its own 3×3 neighbourhood of cells — if sprites are reasonably spread out, that’s a small, roughly constant number of checks per sprite, so the whole pass is ~O(n). It’s the exact same hash(key) % table_size idea from earlier in this lesson — the only difference is that key is now a position instead of a string.

Figure: a sprite’s position hashes to a grid cell, and that cell’s bucket holds only the sprites near it — no scanning the whole world.

The same bucket-by-hash trick shows up twice more in a typical engine, this time hashing a plain id instead of a position:

entities = {}                        # entity_id -> Entity object
entities[42] = Entity("goblin")
entities[42].hp -= 10                # O(1) -- no scanning a list of entities

TILE_TYPES = {0: "grass", 1: "wall", 2: "water", 3: "lava"}
def tile_at(grid, tx, ty):
    return TILE_TYPES[grid[ty][tx]]  # O(1) dict lookup, not a linear search

Both are ordinary dicts, but the payoff is identical to the spatial hash above: an id or a tile code hashes straight to its bucket instead of forcing a linear scan through every entity or every tile type in the game. Try <algo-hash size="8"> below with your own keys and watch which bucket each one lands in.

Exercises

G1. Hashing positions — A sprite sits at (150, 230). Using CELL_SIZE = 64, which cell (bucket) does it hash into?

Answer

cx = 150 // 64   # 2
cy = 230 // 64   # 3
# cell = (2, 3)

G2. Collisions in a bucket — Five sprites sit at (10,10), (95,20), (150,150), (205,190), (300,300). Using cell_size = 100, which bucket holds more than one sprite, and which two sprites does that make candidates for a real overlap check?

Answer

(10,10)   -> (0,0)
(95,20)   -> (0,0)   # same bucket as (10,10)
(150,150) -> (1,1)
(205,190) -> (2,1)
(300,300) -> (3,3)

Bucket (0,0) holds two sprites — (10,10) and (95,20) — so only that pair needs an actual overlap check. Every other sprite sits alone in its bucket and can skip the check entirely.

G3. Cell-size choice — Your sprites are all 32×32 pixels. A teammate proposes CELL_SIZE = 8, another proposes CELL_SIZE = 2000. What goes wrong with each, and what size would you actually pick?

Answer

CELL_SIZE = 8 is far smaller than a sprite: a single 32×32 sprite now spans roughly 4×4 = 16 cells, so you’d have to insert it into (or check) many buckets just to know where it is — you’ve reintroduced a lot of bookkeeping for no benefit. CELL_SIZE = 2000 is far larger than the whole play area a sprite could realistically collide within: almost every sprite falls into the same bucket, and nearby() degrades back to scanning nearly everything — the exact same failure mode as a bad hash function clustering keys. A good rule of thumb is to pick a cell size close to (or a small multiple of) the largest sprite’s size, so each sprite touches only 1–4 cells and each bucket holds only a handful of sprites.

G4. Spot the bug — A teammate’s nearby() only checks the sprite’s own cell:

def nearby(self, sprite):
    return self.buckets.get(self._cell(sprite.x, sprite.y), [])

Two sprites are clearly overlapping on screen, but this function never reports them as neighbours. What’s wrong, and how does the 3×3 version above fix it?

Answer

A sprite near the edge of its cell can overlap a sprite that hashed into the adjacent cell — the grid is an arbitrary partition, not a boundary the game world respects. Checking only self._cell(...) misses every collision that straddles a cell border. The fix is to check the full 3×3 neighbourhood of cells (dx, dy in {-1,0,1}), as SpatialHash.nearby() does above, so a sprite is compared against everything in its own cell and the eight cells surrounding it.

Challenge problems

Challenge 1 — Nearest-neighbour query. Given a SpatialHash and a query point (say, “where’s the closest pickup to the player?”), find the nearest sprite without scanning every sprite in the game.

Approach

Start at the query point’s own cell and check its contents. If it’s empty (or you need a correctness guarantee), expand outward ring by ring: check the 3×3 neighbourhood, then the 5×5 ring, then 7×7, stopping as soon as you find a candidate and have expanded one extra ring past it (because a closer sprite could still be sitting just across a cell boundary in the next ring out). Track the best (closest) candidate found so far and only keep expanding while a closer match is still mathematically possible given the ring distance. This turns a nearest-neighbour query from O(n) into roughly O(1) for evenly spread-out sprites, at the cost of a bit of edge-case bookkeeping.

Challenge 2 — Hash-flooding from clustered sprites. A boss fight spell pulls 300 monsters into a single 64×64 tile. That one bucket now holds 300 entries, and every nearby() call near that tile costs O(n) again — the exact same failure mode as feeding a bad hash function adversarial input, except here the “attacker” is your own game design.

Approach

The fix is never “add more buckets everywhere” (that’s the resizing intuition from earlier in this lesson, and it doesn’t help when the load itself is concentrated in one spot). Instead: detect buckets whose length crosses a threshold and treat them specially — either subdivide that one hot cell into a finer sub-grid on demand (a mini spatial hash inside the crowded bucket, similar in spirit to a quadtree), or route sprites in an overcrowded bucket through a cheaper “crowd” collision path (e.g., treat the cluster as a single circle around its centroid instead of pairwise checks). The general lesson carries over directly from ordinary hash tables: a uniform hash function assumes uniformly-spread keys, and clustered input — whether malicious or just a popular boss arena — always needs a plan beyond “make the table (or the grid) bigger.”

Going deeper

• MIT 6.006 — Introduction to Algorithms, lectures “Hashing with Chaining” and “Table Doubling, Karp-Rabin” (free on MIT OpenCourseWare).
• Stanford CS161 — Design and Analysis of Algorithms, the Hashing and Universal Hashing units.
• CLRS — Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein), Chapter 11 “Hash Tables” — the formal treatment of simple uniform hashing, chaining analysis, and universal hashing behind this lesson’s “average vs. worst case” section.
• Sedgewick & Wayne — Algorithms, 4th ed., Section 3.4 “Hash Tables” — clean implementations of both separate chaining and linear probing, with an especially good treatment of resizing the array in tandem with the hash table.
• Weiss — Data Structures and Algorithm Analysis, the hashing chapter — strong side-by-side comparison of collision-resolution strategies (chaining, linear/quadratic probing, double hashing) with worked complexity derivations.
• Skiena — The Algorithm Design Manual, 3rd ed. — the “Dictionaries” war-story chapter, good for when-to-use-what intuition and real anecdotes about hash table failures in practice (including hash-flooding-style issues).
• Python documentation & CPython source — the dict implementation notes (objects/dictobject.c) and the talk “The Mighty Dictionary”, explaining the open addressing Python actually uses.