4.2 Hash Collisions and Resizing
Prerequisites: Hash Table Basics, about 45 minutes. This section compares chaining with open addressing, focusing on the termination condition of linear probing, tombstone deletion, and when hashing and load assumptions let geometric resizing give expected amortized O(1) insertion cost.
Multiple Keys Land in One Bucket
Assume A and I hash to the same bucket index. Chaining keeps both entries in a container owned by that bucket; open addressing follows a probe sequence to locate another slot.
Collisions cannot be eliminated. The structure needs rules for continuing the search and deciding when a key is absent.
Why Better Hashing Cannot Eliminate Collisions
Assume the table has only m buckets, but the possible key values exceed m. By the pigeonhole principle, at least two keys will end up in the same bucket. A good hash function spreads common inputs more evenly, reducing clustering; it cannot provide infinite buckets for an infinite number of keys.
Conflict resolution must simultaneously address three things:
- Where should the new key be placed?
- Where does the query start, and under what conditions does it stop?
- After deleting a key, how do you ensure that other keys can still be found?
Two main routes
| Dimension | Chaining | Open Addressing |
|---|---|---|
| Bucket storage | Each bucket can hold multiple mappings | All mappings are stored in the main array |
| Actions after a conflict | Continue comparing within the same bucket | Search for other slots according to the probing sequence |
| Delete | Remove the target from the bucket container | Requires strategies such as tombstones, backward shifting, or reinsertion |
| Load factor | Can be greater than 1 | The number of active elements cannot exceed the number of slots |
| Locality | Depends on bucket structure | Contiguous arrays are generally better for caching |
| Major Risks | Single bucket too long | Clustering, accumulated tombstones, longer probe sequences |
Here we're comparing design families. Specific libraries might use different layouts, metadata, and optimizations, so internal implementation should not be inferred solely from type names.
Chaining: Grouping keys in the same bucket together
The bucket implemented on the previous page can be represented as:
bucket[1]
├── ("A", "apple note")
└── ("I", "ink note")When querying "I", the hash function is responsible only for reaching bucket[1]. Then, key equality comparisons are performed sequentially. Deleting "A" does not sever the lookup path of "I", since both mappings are directly managed by the bucket container.
Let n be the number of elements and m be the number of buckets; the load factor for chaining is:
alpha = n / mUnder the simple uniform hashing assumption, the expected length of a bucket is alpha. Lookup also has a constant positioning cost, giving expected O(1+alpha) work. When alpha is bounded by a constant, the expected number of comparisons within a bucket is also bounded by a constant. However, if all inputs hash to the same bucket, the operation degrades to O(n).
Open Addressing: Finding a Spot by Following the Probe Sequence
Open addressing uses only slots in the main array. Linear probing starts at the initial bucket and checks sequentially:
start, (start + 1) % capacity, (start + 2) % capacity, ...Capacity is 8, and "A", "I", "Q" all start at slot 1; the insertion process is as follows:
Insert A: [ ·, A, ·, ·, ·, ·, ·, · ]
Insert I: [ ·, A, I, ·, ·, ·, ·, · ]
Insert Q: [ ·, A, I, Q, ·, ·, ·, · ]A continuously occupied region is called a cluster. Later keys, even if they start at different positions, will still have to traverse more slots if they fall into this region. Linear probing is simple to implement, but it easily leads to primary clustering.
Why can't deletion be simply written as an empty slot?
Continuing from the previous state query "Q": seeing A in slot 1, then I in slot 2, and finally Q in slot 3.
If deleting A immediately changes slot 1 to "never used," querying Q will prematurely stop at slot 1 and incorrectly report a missing entry:
Bad deletion: [ ·, ·, I, Q, ·, ·, ·, · ]
↑ Search wrongly stops hereA common approach is to write a DELETED tombstone:
Tombstone: [ ·, ×, I, Q, ·, ·, ·, · ]
↑ Search skips ×; insertion may reuse itSlots therefore have three states:
EMPTY: Never used. Query can stop.OCCUPIED: Save a mapping. Compare key.DELETED: Was previously used. Continue searching; remember this slot as a possible insertion position.
An executable linear probing table
The following teaching implementation only accepts string keys. Each probe pass checks at most capacity slots, so a full-table search terminates. Insertion checks active load and grows if needed. This version does not automatically clear accumulated tombstones; that limitation will show why active count alone is insufficient. The demo uses max_load=1.0 to exercise full-table behavior, not as a performance recommendation.
EMPTY = object()
DELETED = object()
def stable_hash(key):
if not isinstance(key, str):
raise TypeError("this teaching map accepts string keys only")
value = 0
for char in key:
value = (value * 31 + ord(char)) & 0xFFFFFFFF
return value
class LinearProbingMap:
def __init__(self, capacity=8, max_load=0.7):
if capacity <= 0:
raise ValueError("capacity must be positive")
if not 0 < max_load <= 1:
raise ValueError("max_load must be in (0, 1]")
self._keys = [EMPTY] * capacity
self._values = [None] * capacity
self._size = 0
self._max_load = max_load
@property
def capacity(self):
return len(self._keys)
def __len__(self):
return self._size
def _indices(self, key):
start = stable_hash(key) % self.capacity
for offset in range(self.capacity):
yield (start + offset) % self.capacity
def _find_existing(self, key):
for index in self._indices(key):
stored_key = self._keys[index]
if stored_key is EMPTY:
return None
if stored_key is not DELETED and stored_key == key:
return index
return None
def _insert_without_resize(self, key, value):
first_deleted = None
for index in self._indices(key):
stored_key = self._keys[index]
if stored_key is DELETED and first_deleted is None:
first_deleted = index
elif stored_key is EMPTY:
target = first_deleted if first_deleted is not None else index
self._keys[target] = key
self._values[target] = value
self._size += 1
return
if first_deleted is not None:
self._keys[first_deleted] = key
self._values[first_deleted] = value
self._size += 1
return
raise RuntimeError("hash table is full")
def _resize(self, new_capacity):
old_entries = [
(key, self._values[index])
for index, key in enumerate(self._keys)
if key is not EMPTY and key is not DELETED
]
self._keys = [EMPTY] * new_capacity
self._values = [None] * new_capacity
self._size = 0
for key, value in old_entries:
self._insert_without_resize(key, value)
def put(self, key, value):
existing = self._find_existing(key)
if existing is not None:
self._values[existing] = value
return
if (self._size + 1) / self.capacity > self._max_load:
new_capacity = self.capacity * 2
while (self._size + 1) / new_capacity > self._max_load:
new_capacity *= 2
self._resize(new_capacity)
self._insert_without_resize(key, value)
def get(self, key):
index = self._find_existing(key)
if index is None:
raise KeyError(key)
return self._values[index]
def remove(self, key):
index = self._find_existing(key)
if index is None:
raise KeyError(key)
value = self._values[index]
self._keys[index] = DELETED
self._values[index] = None
self._size -= 1
return value
table = LinearProbingMap(8, max_load=1.0)
table.put("A", "apple")
table.put("I", "ink")
table.put("Q", "quartz")
table.remove("A")
assert table.get("I") == "ink"
assert table.get("Q") == "quartz"
assert len(table) == 2
table.put("Q", "updated quartz")
assert len(table) == 2
assert table.get("Q") == "updated quartz"
table.put("Y", None)
assert table._keys[1] == "Y"
assert table.get("Y") is NoneThree Invariants in Code
_indicescan generate at mostcapacitypositions, and both queries and inserts can terminate._find_existingstops atEMPTYwhen the key is absent; it must continue pastDELETED._resizemoves active mappings; tombstones won't be moved into the new table.
put should first look for an existing key and only then decide whether to resize. Updating a value must not increase the element count or trigger growth intended for a new key. Searching the whole relevant path first also prevents duplicates: inserting immediately at a tombstone could miss the same key farther along. _insert_without_resize is therefore private and assumes the key has already been confirmed absent, or is being rebuilt into a new table.
Load factor doesn't have just one meaning
Typically written as alpha = n / m, where n is the number of active mappings and m is the number of buckets or slots. The two strategies differ in their tolerance for alpha:
- Chaining allows
alpha > 1, since a bucket can hold multiple mappings; increasing alpha will lengthen the search within the bucket. - Open addressing requires that the number of active elements not exceed the number of slots. The closer alpha gets to 1, the fewer available empty slots there are, and the longer the probing sequences tend to become.
Tombstones introduce a second metric: the occupancy factor (n+t)/m, where t counts tombstones. They extend searches even when active load n/m is low. Fill eight slots, then delete seven entries:
sparse = LinearProbingMap(8, max_load=1.0)
for key in "ABCDEFGH":
sparse.put(key, key)
for key in "ABCDEFG":
sparse.remove(key)
assert len(sparse) == 1
assert all(key is not EMPTY for key in sparse._keys)
assert sparse._find_existing("missing") is NoneOnly one entry remains, but there is no EMPTY slot, so a failed lookup scans all eight. This teaching class does not rebuild based on occupancy and cannot promise expected O(1) under arbitrary long-running insert/delete workloads. An extension can count tombstones and rebuild at the same capacity; growth is not always necessary.
Java HashMap has a default load factor of 0.75. This number represents the default trade-off between time and space for this class, and it is not a constant that should be adopted by all hash tables. Python, C++ libraries, and other open-addressing implementations have their own public contracts and implementation choices.
Why Resizing Must Reposition Entries
The bucket index depends on capacity:
index = hash_code % capacityAfter the capacity grows from 8 to 16, old indices can't be directly reused. Implementation requires creating a new array and relocating each active key to its new position. This process is commonly called rehashing, but it doesn't necessarily require recomputing the original hash values of the keys; it depends on whether the implementation caches hash values.
Separate allocation, scanning, and reinsertion. With new capacity m_new and old capacity m_old, initializing the new arrays and scanning the old ones take Θ(m_new+m_old) work. This example also recomputes hashes and probes for each entry’s new position.
With constant-time key operations, suitable hash distribution, and capacity proportional to live entries, rebuilding has expected Θ(n) cost. Start empty with fixed initial capacity and grow by a fixed factor: expected migration work across n consecutive insertions forms a geometric series:
1 + 2 + 4 + ... < 2nThe expected total is Θ(n), giving expected amortized O(1) insertion. This uses both a probability model and analysis over an operation sequence.
In the worst collision pattern, reinserting n keys with the same starting position examines 1+2+...+n = n(n+1)/2 slots. This implementation can therefore take Θ(n²) to rebuild. Geometric growth does not eliminate reinsertion collisions.
If a real-time system cannot tolerate a single long pause, it can opt for incremental migration, reserved capacity, or other data structures; ordinary business code typically pre-allocates capacity based on expected element counts.
Complexity Quick Reference
Let n count live entries and m denote capacity. The table assumes constant-time key operations and hashing suitable for the collision strategy. Linear probing also requires occupancy to stay a fixed distance below 1; bounding only n/m is insufficient.
| Operation | With suitable hashing and controlled load | Worst case | Main reason |
|---|---|---|---|
| Chained Hash Lookup | Expected O(1) | O(n) | All keys enter the same bucket |
| Linear-probing lookup | Expected O(1) | O(m) | Clusters, tombstones, or a full table |
| Linear-probing insertion without growth | Expected O(1) | O(m) | Absence check and placement each scan at most m slots |
| Rebuild/resize with m proportional to n | Expected Θ(n); O(1) after amortizing over a sequence | Θ(n²) can occur | Reinsertion collisions |
| Delete | Expected O(1) | Chaining O(n); linear probing O(m) | Locate, then remove or mark deleted |
| Space | O(m + n) or O(m) | Same order | Depends on strategy and metadata |
If the hash key itself has length L, table operations also incur the cost of hashing and equality comparison. The time complexity table cannot replace a description of the key type and source of input.
How to read the standard library contracts
| Type | Public facts you can rely on | Assumptions to avoid making |
|---|---|---|
Python dict | key must be hashable; insertion order is preserved | fixed bucket layout, fixed string hash values |
Java HashMap | Default load factor 0.75; allows null; does not guarantee order; unsynchronized | All versions use the same internal node strategy |
C++ std::unordered_map | defined with buckets, hashers, and key equivalence predicates; most operations are average constant time, worst-case linear | a specific linked list layout is mandated by the standard |
Resizing may also affect iterators or traversal order. The C++ standard explicitly states that rehashing invalidates iterators and changes bucket distribution but preserves element pointers and references; Java and Python each have their own rules for traversal during modification. Before crossing structural changes with iterators, references, or views, consult the corresponding version's documentation.
Common Mistakes
Compare keys by object identity during probing
Python is checks object identity, while mapping keys usually require the value-equality semantics of ==. Two separately created strings equal to "same" can compare equal without being the same object.
Loop until finding an empty spot, without limiting the number of steps
A full table has no EMPTY. A probe pass checks at most capacity slots and then reports missing entries, triggers expansion, or throws a clear error.
When deleting, write back EMPTY
This will interrupt the lookup chain for other collision keys. When using tombstones, lookup skips tombstones, while insertion remembers the first reusable one.
Expand and copy old index
The bucket index depends on the new capacity. Active mappings must be reinserted according to the new table rules.
Treat 0.75 as a theoretical law
The threshold depends on the conflict strategy, cache layout, memory budget, and latency goals. 0.75 is one of the default values for Java HashMap, not a cross-language solution.
Count Only Live Entries and Ignore Tombstones
Many tombstones can leave failed lookups traversing long probe sequences. A maintained implementation can rebuild periodically or track both live and occupied slot counts.
Debugging Order
- Draw different symbols for
EMPTY,OCCUPIED, andDELETED. - Construct three keys with the same starting point, and gradually record the position of each probe.
- Remove the first element of the cluster, then query the key of the remaining elements.
- Fill a small table and confirm that lookup of a missing key terminates.
- Update existing keys, confirm that
sizeremains unchanged and no unnecessary resize occurs. - Trigger a resize and check every old mapping.
- When analyzing costs, distinguish between regular operations, a single resize, and amortized sequences.
Verify the Probe Sequence
| Difficulty | Task | Acceptance Criteria |
|---|---|---|
| Basic | Manual calculation of linear probing A, I, Q | Mark starting point, clustering areas, and termination conditions |
| Basic | Reproduce incorrect deletion | Can explain why EMPTY truncates the query |
| Advanced | Count tombstone entries | Perform same-capacity rebuild when occupancy factor is too high |
| Advanced | Implement quadratic probing | Prove whether the probing sequence can cover the selected capacity |
| Engineering | Stress-test under different loads | Simultaneously record throughput, tail latency, and memory usage |
Move from Exact-Key Lookup to Ordered Queries
The real difficulty with open addressing is tracing the lookup path: EMPTY indicates the path terminates here, so the search can stop; DELETED only means the old element has moved, and subsequent collision elements might still exist. Resizing requires relocating all active mappings to the new capacity. Under the hashing and load assumptions, a rebuild takes expected Θ(n); fixed-factor growth then keeps expected migration work linear across an insertion sequence. Severe collisions can still make reinsertion quadratic.
Draw empty slots, tombstones, and active entries as one probe sequence and the stopping rule becomes visible. Hash tables excel at exact-key lookup, but they do not answer "what is the next larger key?" Continue with Binary Trees for ordered queries.