Skip to main content
2 of 2
added 21 characters in body
Glorfindel
  • 2.8k
  • 6
  • 28
  • 38

information theoretic lower bound for hashing functions

The literature on minimal perfect hashing functions (mphf) says that the best function we can do will have to store $\frac1{\ln(2)}$ (~1.44) bits per key. There are some sets though that require 0 bits per key, eg the key set {apple, banana, cherry} can have a mphf of the form

uint32 getIndex(string key) { return key[0] - 'a'; }

This function doesn't need to store information. Is the lower bound saying that given an arbitrary set there might not exist any mphf that can go lower than 1.44 bits/key but there is guaranteed to exist a mphf which only requires 1.44 bits/key?