Perfect Hashing in an Imperfect World - Joaquín M. López Muñoz

Unlike regular hash functions, so-called perfect hash functions guarantee that no collisions ever happen, that is, every two distinct keys map to different hash values, which allows for the construction of hash tables with strict O(1) performance. This seemingly impossible feat comes with the tradeoff that the set of elements must be known in advance prior to table initialization. In this talk we'll review the basics of perfect hashing theory, explain some of the most common algorithms found in the literature, review some C++ perfect hashing libraries and learn how perfect hashing can be used to improve the efficiency of our programs.