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

Does anyone have a source I could use to learn more about this?
You're missing the (obvious but) unstated caveat of "with high probability", I think.  If you're hashing randomly, there's some chance all items choose the same two buckets.  With high probability, you can get constant load.  I think I recall this was first shown to me by Alan Frieze, but I can't recall the reference.  Cuckoo hashing provides another way of showing this is true.