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.

Experiment

In the interactive module, you can select different sets of Keys, a Multiplier a, and an Offset b.

1. Change the distribution of keys from "Spread" to "Clustered".
2. Observe how it drastically increases the collision energy

(the sum of squares of bucket sizes). If the energy exceeds 4n, the first-level hash is rejected and would need a retry. For accepted first-level hashes, the module then computes secondary hash parameters for each bucket to ensure zero within-bucket collisions.