Let us define a "root universal family" as a family of hash function which for every two items $k_i,k_j$ the probability $P(h(k_i)=h(k_j)) \le \frac{1}{\sqrt m}$ where $m$ is the size of the table.

Now, let us have $|U| = n$ - (the size of the given universe, note that it is perfect hash).

Define an efficient perfect hash algorithm, for which the total sizes of the tables is $\le O(n^2)$.

Now, we note that if we have a table of size $n^2$, then the expected number of collision of a random hash function from that family is $\le \frac{n}{2}$. This is because:

$$\mathbb E[\text{number of collisions}] = \sum_{\{k_i,k_j\} \subset U, k_i\ne k_j}P(h(k_i)=h(k_j)) \le \frac{\binom{n}{2}}{\sqrt {n^2}} \le \frac{n}{2}$$

So, we define the "first-level" hash table to be of size $n^2$. The expected number of hash function we need to draw in order to have less than $n$ collisions is $2$ (since it is a geometric variable).

Now, this is where I get stuck:

After a hash family that satisfies less then $n$ collisions is chosen, for each table that has items colliding, we make a "second-level" table of size $|\text{number of collisions in table}|^4$. (It is easy to prove that in order to get no collisions when the size is $x^4$ we need again two draws for the second function.

The problem I having is showing that all the "second-level" tables + the "first-level" tables are $O(n^2)$ of total size. Would like help in proving that, Thanks!


1 Answer 1


Ok, I managed to prove it:

We note that the total size of the tables = $$n^2 + \sum_i n_i^4$$ where $n^2$ is the first table and $n_i$ is the size of the $i$th index of table with collisions. Therefore we get:

$$n^2 + \sum_i n_i^4 = n^2 +\sum_i (n_i^2)^2 \le n^2 + \sum_i (4\binom{n_i}{2})^2 \le n^2 + 16(\sum_i \binom{n_i}{2}) = n^2 +16(\text{number of collisions})^2 = n^2 + 16n^2 = O(n^2)$$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.