<p>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)$.</p>

CC BY-SA 3.0
2016-12-30T18:02:18.657Z
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?
yberman
CC BY-SA 3.0
2016-12-30T19:30:56.370Z
@YBerman, I don't have such an an analysis. It can complicate the insert code, however, which would need to add backtracking.
jbapple
CC BY-SA 4.0
2019-10-06T18:47:47.047Z
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.
pfalcon
CC BY-SA 4.0
2019-10-06T23:26:10.343Z
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
CC BY-SA 4.0
2019-10-06T23:39:36.017Z
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).
pfalcon
CC BY-SA 3.0
2016-12-21T06:31:33.663Z
2016-12-30T19:28:11.737Z
2016-12-30T19:28:11.737Z
jbapple
<p>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 href="http://www.itu.dk/people/pagh/papers/cuckoo-undergrad.pdf" rel="nofollow">a set of lecture notes aimed at undergraduates where this simplification is used</a>).</p>

<p>Is there any particular reason for this?</p>

CC BY-SA 3.0
2016-05-10T07:27:00.207Z
One advantage is that it makes it easier to tell which hash function to use when you're moving a key.
David Eppstein
CC BY-SA 3.0
2016-05-10T07:40:55.727Z
@DavidEppstein I suppose that's true, but you'd have to track that anyway when implementing the normal cuckoo hashing displacement algorithm.
templatetypedef
CC BY-SA 3.0
2016-12-30T19:15:24.160Z
As noted in the cuckoo hashing journal paper (http://www.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
<ds.data-structures>
Why use two separate tables in cuckoo hashing?
templatetypedef
# Why use two separate tables in cuckoo hashing?

(Asked by: username_0 on 2016-05-10)

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](http://www.itu.dk/people/pagh/papers/cuckoo-undergrad.pdf)).

Is there any particular reason for this?

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: One advantage is that it makes it easier to tell which hash function to use when you're moving a key.  
> **username_0**: @DavidEppstein I suppose that's true, but you'd have to track that anyway when implementing the normal cuckoo hashing displacement algorithm.  
> **username_2**: As noted in the cuckoo hashing journal paper (http://www.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$."  

---

## 1 answers

### Answer by username_2 on 2016-12-21. Score: 5 | Accepted answer

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)$.

> **Comments:**
> **username_3**: 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?  
> **username_2**: @YBerman, I don't have such an an analysis. It can complicate the insert code, however, which would need to add backtracking.  
> **username_4**: 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.  
> **username_4**: 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.  
> **username_4**: 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).  

---

