Cuckoo hashing

Kuckucks hashing ( English cuckoo hashing ) is an algorithm , by means of two hash functions to index into a table computed at which the member is to be inserted. It was developed in 2001 by Rasmus Pagh and Flemming Friche Rodler. It gets its name from the cuckoo , which lays its eggs in strange nests and whose chicks push the eggs of the host parents out of the nest.

functionality

Each of the two hash functions calculates the index of an element to be inserted for a table. First it is checked whether the element to be inserted can be inserted into the table at the point with the hash function . If this is the case, the element is inserted there. However, if the space is already occupied, the space in the second table is calculated with the second hash function and, if it is free, inserted there. However, if the space is also occupied, the element to be inserted is inserted into the first table and the element that was there before is moved to the second table. If a collision occurs there again, the element is moved from there to the first table. If the space in the first table is free, the insertion is finished. If, however, an element occupies the space again here, it is moved back to the second table. This procedure is repeated until a free space is found. However, it can happen that the same table constellation occurs as at the beginning, so that the process then gets into a cycle (endless loop). In this case, the table is rebuilt with new hash functions. ${\displaystyle h}$ ${\displaystyle h(k)}$ ${\displaystyle h'(k)}$

Pseudocode

Insert(T1,T2,x):
    // key[x] schon in Hashtabelle?
    if T1[h1(key[x])]=NIL or key[T1[h1(key[x])]]=key[x] then
        T1[h1(key[x])]←x; return
    if T2[h2(key[x])]=NIL or key[T2[h2(key[x])]]=key[x] then
        T2[h2(key[x])] ←x; return
    // nein, dann einfügen
    while true do
        x↔T1[h1(key[x])] // tausche x mit Pos. in T1
        if x=NIL then return
        x↔T2[h2(key[x])] // tausche x mit Pos. in T2
        if x=NIL then return

example

The following hash functions are given:

• ${\displaystyle h\left(k\right)=k\mod 11}$
• ${\displaystyle h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor \mod 11}$

k	h (k)	h '(k)
20th	9	1
50	6th	4th
53	9	4th
75	9	6th
100	1	9
67	1	6th
105	6th	9
3	3	0
36	3	3
39	6th	3

1. Table for h (k)
	20th	50	53	75	100	67	105	3	36	39
0
1					100	67	67	67	67	100
2
3								3	3	36
4th
5
6th		50	50	50	50	50	105	105	105	50
7th
8th
9	20th	20th	20th	20th	20th	20th	53	53	53	75
10

2. Table for h '(k)
	20th	50	53	75	100	67	105	3	36	39
0										3
1							20th	20th	20th	20th
2
3									36	39
4th			53	53	53	53	50	50	50	53
5
6th				75	75	75	75	75	75	67
7th
8th
9						100	100	100	100	105
10

cycle

If you want to insert element 6, you get into a cycle. The last line of the table shows the same initial situation as at the beginning.

• ${\displaystyle h\left(6\right)=6\mod 11=6}$
• ${\displaystyle h'\left(6\right)=\left\lfloor {\frac {6}{11}}\right\rfloor \mod 11=0}$

considered key	Table 1		Table 2
	old value	new value	old value	new value
6th	50	6th	53	50
53	75	53	67	75
67	100	67	105	100
105	6th	105	3	6th
3	36	3	39	36
39	105	39	100	105
100	67	100	75	67
75	53	75	50	53
50	39	50	36	39
36	3	36	6th	3
6th	50	6th	53	50

Individual evidence

1. ^ Rasmus Pagh, Flemming Friche Rodler: Cuckoo Hashing . 2001 ( cs.tau.ac.il (PDF)).