A $(n,k)$-perfect hashing family is a family of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $H_S$ is injective on $S$.

There are known (deterministic) builds of such family of size $O(e^{k+log^2k}log n)$, while there is a $\Omega(e^k \cdot \frac{log n}{\sqrt k})$ lower bound , which is almost tight.

I'm looking at a slight variation of this, and require that for every (ordered) sequence $X=<x_1,x_2,...,x_k>$ such that $\forall i\neq j:x_i\in [n],x_i\neq x_j$, there exists some $h_S$ such that $\forall i\in [k]: h(x_i)=i$.

Showing a small (of size $O(k^{k+1} \log n)$) family exists is quite simple:

The probability that such random $h$ satisfies the condition for $X$ is $k^{-k}$, and there are $\frac{n!}{(n-k)!}$ such vectors, so if I pick a random set of $r$ functions the chance that any $X$ was left uncovered is at most (union bound)

$$ (1-k^{-k})^r\frac{n!}{(n-k)!} < (1-k^{-k})^r\cdot n^k < n^ke^{rk^{-k}}$$

Now we can demand that the probability will be strictly smaller than 1 (which means that family of size $r$ exists), we get: $$r > k^{k+1}\text{log}n$$

What is the smallest ordered perfect hashing family we can build deterministically?

  • 1
    $\begingroup$ What is a reference on the $O(e^{k+\log^2k}\log n)$ upper bound (and the lower bound)? $\endgroup$ May 18, 2015 at 15:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.