# Constant-time bounds on offline 2-choice hashing?

I'm reading up on cuckoo hashing and came across Michael Mitzenmacher's blog posts on the subject. In his motivation of why cuckoo hashing seems like a reasonable strategy, he mentions a connection to 2-choice hashing:

In the course of these results [about 2-choice hashing], the question arose as to whether one could do better if placing the elements offline. That is, if you had all n elements and their hashes in advance, could you place each element in one of their bucket choices and achieve a better load than the O(log log n) obtained by the sequential placement? The answer turns out to be yes. The best placement only has a constant maximum load. Another way to think of this is to say that if we place the elements sequentially, but retain the power to move them later, as long as each element ends up at one of its bucket choices, we could get down to constant maximum load.

I found this result really intriguing and have been trying to track down a source on it. However, I can't seem to find any papers on the subject that prove this particular result. I'm aware that cuckoo hashing itself can be thought of as an offline version of 2-choice hashing, but given that cuckoo hashing sometimes fails and requires a rehash, it doesn't seem like the traditional analysis of cuckoo hashing itself would meet the description given above (or does it?)

• The probability of failure (either a genuine inability to place all keys or an insertion that takes more than a logarithmic number of steps) when inserting $n$ keys into a standard (two-hash) cuckoo table is $O(1/n)$. This is small enough to make failures unimportant when analyzing the max expected bucket size of the offline algorithm, but still large enough that you should include some fallback code. You can shrink the failure probability to any inverse polynomial by using either a stash or more hashes. – David Eppstein May 11 '16 at 17:42