Suppose we have a universe of $ u=|U|$ elements. We called a set of $ H$ function $ (U,m)$ order-preserving minimal perfect hash family (OPMPHF) if for every subset $ M\subset U$ of size $ m$ has at least one function $ h\in H$ which is an over preserving minimal prefect hash. It is shown in [1,2] that for every

$ (U,m)$ -OPMPHF $ H$ obeys:

$ $ H=m! \cdot {u \choose m}/(\frac{u}{m})^m $ $

Thus, the program length for any order preserving minimal perfect hash function should contain at least $ \log_2 |H|$ bits.

In partiular, if $ m=3,u=8$ , we have that $ |H|\geq 17.7$ .

However, I think I can create as set of $ |H|=6$ functions for such family. For every $ 2\leq i\leq 7$ we define $ f_i(x)$ to be equal $ 1$ if $ x<i$ , equal $ 2$ if $ x=i$ and equal $ 3$ if $ x\geq i$ . Every function $ f_i$ is order-preserving, and for each set $ M$ with second element $ i$ has a perfect function $ f_i$ .

Do I miss something in my analysis?

[1]- http://160592857366.free.fr/joe/ebooks/ShareData/Optimal%20algorithms%20for%20minimal%20perfect%20hashing.pdf [2]-K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1. Springer-Verlag, Berlin Heidelberg, New York, Tokyo, 1984