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?

Improve this question
$\endgroup$
3
  • 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
    Commented May 10, 2016 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
    Commented May 10, 2016 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
    Commented Dec 30, 2016 at 19:15

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Dec 30, 2016 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
    Commented Dec 30, 2016 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
    Commented Oct 6, 2019 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
    Commented Oct 6, 2019 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
    Commented Oct 6, 2019 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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