Hash Tables: Collisions, Load, and Resizing

Looking up a profile by user ID asks “what value belongs to this key?” rather than “what is the element at this position?” A hash table converts the key to an integer and uses it to choose a starting position in an array, reducing the need to compare entries one by one. Open Data Structures’ hash-table chapter introduces two common implementations: separate chaining and linear probing.

The data structures map helps choose a representation by its operations. The question here is how lookup stays correct when several keys land at the same position, why deletion needs care, and what “expected constant time” assumes. For arrays and capacity, see Arrays and Dynamic Arrays.

Mappings, sets, and hash tables

A mapping associates unique keys with values and supports keyed lookup, insertion or update, and deletion. A set stores members and supports addition, deletion, and membership tests. These are interfaces; a hash table is an implementation. A balanced search tree can also implement either interface, provided keys can be compared in a consistent total order, with different costs and ordering capabilities.

CPython’s implementation FAQ describes its dictionaries as resizable hash tables. For Python’s missing-key behavior, iteration, and merging, see Dictionaries and Keyed State. The small mapping below makes storage visible; the same collision handling works for a set if the values are omitted.

Hashes choose the start; equality identifies the key

Let $h(k)$ be a key’s integer hash value and $m$ the capacity. A simple way to choose the starting position is $h(k)\bmod m$. Different keys can have the same complete hash value, or different hashes that reduce to the same starting position. Both situations need collision handling.

Open Data Structures’ requirements for hash codes are that equal keys have equal hashes and that unequal keys should have a small probability of sharing a hash. Collisions still require key comparisons. Treating the hash itself as a unique identifier would merge distinct keys.

Python’s definition of hashable requires an object’s hash to stay unchanged throughout its lifetime, with equal objects having equal hashes. Keep the fields used in hashing and equality stable: otherwise an entry may remain at its old position while a new lookup starts elsewhere. Changing equality can also break key uniqueness even if the hash stays unchanged. Strings and tuples of hashable elements are common choices. Lists are unhashable, as are tuples containing lists. Mutability and hashability are separate properties for custom objects; instances using the default identity-based equality can be hashable.

The Python data model also explains that string and bytes hashes are salted by default. They stay stable within a process but are not guaranteed to match across processes. This helps resist deliberately colliding inputs, but does not remove every bad case or make a custom constant hash efficient. Store persistent identifiers separately rather than relying on a built-in hash value.

Two storage strategies

Separate chaining keeps a collection of entries in each array bucket. Lookup selects a bucket and compares keys within it; deletion removes the matching entry. A linked list is one possible bucket representation, but other list structures also work.

Open addressing with linear probing stores entries in one array, with at most one entry per slot. When the starting slot is occupied, it checks successive slots, wrapping to zero after the end. Lookup must follow the same probe sequence.

Question	Separate chaining	Open addressing (linear probing)
Where does a colliding entry go?	Into the same bucket’s list	Into a later available slot
How does lookup work?	Compare keys in the bucket	Compare keys along the probe sequence
How does deletion work?	Remove from the bucket’s list	Here, leave a deletion marker to preserve the probe path
Space and access	Bucket storage adds overhead; linked nodes require indirection	Spare slots are needed; consecutive probes have locality but can form long clusters

In linear probing, adjacent occupied slots form a cluster. Further keys whose starting positions fall inside it extend the cluster: this is primary clustering. Hash distribution and the probe rule affect performance, so the number of entries alone is not enough to predict it.

A collision trace with deletion

Take capacity $m=8$ and the teaching hash $h(k)=k$ for integer keys. Insert 5, 13, and 21 in that order with values A, B, and C. All three start at slot 5. This deliberately colliding rule makes the arithmetic easy; it does not satisfy a uniform-distribution performance assumption or reproduce CPython’s probing algorithm.

EMPTY means a slot has never held an entry since the current table was built. DEL means an entry was stored there and later deleted.

Operation	Slots examined	Result
Insert 5	5	Store at slot 5
Insert 13	5, 6	Store at slot 6
Insert 21	5, 6, 7	Store at slot 7
Delete 13	5, 6	Mark slot 6 as DEL
Look up 21	5, 6, 7	Skip DEL; find C at slot 7
Look up 29	5, 6, 7, 0	Slot 0 is EMPTY, proving absence
Update 21 to C2	5, 6, 7	Update slot 7; leave the marker at slot 6
Insert 29	5, 6, 7, 0	After establishing absence, reuse slot 6

If deleting 13 changed slot 6 to EMPTY, lookup for 21 would stop there and incorrectly report absence. A deletion marker, often called a tombstone, tells lookup to continue. Insertion can remember the first tombstone, but must keep looking for an existing equal key so that an update does not become a duplicate insertion.

This complete Python 3 program runs the trace and reinserts the remaining entries into a table of capacity 16. Keys are integers and values are strings; get returns None for absence. put returns the target slot, whether the key already existed, and the slots examined. For an absent key, it raises OverflowError if no empty slot or tombstone is available; existing keys can still be updated in a full table. Rebuilding is explicit at the end; “Why resizing can be amortized” describes an automatic growth policy. Each probe sequence examines the table at most once.

EMPTY = None
DELETED = object()


def locate(table, key):
    first_deleted = None
    visited = []
    for step in range(len(table)):
        index = (key + step) % len(table)
        visited.append(index)
        entry = table[index]
        if entry is EMPTY:
            target = index if first_deleted is None else first_deleted
            return target, False, visited
        if entry is DELETED:
            if first_deleted is None:
                first_deleted = index
        elif entry[0] == key:
            return index, True, visited
    return first_deleted, False, visited


def put(table, key, value):
    index, found, visited = locate(table, key)
    if index is None:
        raise OverflowError("table full")
    table[index] = (key, value)
    return index, found, visited


def get(table, key):
    index, found, visited = locate(table, key)
    return (table[index][1] if found else None), visited


def delete(table, key):
    index, found, visited = locate(table, key)
    if found:
        table[index] = DELETED
    return found, visited


def snapshot(table):
    return ["EMPTY" if x is EMPTY else "DEL" if x is DELETED
            else x[0] for x in table]


table = [EMPTY] * 8
for key, value in [(5, "A"), (13, "B"), (21, "C")]:
    print("put", key, put(table, key, value))
print("slots", snapshot(table))
print("delete", 13, delete(table, 13))
print("slots", snapshot(table))
print("get", 21, get(table, 21))
print("get", 29, get(table, 29))
print("update", 21, put(table, 21, "C2"))
print("put", 29, put(table, 29, "D"))
print("slots", snapshot(table))
larger = [EMPTY] * 16
for entry in table:
    if entry is not EMPTY and entry is not DELETED:
        put(larger, *entry)
print("resized", snapshot(larger))
print("get", 21, get(larger, 21))

Output:

put 5 (5, False, [5])
put 13 (6, False, [5, 6])
put 21 (7, False, [5, 6, 7])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 13, 21]
delete 13 (True, [5, 6])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 'DEL', 21]
get 21 ('C', [5, 6, 7])
get 29 (None, [5, 6, 7, 0])
update 21 (7, True, [5, 6, 7])
put 29 (6, False, [5, 6, 7, 0])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 29, 21]
resized ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 21, 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 29, 'EMPTY', 'EMPTY']
get 21 ('C2', [5, 6])

At capacity 16, keys 5, 21, and 29 start at 5, 5, and 13. Reinserting in old-slot order places them at 5, 6, and 13; lookup for 21 now examines only 5 and 6. Resizing must recalculate positions. Copying the old array and appending empty slots would not restore the lookup rules.

Load factor and tombstones

Let $n$ be the number of live entries and $m$ the number of buckets or slots. The load factor is $\alpha=n/m$. In separate chaining it is also the average bucket length and can exceed 1. Under a suitable randomized hashing model, expected lookup cost is $O(1+\alpha)$; bounding the load gives expected $O(1)$. A short average bucket does not rule out a long individual bucket.

Open addressing also needs to track tombstones. Let $d$ count deletion markers and $q=n+d$ count nonempty slots. Before deletion in the example, $n=3$ and $\alpha=3/8=0.375$. Afterwards, $n=2$ and $d=1$: live load falls to $2/8=0.25$, while the nonempty fraction stays at $q/m=3/8=0.375$. Lookup cannot stop at DEL, so counting only live entries understates the probing burden.

Open Data Structures’ linear-probing implementation maintains $m\ge 2q$, leaving at least half the slots EMPTY. Its analysis first assumes independently, uniformly distributed hash positions, then discusses tabulation hashing suitable for linear probing. Under those conditions, lookup, insertion, and deletion excluding rebuilding take expected $O(1)$ time. Half-full is that implementation’s policy, not a universal threshold for hash tables or Python dictionaries.

Rebuilding reinserts only live entries and removes tombstones. Grow when more space is needed; rebuilding at the same capacity can clear excessive tombstones. In this trace, insertion of 29 has already removed the only marker. Growing to 16 gives load $3/16=0.1875$, but keys 5 and 21 still collide.

Why resizing can be amortized

Consider another table that starts at capacity 4, receives only new-key insertions, and doubles before an insertion would make it more than half-full. Inserting 20 keys triggers growth before insertions 3, 5, 9, and 17, reinserting 2, 4, 8, and 16 existing entries. That is $2+4+8+16=30$ reinsertions plus 20 new-entry writes: 50 entry placements. This counts neither elapsed time nor probes. Collisions, scanning the old table, initializing the new array, and hashing still need accounting.

The reinsertion counts form a geometric series. For $N$ insertions starting empty, this policy makes fewer than $2N$ reinsertions; total array initialization and scanning also grow linearly with $N$. If each placement has bounded expected cost, total expected work is $O(N)$ and insertion is expected amortized $O(1)$. The reasoning parallels geometric growth in dynamic arrays, but a hash table must also restore each key’s lookup position.

“Expected” averages over hashing randomness; “amortized” spreads occasional rebuilding across a sequence of operations. See time complexity for the distinction. When capacity is proportional to the entry count, hashing and comparisons have fixed cost, and expected probing cost is bounded, one rebuild costs expected $O(n)$. The insertion that triggers it can still have noticeable latency. If every key clusters together, reinserting entries one by one with linear probing can even require quadratic probing work.

If shrinking is supported, separate growth and shrink thresholds so that alternating insertion and deletion of one key cannot repeatedly rebuild the table. Open Data Structures’ implementation rebuilds when more than half the slots are nonempty or live entries fall below one-eighth of capacity; it then chooses the smallest power-of-two capacity at least $3n$.

What constant time still pays for

For ordinary chained or probing implementations, suitable hashing, controlled load, and fixed-cost key handling give expected $O(1)$ lookup and deletion excluding rebuilding. Insertion and deletion that can rebuild need expected amortized bounds under a suitable rebuild policy. Severe collisions can make one lookup examine $O(n)$ entries. For a full-table scan in open addressing, the more precise bound is $O(m)$, which becomes $O(n)$ only when $m=O(n)$.

The key itself has a cost. If hashing key $k$ takes $H(k)$, lookup examines $p$ slots and compares candidate keys, its cost can be written as:

$$T(k)=H(k)+O(p)+\sum_{j\in C}E(k,k_j).$$

Here $C$ contains the candidate entries actually compared, and $E(k,k_j)$ is the cost of one equality test. Tombstones contribute to $p$ but not to $C$. Hashing by scanning a whole key of length $L$ takes $O(L)$ work, and comparing long keys may also read to the end. Reducing the candidate count does not automatically remove that work. Reusing a cached hash can save computation when the key stays stable and the implementation actually stores and uses that cache.

When order or range queries matter

Python’s mapping contract guarantees dictionary insertion order in Python 3.7 and later. Insertion order and sorted key order serve different needs; hash-bucket positions do not express comparisons such as less than or greater than.

Main need	Candidate structure	Costs to include
Repeated full-key lookup, deduplication, or counting	Hash mapping or hash set	Hashing, collisions, spare capacity, and rebuilding
Sorted positions or range boundaries in static data	Sorted array with binary search	Sort first; boundary lookup takes $O(\log n)$ comparisons and listing $r$ results adds $O(r)$; Python bisect provides boundary searches
Frequent updates plus predecessor, successor, or range queries	Balanced search tree	Maintain balance; typical range reporting is $O(\log n+r)$ with fixed-cost comparisons

“Does key 21 exist?” fits a hash table. “Which keys lie between 10 and 30?” usually requires scanning entries in an ordinary hash table or maintaining another ordered index. The search algorithms map puts these workloads together, so the query method follows from the information the structure maintains.

My reading · Opened notes are remembered in this browser.