Implementing a hash table with quadratic probing
A hash table stores key–value pairs by converting each key into an array index. This direct mapping makes inserts, lookups and updates constant-time on average, but two keys can hash to the same slot. Handling this collision efficiently is the central design problem in an open-addressing hash table.
Quadratic probing resolves a collision by moving through offsets such as 0, 1, 4 and 9 rather than checking every following slot. The result is a compact, array-backed map with less primary clustering than linear probing. The implementation below covers probing, tombstones, resizing and tests without relying on Python’s built-in dictionary.
Open addressing and the collision problem
Open addressing keeps every entry inside one array. Each array position is a bucket, and a collision moves the new entry to another position according to a probe sequence. This contrasts with separate chaining, where each bucket owns a linked list or another container. Open addressing usually uses less per-entry overhead and can be cache-friendly, which is valuable for services handling many small records.
Feature indexing for a random forest ensemble provides a useful example: names or categorical values can be mapped to compact integer identifiers before training. A dedicated table may also power spell-checking, symbol tables or caches, although application code will usually start with Python’s dict. Understanding the mechanism explains why dict is fast and what an educational reimplementation must reproduce.
Selecting a hash function and capacity
The hash function should distribute keys quickly and evenly. Python’s built-in hash is an excellent default for an in-memory table: integers hash predictably, while strings and bytes receive per-process randomisation. That randomisation protects dictionary-like structures from crafted collision attacks, but it also means an index calculated in one process may differ in another. Distributed or persistent systems therefore need a stable custom hash or stable numeric identifiers.
Capacity affects both collisions and memory. Begin with enough space for the expected entries, then resize before the effective load becomes expensive; a practical ceiling is around 0.70 used slots. A prime or odd capacity often distributes quadratic offsets more evenly, although it does not guarantee that a pure square sequence visits every slot. The broader algorithm reference provides useful context for hashing and probing strategies.
The quadratic probe sequence
Given a base index (b = hash(key) \bmod m), quadratic probing examines (h_i = (b + i^2) \bmod m). With (m = 17) and (b = 5), the first positions are 5, 6, 9, 14, 4 and 13. The changing stride breaks the long consecutive runs that make linear probing vulnerable to primary clustering, although overlapping sequences can still create secondary clustering.
Every operation must use exactly the same probe order. A lookup follows the sequence until it finds the key, reaches an unused slot or exhausts the cycle. An insert follows the same path and uses the first unused position. Deletion introduces a subtle exception because a removed slot cannot be treated as unused.
Pure (i^2) offsets eventually repeat. The example therefore uses quadratic positions first and a complete fallback scan if that cycle cannot provide a free slot. This keeps the method correct for every capacity. Another design is to resize whenever the quadratic cycle is exhausted, accepting that some array positions may remain unreachable by that key’s sequence.
Deletion, tombstones, and resizing
Deleting an occupied slot by clearing it would break the search path: a later key might sit beyond what now looks like the end of the chain. A tombstone marks the slot as previously used, so probing continues. During insertion, the table remembers the first tombstone but keeps searching because the same key may already exist farther along the sequence. Transaction-oriented examples, such as this Python blockchain example, show why consistent lookup behaviour matters when many records are addressed by stable identifiers.
Resizing serves two purposes. It creates room when the number of live entries grows, and it removes accumulated tombstones. A useful implementation tracks both size, meaning live entries, and used, meaning occupied positions plus tombstones. When used slots cross a threshold, rehash only live entries into a larger array and reset the tombstone count.
A practical Python implementation
The following Python example uses parallel arrays for keys, values and slot states. It accepts an injectable hash function so tests can force collisions, and its linear fallback guarantees that every slot is eventually considered. States distinguish empty cells from tombstones, which is safer than relying on a special key value.
class QuadraticHashTable:
EMPTY, OCCUPIED, DELETED = 0, 1, 2
def __init__(self, capacity=17, hash_function=hash):
if capacity < 3:
raise ValueError("capacity must be at least 3")
self.capacity = capacity
self.hash_function = hash_function
self.size = 0
self.used = 0
self.keys = [None] * capacity
self.values = [None] * capacity
self.states = [self.EMPTY] * capacity
def _positions(self, key):
base = self.hash_function(key) % self.capacity
seen = set()
# Quadratic probing comes first.
for i in range(self.capacity):
position = (base + i * i) % self.capacity
if position not in seen:
seen.add(position)
yield position
# Guarantee complete coverage if the quadratic cycle repeats.
for position in range(self.capacity):
if position not in seen:
yield position
def put(self, key, value):
first_deleted = None
for position in self._positions(key):
state = self.states[position]
if state == self.OCCUPIED:
if self.keys[position] == key:
self.values[position] = value
return
elif state == self.DELETED:
if first_deleted is None:
first_deleted = position
else:
target = (
position if first_deleted is None else first_deleted
)
was_deleted = self.states[target] == self.DELETED
self.keys[target] = key
self.values[target] = value
self.states[target] = self.OCCUPIED
self.size += 1
self.used += int(not was_deleted)
if self.used / self.capacity > 0.70:
self._resize()
return
self._resize()
self.put(key, value)
def get(self, key, default=None):
for position in self._positions(key):
state = self.states[position]
if state == self.OCCUPIED:
if self.keys[position] == key:
return self.values[position]
elif state == self.EMPTY:
return default
return default
def delete(self, key):
for position in self._positions(key):
state = self.states[position]
if state == self.OCCUPIED:
if self.keys[position] == key:
self.states[position] = self.DELETED
self.keys[position] = None
self.values[position] = None
self.size -= 1
return True
elif state == self.EMPTY:
return False
return False
def _resize(self):
old_entries = list(zip(self.keys, self.values, self.states))
capacity = max(17, int(self.capacity * 1.5) + 1)
while any(
capacity % divisor == 0
for divisor in range(2, int(capacity ** 0.5) + 1)
):
capacity += 1
self.capacity = capacity
self.keys = [None] * capacity
self.values = [None] * capacity
self.states = [self.EMPTY] * capacity
self.size = 0
self.used = 0
for key, value, state in old_entries:
if state == self.OCCUPIED:
self.put(key, value)
Calling put again with an existing key updates the value without increasing size. The delete method returns a boolean and leaves a tombstone, while get stops only at a genuinely empty slot. Because get uses None as its default, it cannot distinguish a missing key from a stored None; a sentinel default or contains method would be needed for that distinction.
The implementation favours clarity over production speed: building the seen set and scanning arrays add overhead. A native dict remains the right choice for most Python programs. The exercise is valuable because it exposes invariants that mature hash-map libraries handle internally.
Performance checks for Australian deployments
For teams serving the Australian market, the table can sit behind local catalogue, routing or scheduling services. A compact cache may index records used by teams in Sydney and Melbourne, while identical replicas in Brisbane and Perth must agree on identifiers even when their processes use different hash seeds. Store canonical IDs rather than relying on a process-specific hash position.
Other Australian details belong in the key design, not in the probe arithmetic. Time-sensitive records should use UTC internally and convert to AEST or AEDT at the boundary, particularly around daylight-saving changes. Catalogue integrations can include retailer-specific identifiers from Coles and Woolworths. Route data for left-hand traffic needs precise coordinates, and event records for AFL or cricket should include the season and venue rather than a bare team name.
Under a well-distributed hash function and a load factor around 0.70, average operations remain close to (O(1)). The worst case is (O(m)), when many probe positions are occupied or keys deliberately collide.
Reliable checks before deployment
- Insert the same key twice and confirm that only one entry remains.
- Delete a key, insert it again and verify that probing passes through the tombstone.
- Inject a constant hash function to force every key through the same collision path.
- Add enough entries to cross the resize threshold and confirm that all values survive.
- Compare random operations against a Python
dictwhile checking the expected size after each mutation.
Australian checks worth including
- Run the same fixtures from services operating in Sydney, Melbourne, Brisbane and Perth.
- Test daylight-saving boundaries using UTC timestamps before applying AEST or AEDT.
- Keep Coles and Woolworths identifiers separate when records represent different catalogues.
- Include left-hand-driving route fixtures with Australian coordinates and road names.
- Use composite identifiers for AFL and cricket fixtures, seasons and venues.
| Property | Quadratic probing | Linear probing | Separate chaining |
|---|---|---|---|
| Storage | One slot per array position | One slot per array position | A list or chain at each bucket |
| Probe sequence | (h(key) + i^2) | (h(key) + i) | Follow the bucket chain |
| Primary clustering | Reduced | Can form long runs | Avoided in the same form |
| Deletion | Tombstone or backward shift | Tombstone or backward shift | Unlink the matching node |
| Memory use | Predictable array allocation | Predictable array allocation | Additional nodes or lists |
| Typical fit | Compact, cache-friendly in-memory maps | Simple open-addressing maps | Higher load factors or frequent collisions |
Quadratic probing offers a compact and predictable implementation when memory usage matters and collision rates remain modest. Keeping the effective load factor under control, preserving tombstones correctly and using stable identifiers across process boundaries provides a clear foundation for understanding the hash maps embedded in languages, databases and caching layers.