Hash Functions, Collisions, Probing and Deletion

A hash table stores key-value entries and uses a hash function to choose where a key should be sought. Instead of maintaining keys in sorted order, it transforms a key into an integer hash value and derives an initial bucket or slot from that value. With a suitable hash function, controlled occupancy and correct collision handling, search, insertion and deletion take expected O(1) time.

This expectation is not a universal guarantee. Several keys may concentrate in one region, an adversary may construct colliding keys or the table may become too full. In the worst case, a lookup can examine O(n) entries. Hash tables favor exact-key access; they do not naturally provide sorted traversal, predecessor queries or efficient key ranges.

Hash Functions and Key Equality

A hash function should be deterministic during the key’s residence in the table: the same key state must produce the same hash. It should mix relevant key information so common input patterns spread across available buckets. Computing the hash must also be inexpensive compared with the operation being accelerated.

The table converts a possibly wide hash value into an index. A simple teaching example uses

index = floorMod(hash, capacity)

where floor-mod behavior keeps the result nonnegative. Direct % with a negative hash can produce a negative remainder in some languages. Real implementations may further mix bits or exploit a power-of-two capacity.

Because a large key universe maps into a finite number of positions, collisions are unavoidable. A collision occurs when different keys choose the same initial position. Equal hashes do not imply equal keys. After locating candidates by hash, the table must still compare keys for equality.

For key objects, equality and hashing must agree: if two keys are equal, they must have equal hash codes. Unequal keys may share a hash. If an object’s fields used by equality or hashing change while it is stored, later lookup may start from a different bucket and fail to find the entry. Hash keys should therefore be immutable in their hash-relevant state or removed before mutation and reinserted afterward.

Load Factor

The load factor is commonly

alpha = number of entries / number of buckets or slots

Its interpretation depends on collision strategy. In separate chaining, alpha can exceed one because a bucket may hold several entries. Under uniform distribution, it approximates average chain length. In open addressing, every entry occupies a table slot, so alpha must remain below one and performance deteriorates sharply as it approaches one.

A table normally resizes when occupancy crosses a threshold. It allocates a new table, often with a substantially larger capacity and reinserts active entries. Simply copying entries to identical numeric indices is incorrect because the mapping and probe sequences depend on capacity. Geometric growth makes occasional O(n) rehashing compatible with expected amortized constant-time insertion.

Common Hash Construction Ideas

For integers, division hashing uses a remainder such as key mod m. Capacity choice affects distribution: if keys share factors with m, they can cluster. Prime capacities are often used with some probing formulas, while power-of-two capacities work well when hashes have been mixed across their low bits.

String hashing processes characters in sequence, commonly with a polynomial recurrence such as h = multiplier * h + character. Fixed-width overflow can be treated as part of the arithmetic. A good multiplier and final mixing help small character changes influence several result bits.

Composite keys combine component hashes in an order-sensitive way when component order matters. Every field involved in equality should normally contribute to hashing. A secure keyed hash may be appropriate when attackers can select keys and collision attacks are a concern; a fast noncryptographic function is usually sufficient for trusted in-memory keys.

Separate Chaining

Separate chaining gives each array bucket a secondary container, traditionally a linked list. All keys mapping to bucket i are stored in that bucket’s chain. Search computes i and compares the target with entries in that one chain. Insertion adds or updates an entry there and deletion unlinks it.

With n entries and m buckets under approximately uniform hashing, average chain length is alpha = n/m, so expected operation time is O(1 + alpha). A badly distributed table can place all entries in one chain and require O(n) search.

Chains may be dynamic arrays, linked lists or tree structures. Linked chains make deletion simple once the entry is located but add allocation and pointer overhead. Some library implementations convert a heavily populated bucket into a balanced tree, improving behavior under concentrated collisions while adding complexity.

Chaining handles deletion naturally and can operate with load factor above one. It uses additional node or container storage and has weaker locality than entries stored directly in one array.

Open Addressing

Open addressing stores every entry within the table array. When the initial slot is occupied by another key, a probe sequence examines alternative slots. Search and insertion must generate exactly the same sequence for the same key and table state.

A slot has at least three logical states: never used, currently occupied and deleted. Search compares occupied entries, continues past deleted slots and stops unsuccessfully at a never-used slot because no insertion following that probe sequence could have passed it without occupying it. A full cycle or explicit probe bound is needed to prevent an infinite loop when no terminating slot exists.

Linear Probing

Linear probing examines

(h(key) + i) mod m, for i = 0, 1, 2, ...

It has excellent locality because it scans adjacent slots. It suffers from primary clustering: once a contiguous occupied run forms, any key hashing anywhere into that run extends it, making future probes longer.

Quadratic Probing

Quadratic probing uses offsets based on a quadratic expression, such as

(h(key) + c1*i + c2*i*i) mod m

It spreads probes away from a contiguous run and reduces primary clustering. Its ability to reach enough slots depends on capacity and constants. Keys with the same initial hash still follow the same sequence, a behavior called secondary clustering.

Double Hashing

Double hashing uses a second hash to choose the step:

(h1(key) + i * h2(key)) mod m

Different keys with the same first position can have different steps. The step must be nonzero modulo m and relatively prime to m if the sequence is to visit every slot. With prime m, a common construction chooses a step from 1 through m - 1.

Deletion in Open Addressing

Deletion cannot usually change an occupied slot directly to never-used. Suppose keys 10 and 17 both hash to 3 modulo 7 and linear probing places 17 at slot 4. If deleting 10 marks slot 3 never used, a later search for 17 starts at 3, stops immediately and incorrectly reports absence.

A tombstone marks a slot as deleted while preserving evidence that a probe sequence may continue. Search passes a tombstone. Insertion remembers the first tombstone as a reusable position but continues far enough to determine whether the key already exists; otherwise it could create duplicate entries later in the sequence.

Tombstones accumulate and lengthen probes even though the logical entry count is low. A rehash discards them by reinserting only active entries. Some linear-probing implementations instead use backward-shift deletion, carefully moving later entries toward the gap without crossing their legal probe origins. That technique avoids tombstones but requires a correct circular-range test.

Insertion, Lookup and Updating

A map insertion must distinguish adding a new key from replacing the value of an existing key. During probing or chain traversal, equality is checked before a new entry is committed. Updating an existing key does not increase size. A set uses the same structure but stores only membership or stores a placeholder value.

A lookup returns success only after an equality match. Hash equality narrows candidates but never completes the logical key test. APIs must also distinguish a missing key from a key mapped to null if null values are allowed, using membership testing or an explicit optional result.

Expected constant time depends on hash quality and a bounded load factor. Resizing, treeified collision buckets or randomized hash seeds can protect performance, but each comes with memory or implementation costs.

Hashing and Memoization

Memoization uses a map from subproblem arguments to previously computed results. In naive Fibonacci recursion, the same argument is solved repeatedly. Caching fib(k) by key reduces the number of distinct computations to n + 1, changing exponential work to linear time. The key must contain all information that determines the subproblem result; an incomplete key can return an incorrect cached answer.

Hash tables also support symbol tables, caches, indexes, frequency counts, duplicate detection, graph adjacency maps and joins. Where ordered operations matter, a balanced search tree may be a better choice. Where keys are dense small integers, direct array indexing can be simpler and faster.

Verifying a Hash Table

Tests should force collisions rather than using only distinct initial buckets. For open addressing, insert colliding keys, delete the earliest one, confirm later keys remain reachable, reuse tombstones and exercise wraparound at the array end. Resize tests should verify every active mapping and ensure size excludes deleted markers.

For chaining, verify head, middle and tail deletion within one bucket and replacement of an equal key. Key-contract tests use distinct but equal objects and keys with deliberately identical hashes. An invariant checker can confirm that every active entry is reachable from its computed bucket or probe sequence and that recorded counts match physical states.

Hashing is powerful because it turns a key into a small search region. Correctness still depends on key equality, collision resolution, load management, deletion semantics and rehashing as one coherent design.