information theoretic lower bound for hashing functions [closed]

Question

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?

Answer 1

The constant 1.44 is an approximation to $\log_2 e.$ All logs are to base 2 in the rest of this answer.

The lower bound due to Fredman and Komlos 1 (1984) goes as follows. For a MPHF (in the worst case over all sets of size $n$) provided $u\geq n^a,$ for some $a>2,$ at least $$ n \log e + \log \log u - O(\log n)\sim 1.44 n, $$ bits are required. So given an arbitrary set we know that there is no MPHF with lower number of storage.

There are constructions approaching this lower bound but usually they either require exponential time co construct and evaluate or require near-optimal space only asymptotically.

There is a 2007 paper by Botelho, Pagh and Ziviani [2] (see also here) where an efficient construction is given where

1. The evaluation of the PHF requires constant time
2. The algorithms are simple to implement and run in linear time
3. The amount of space is a factor of 2 worse than the information theoretic minimum

References:

1. Fredman, M.L., Koml´os, J.: On the size of separating systems and families of perfect hashing functions. SIAM Journal on Algebraic and Discrete Methods 5, 61–68 (1984)

2. Botelho, F.C., Pagh, R. and Ziviani, N.: Simple and Space-efficient Minimal Perfect Hash Functions. in F. Dehne, J.-R. Sack, and N. Zeh (Eds.): WADS 2007, LNCS 4619, pp. 139–150, 2007