# 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. – David Eppstein May 10 '16 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. – templatetypedef May 10 '16 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$." – jbapple Dec 30 '16 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. – pfalcon Oct 6 at 23:26