3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is definitely not obvious. It's confused the heck out of me every time I've read about Cuckoo hashing... in fact I'm not sure if I was ever 100% confident that this was what I was missing, although it did hit me at some point. Part of the reason was that I had no idea (and no one ever told me) exactly how high is this "high probability"? Is it guaranteed to high enough that you don't need to actually handle the edge case in your code when the items aren't known at compile-time, or do you need to have a fallback? If you need to have a fallback, what should it be? etc. $\endgroup$ – Mehrdad May 10 '16 at 4:07
  • $\begingroup$ 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. $\endgroup$ – David Eppstein May 11 '16 at 17:42
1
$\begingroup$

Try Google scholar search for "cuckoo hashing" or https://en.wikipedia.org/wiki/Cuckoo_hashing — that is, the answer to your question is the subject you say you are already reading. Cuckoo hashing is exactly the technique for moving elements to achieve constant load. If you do all the insertions and moves before you do any queries, you get an offline placement scheme.

$\endgroup$
  • 1
    $\begingroup$ My apologies, I should have clarified my question more. I'm familiar with cuckoo hashing and its analysis, but I'm not sure I see how that implies this particular result. After all, it's possible that you end up with a cycle in the cuckoo graph that prevents elements from being distributed properly, which in a normal cuckoo hash table is resolved by rehashing, which isn't permitted in 2-choice hashing. I haven't seen this analysis done in a way that bounds the expected worst-case number of elements in a bucket. Do you know of such a reference / bound? $\endgroup$ – templatetypedef May 9 '16 at 21:14
  • 1
    $\begingroup$ The usual analysis of cuckoo hashing gives high probability of success. When you combine that with the higher load per bucket that you would get in the unlikely event of a failure, you immediately get constant expected max bucket size. $\endgroup$ – David Eppstein May 9 '16 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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