Source: Comprehensive Guide on Hash Tables and Collision Resolution Techniques (UCF Computer Science I)
Tags: open addressing, linear probing, quadratic probing, double hashing, perfect hashing, probing sequence, primary clustering, secondary clustering, collision resolution, hash table
Difficulty: Intermediate
Prerequisites: Hash table fundamentals, chaining, load factor, and the division method (see companion notes: "Hash Tables Fundamentals and Chaining").
Chaining resolves collisions by building linked lists outside the table's array. Open addressing takes a different approach: everything lives inside the array itself. When a collision occurs, the algorithm searches for the next available slot using a probing sequence. This removes pointer overhead but introduces new problems, notably clustering. These notes cover the three main probing strategies (linear, quadratic, double hashing) and finish with perfect hashing, a special-case technique that eliminates collisions altogether.
Open addressing stores all keys directly in the hash table array. On collision, it probes forward through a sequence of slots until it finds an empty one. Linear probing is simplest but suffers from primary clustering. Quadratic probing reduces that clustering. Double hashing nearly eliminates it by giving each key its own step size. Perfect hashing avoids collisions entirely, but only works when the key set is known in advance and never changes.
Open addressing
A collision resolution family where every record is stored directly in the hash table's array, with no external data structures. When a collision occurs, the algorithm probes other slots in the array according to a defined sequence. Think of it as: if your seat is taken, you walk down the row until you find an empty one.
Probing sequence
The order in which an open-addressing scheme checks slots after a collision. Different probing rules produce different sequences and different performance characteristics.
Linear probing
A probing strategy that checks the next slot sequentially: slot + 1, slot + 2, slot + 3, and so on, wrapping around to the start of the array. In simple terms, you just keep stepping forward one at a time.
Primary clustering
The tendency of linear probing to create long runs of occupied slots. Once a cluster forms, any new key that hashes into it makes the cluster even longer, which makes future collisions more likely. A snowball effect.
Quadratic probing
A probing strategy that spaces out the checks using squared increments: slot + 1², slot + 2², slot + 3², and so on. This breaks up the linear clusters.
Secondary clustering
A milder form of clustering that affects quadratic probing. Keys that hash to the same initial slot follow the same quadratic sequence, so they still compete with each other, even though they no longer form long contiguous runs.
Double hashing
A probing strategy that uses a second, independent hash function to determine the step size between probes. Each key gets its own unique probe sequence, which distributes keys more evenly than linear or quadratic probing.
Perfect hashing
A hash function designed for a static, known set of keys that maps every key to a unique slot with zero collisions. Think of it as a custom-fit index built after you already know every entry.
All records sit in the table array itself. No linked lists, no pointers.
Each slot holds at most one item.
On collision, the algorithm follows a probing sequence to find the next empty slot.
The load factor α must stay below 1.0 (the table cannot hold more elements than it has slots), unlike chaining where α can exceed 1.
Probe sequence: h(k), h(k) + 1, h(k) + 2, ... (all mod m).
On insertion, if h(k) is occupied, check h(k) + 1, then h(k) + 2, wrapping around to slot 0 after slot m − 1.
Worked example:
Table size: 11, hash function h(k) = k mod 11.
Insert keys in order: 10, 22, 31, 4, 15, 28, 17, 88, 59.
10 mod 11 = 10 → slot 10 (empty, placed)
22 mod 11 = 0 → slot 0 (empty, placed)
31 mod 11 = 9 → slot 9 (empty, placed)
4 mod 11 = 4 → slot 4 (empty, placed)
15 mod 11 = 4 → slot 4 occupied → probe slot 5 (empty, placed)
28 mod 11 = 6 → slot 6 (empty, placed)
17 mod 11 = 6 → slot 6 occupied → probe slot 7 (empty, placed)
88 mod 11 = 0 → slot 0 occupied → probe slot 1 (empty, placed)
59 mod 11 = 4 → slot 4 occupied → slot 5 occupied → slot 6 occupied → slot 7 occupied → probe slot 8 (empty, placed)
Notice how 59 required four extra probes. That run of filled slots (4 through 7) is primary clustering in action.
Advantages:
Very simple to code.
Cache-friendly, because probes hit adjacent memory locations.
Works well at low load factors.
Disadvantages:
Primary clustering causes probe sequences to lengthen rapidly as the table fills.
Performance degrades sharply once α exceeds roughly 0.7.
Probe sequence: h(k) + 1², h(k) + 2², h(k) + 3², ... (all mod m).
Instead of stepping one slot at a time, the jumps grow: +1, +4, +9, +16, and so on.
How it helps:
Breaks up the contiguous clusters that linear probing creates.
Keys that collide at different initial slots are far less likely to follow the same path.
Remaining weakness:
Secondary clustering: keys that hash to the same initial slot still follow the identical quadratic sequence, so they pile onto each other.
If the table is more than half full, quadratic probing may fail to find an empty slot at all unless the table size is prime and α ≤ 0.5.
Advantages:
Better distribution than linear probing.
Still relatively simple to implement.
Disadvantages:
Not guaranteed to visit every slot; can fail to insert even when empty slots exist, if the table is too full.
Requires careful choice of table size (prime numbers work best).
Uses two hash functions: h1(k) for the initial slot, h2(k) for the step size.
Probe formula: h(k, i) = (h1(k) + i × h2(k)) mod m, where i = 0, 1, 2, ...
h2(k) must never return 0 (otherwise the probe stays in the same slot forever).
For best results, h2(k) should produce values that are relatively prime to m.
Worked example:
h1(k) = k mod 11, h2(k) = 1 + (k mod 10), table size m = 11.
Each key generates its own step size from h2, so two keys that collide at the same slot will typically probe entirely different sequences.
Why it works well:
Eliminates both primary and secondary clustering, because even keys with the same h1 value usually have different h2 values.
Produces probe distributions close to the theoretical ideal of uniform probing.
Trade-off:
Slightly more expensive per probe (two hash evaluations instead of one).
Requires a well-chosen second function; a poor h2 can reintroduce clustering.
Linear probing: simplest, cache-friendly, but primary clustering hurts at moderate-to-high load factors.
Quadratic probing: reduces primary clustering, still has secondary clustering, needs a prime table size.
Double hashing: best distribution and fewest wasted probes, at the cost of computing a second hash per key.
Designed for a static, known-in-advance set of keys.
Constructs a hash function that guarantees zero collisions, so every lookup is exactly O(1) with no probing.
Construction can be computationally expensive, but once the function is built, lookups are extremely fast.
Only useful when the key set never changes (e.g., reserved words in a programming language, fixed lookup tables).
Linear probing
h(k, i) = (h(k) + i) mod m, for i = 0, 1, 2, ...
Quadratic probing
h(k, i) = (h(k) + i²) mod m, for i = 0, 1, 2, ...
Double hashing
h(k, i) = (h1(k) + i × h2(k)) mod m, for i = 0, 1, 2, ...
Common choice for the second function: h2(k) = 1 + (k mod (m − 1)), where m is prime.
Open addressing is used in performance-critical systems where memory allocation overhead matters, such as embedded systems and game engines. Python's built-in dict historically used a form of open addressing with perturbation-based probing. Perfect hashing shows up in compiler keyword tables, network packet classifiers, and read-only lookup structures where the key set is fixed at build time.
Students often think linear probing is always bad. It is not. At low load factors it is fast, simple, and cache-friendly. The problems only become serious as the table fills up.
Students confuse primary and secondary clustering. Primary clustering is about contiguous runs of filled slots (a linear probing problem). Secondary clustering is about keys sharing the same probe sequence because they share the same initial hash (a quadratic probing problem). They are different phenomena.
Students sometimes assume open addressing allows α > 1. It does not. With one item per slot, you cannot have more items than slots.
Students occasionally forget that deletion in open addressing is tricky. You cannot simply empty a slot, because that would break probe chains. A "deleted" or "tombstone" marker is needed.
⚠️ Expect to be given a table size, a hash function, and a list of keys, then asked to insert them step by step using linear probing, quadratic probing, or double hashing. Practise these by hand until the mod arithmetic is automatic.
⚠️ Be able to identify primary clustering in a linear probing example and explain why it degrades performance.
⚠️ Know the probe formula for each method. The double hashing formula h(k, i) = (h1(k) + i × h2(k)) mod m is a favourite exam question.
⚠️ Understand why h2(k) must be non-zero and ideally coprime to m.
⚠️ Perfect hashing is limited to static key sets. If an exam question describes a changing dataset, perfect hashing is not the right answer.
True or False: In open addressing, the load factor can exceed 1.
Fill in the blank: The clustering problem specific to linear probing is called ______ clustering.
True or False: Quadratic probing guarantees it will find an empty slot if one exists.
Fill in the blank: Double hashing uses a second hash function to determine the ______.
True or False: Perfect hashing works well for datasets that change frequently.
Answers: 1. False (each slot holds at most one item, so α ≤ 1). 2. Primary. 3. False (it may fail if the table is too full or the size is not prime). 4. Step size (between probes). 5. False (it requires a static, known-in-advance key set).
Q: Using linear probing with h(k) = k mod 7 and table size 7, insert keys 14, 21, 7 in that order. Where does each key end up?
A: 14 mod 7 = 0 → slot 0. 21 mod 7 = 0 → slot 0 occupied → slot 1. 7 mod 7 = 0 → slot 0 occupied → slot 1 occupied → slot 2. All three hashed to slot 0, demonstrating primary clustering.
Q: Why does quadratic probing reduce primary clustering compared to linear probing?
A: Because the probe increments grow (1, 4, 9, 16, ...), keys that collide at different initial positions jump to widely separated slots rather than piling into the same contiguous run.
Q: In double hashing, what goes wrong if h2(k) = 0 for some key k?
A: The probe formula becomes h1(k) + i × 0 = h1(k) for every i. The algorithm keeps checking the same slot forever and never finds an alternative, resulting in an infinite loop.
Q: When would you choose perfect hashing over chaining or open addressing?
A: When the set of keys is completely known in advance and will not change. The upfront cost of constructing the perfect hash function is justified by guaranteed O(1) lookups with zero collisions thereafter.
Q: A hash table uses double hashing with h1(k) = k mod 11 and h2(k) = 1 + (k mod 10). For key 33, what is the initial slot and the step size?
A: Initial slot: 33 mod 11 = 0. Step size: 1 + (33 mod 10) = 1 + 3 = 4. So the probe sequence is 0, 4, 8, 1, 5, 9, 2, ... (all mod 11).
Open addressing builds directly on the hash table fundamentals and chaining covered in the companion notes. The clustering problems here connect to broader performance-analysis topics: understanding why data structure performance degrades under certain conditions is a recurring theme in algorithm courses. Double hashing's requirement that h2(k) be coprime to m ties back to number theory concepts (GCD, modular arithmetic) that also appear in cryptography and the RSA algorithm.
open addressing, closed hashing, linear probing, quadratic probing, double hashing, perfect hashing, probing sequence, primary clustering, secondary clustering, tombstone deletion, hash collision, load factor, rehashing, hash table performance, probe formula, coprime, relatively prime, COP 3502, UCF Computer Science I