# Why use two separate tables in cuckoo hashing?

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?

• One advantage is that it makes it easier to tell which hash function to use when you're moving a key. Commented May 10, 2016 at 7:27
• @DavidEppstein I suppose that's true, but you'd have to track that anyway when implementing the normal cuckoo hashing displacement algorithm. Commented May 10, 2016 at 7:40
• 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$." Commented Dec 30, 2016 at 19:15

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)$.
• 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. Commented Oct 6, 2019 at 23:26