FKS Perfect Hashing Collision Energy
Use bucket collision energy to turn two-level hashing into collision-free lookup.
By Riano · Published · Updated · Report a correction
FKS Perfect Hashing Collision Energy
The FKS (Fredman, Komlós, Szemerédi) perfect hashing scheme provides a way to construct a static hash table with O(n) space and guaranteed O(1) worst-case lookup time. It achieves this by using a two-level hashing strategy and bounding the collision energy of the first level.
Worked Example
Consider hashing a set of keys into buckets. The sum of the squares of the bucket sizes represents the collision energy. If we have keys [0, 1, 4, 7, 10, 15], so n = 6. We use m = 6 buckets for the first level. Let's compute the first-level hash h(x) = ((1 · x + 0) mod 37) mod 6 for each key:
h(0) = (0 mod 37) mod 6 = 0 h(1) = (1 mod 37) mod 6 = 1 h(4) = (4 mod 37) mod 6 = 4 h(7) = (7 mod 37) mod 6 = 1 h(10) = (10 mod 37) mod 6 = 4 h(15) = (15 mod 37) mod 6 = 3
The resulting buckets are:
| Bucket Index | Keys | Size k | k² (Energy) |
|---|---|---|---|
| 0 | [0] | 1 | 1 |
| 1 | [1, 7] | 2 | 4 |
| 2 | [] | 0 | 0 |
| 3 | [15] | 1 | 1 |
| 4 | [4, 10] | 2 | 4 |
| 5 | [] | 0 | 0 |
The sum of squares of the bucket sizes is 1 + 4 + 0 + 1 + 4 + 0 = 10. Since 10 ≤ 4n (where 4n = 24), we accept this first-level hash function.
Experiment
In the interactive module, you can select different sets of Keys, a Multiplier a, and an Offset b.
- Change the distribution of keys from "Spread" to "Clustered".
- Observe how it drastically increases the collision energy
Limitations
The FKS scheme is designed for a static set of keys, meaning the entire set must be known in advance to construct the two-level table without collisions. It does not efficiently support dynamic insertions, as adding a new key might cause a collision in a secondary table, requiring rehashing of that entire bucket or even the entire primary table. Furthermore, finding a suitable hash function requires randomized trials, meaning the construction time is expected O(n) rather than strictly deterministic O(n).
References
The original paper describing this technique is by Fredman, Komlós, and Szemerédi. For detailed lecture notes on the topic, including the expected space and time complexity proofs, see the MIT course material:https://courses.csail.mit.edu/6.851/spring07/erik/L11.pdf.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive FKS Perfect Hashing Collision Energy module.
Try FKS Perfect Hashing Collision Energy on Riano →