Lesson 7

The ideas presented above are used, for example, in the analysis of a perfect hash function, a two-level hashing scheme for a given static set of \(n\) objects, in which there will be no collisions and which uses \(O(n)\) memory. To achieve this, a hash function of size \(n\) is used at the first level. Then the \(n\) objects are distributed into buckets of size \(n_{i}\). If we now choose a random hash function of size \(n_{i}^{2}\) from a universal family at the second level, then on the one hand, with probability at least \(1/2\), there will be no collisions, and on the other hand, the size will be linear: \[\operatorname{E}\left[\sum_{i} n_{i}^{2}\right] < 2n \ .\]