# Limit on table size - perfect hashing

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

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)$$