I’m trying to construct a hash table in which we store $ n$ items using $ n(1+\epsilon)$ space. Lookups should be worst case $ O(1)$ and insertion/deletion should be $ O(1)$ in expectation.

*Thoughts:* The idea is to have a main table that is size $ n$ . We use the power of $ d$ choices to find a cell for a given item. Let the max capacity per cell in the main table be a constant $ c$ . We hash the item with $ d$ different hash functions and place the item in the cell with the most room. If that fails (that is, no cells have room), we move the item to an overflow table that is size $ n\epsilon$ for $ 0 < \epsilon < 1$ . The overflow table will use Cuckoo hashing. I need to find a $ d$ and $ c$ for which this works.

Cuckoo hashing works well when the load factor is under $ 1/2$ . That means with $ n\epsilon$ space, we should never move more than $ \frac{n\epsilon}{2}$ items from the main table into the overflow table. We need to pick $ d$ such that the number of collisions greater than $ c$ is at most $ \frac{n\epsilon}{2}$ .

I’m not sure where to go from here (or if I’m on the right track). Any help is appreciated.