4
$\begingroup$

I've been reading a number of papers on cuckoo hashing, including several that generalize it by talking about cuckoo hashing with multiple tables, cuckoo hashing with a stash, the (multi)graph-theoretic properties of the cuckoo graph, etc. However, I have not seen any papers discuss why cuckoo hashing typically separates out the slots into distinct tables rather than having one larger table with multiple hash functions indexing into it (though I did come across a set of lecture notes aimed at undergraduates where this simplification is used).

Is there any particular reason for this?

$\endgroup$
  • 3
    $\begingroup$ One advantage is that it makes it easier to tell which hash function to use when you're moving a key. $\endgroup$ – David Eppstein May 10 '16 at 7:27
  • $\begingroup$ @DavidEppstein I suppose that's true, but you'd have to track that anyway when implementing the normal cuckoo hashing displacement algorithm. $\endgroup$ – templatetypedef May 10 '16 at 7:40
  • $\begingroup$ As noted in the cuckoo hashing journal paper (it-c.dk/people/pagh/papers/cuckoo-jour.pdf), "The following trick due to John Tromp [38] can be used in this case to avoid keeping track of the hash function according to which each key is placed: If we change the possible locations for key $x$ to be $h_1(x)$ and $(h_2(x) − h_1(x)) \bmod 2r$, we can jump from one location of $x$ to the other using the map $i \mapsto (h_2(x) − i) \bmod 2r$." $\endgroup$ – jbapple Dec 30 '16 at 19:15
5
$\begingroup$

One reason is that when there is only one set of slots, there will be some keys such that $h_1(k) = h_2(k)$.

$\endgroup$
  • $\begingroup$ Out of curiousity, could you describe a scenario where this makes the scheme worse in the one table variant, where the single table is twice the size? $\endgroup$ – yberman Dec 30 '16 at 18:02
  • 2
    $\begingroup$ @YBerman, I don't have such an an analysis. It can complicate the insert code, however, which would need to add backtracking. $\endgroup$ – jbapple Dec 30 '16 at 19:30
  • $\begingroup$ Reading analysis would be indeed nice. But trying it empirically, with one table, insert indeed "deadlocks" much easier than with 2 tables, in particular due to issue described in this answer. $\endgroup$ – pfalcon Oct 6 at 18:47
  • $\begingroup$ Actually, I probably played with buggy code before. Now, with a naked eye, I can't really see a difference in behavior of classical algo with 2 tables, or mod with 1 table. Nor I see much difference with explicit attempts to de-correlate 2 hash functions (if (h2 == h1) h2++) or not. $\endgroup$ – pfalcon Oct 6 at 23:26
  • $\begingroup$ So, the only tangible difference appears to be that in 2-table scheme, you calc 1 hash func per kicked-off item, whereas in 1-table scheme, for some of items, you'd need to calc 2 (first to probe by which it was placed, then if you missed, the other one for next position). $\endgroup$ – pfalcon Oct 6 at 23:39

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.