Cuckoo Hashing
2001 · paper · Computer science
Presents cuckoo hashing, a simple dictionary data structure with worst-case constant lookup time and space of about three words per key. Experiments show it is competitive with known methods on average.
Checked: PDF from brics.dk, fetched 4 Oct 2026. Page numbers are those of that PDF.
7 findings
Substance Section 2 states that a function with range {0,1}^{2 log(n)+c} "will, with probability 1 − O(2^c), be injective on S". The exponent should be −c, i.e. 1 − O(2^{−c}).
- p. 7 Section 2, paragraph after Theorem 1
will, with probability 1 − O(2c), be injective
- p. 7 Section 2, paragraph after Theorem 1
with probability 1 − O(2^c), be injective
- p. 7 Section 2, paragraph on longer keys
with probability 1 −O(2c)
Judge's note: Page 7 image (printed p. 5): the exponent on 2 is a plain c with no minus sign, while the same paragraph prints O(2^{−c/2}) with its minus. My own check: with (O(1),2)-universality, the expected number of colliding pairs is at most C(n,2)·O(1)/2^{2 log n + c} = O(2^{−c}). The failure probability therefore falls as c grows. As printed, 1 − O(2^c) is not a valid probability bound for growing c. The paragraph's later amortised cost O(2^{−c/2}) is consistent with the 2^{−c} reading.
Second check: another model agreed
Report a problem with this finding
Substance P.16 (PDF p18): "The curve for Cuckoo Hashing seems to be 2 + 1/(4 + 8α) ≈ 2 + 1/(4ϵ)". As printed, the expression decreases in α. That contradicts the rising Cuckoo curve in Figure 5 and the stated ≈ 2 + 1/(4ϵ). The denominator should evidently be 4 − 8α.
- p. 18 Text below Figure 5
to be 2 + 1/(4 + 8α) ≈ 2 + 1/(4ϵ)
- p. 18 Figure 5, Cuckoo curve
Cache Misses
- p. 18 Section 4.3, cache misses during insertion
2 + 1/(4 + 8α) ≈ 2 + 1/(4ϵ)
Judge's note: I viewed p18. The image clearly shows '4 + 8α'. The load factor is defined (p11) as set size relative to memory used, so α = n/(2r) = 1/(2(1+ϵ)). Then 4 − 8α = 4ϵ/(1+ϵ) ≈ 4ϵ, while 4 + 8α ≈ 8 near α = 1/2. With the + sign the value falls from 2.25 at α = 0 to 2.125 at α = 1/2. In Figure 5 the Cuckoo circles rise from about 2.2 at α = 0.1 to about 3.7 at α ≈ 0.46. With the − sign the values are 2.6 at 0.3, 3.25 at 0.4 and 4.5 at 0.45, which roughly track the plotted points.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [3]: "Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '90), pages 43–53. ACM Press, New York, 2000." The year 2000 contradicts 'SODA '90' in the same entry.
- p. 21 Reference [3]
(SODA '90), pages 43–53. ACM Press, New York, 2000.
- p. 21
pages 4353. A CM Press, New Y ork, 2000.
Judge's note: I viewed p21. The entry labels the venue SODA '90 (the 1st) but gives the year 2000. Reference [25] in the same list gives 'SODA '00 ... 2000', so the paper's own labelling convention ties '90 to 1990. The inconsistency is internal to the entry; the evident fix is 1990.
Second check: another model agreed
Report a problem with this finding
Wording Section 3.1.1 defines "let l be the minimum index such that l + 1 > j and x_{l+1} ∈ X_{1,l}". When i > 1 this picks l = j, but the argument and Figure 2 need l ≥ i + j − 1.
- p. 9 Section 3.1.1, definitions
let l be the minimum index such that l + 1 > j and xl+1 ∈ X1,l
- p. 11 Section 3.1.1
Thus we have xj+z = xi−z for z = 0, 1, . . . , i − 1
Only the authors can say what is right here.
Judge's note: Checked on page 9 and page 11 images. My reworking: page 11 states x_{j+z} = x_{i−z} for z = 0,…,i−1. For i > 1, z = 1 gives x_{j+1} = x_{i−1}, which is in X_{1,j}. So l = j meets both printed conditions (j+1 > j, and x_{j+1} ∈ X_{1,j}), and the minimum l is j. The proof, however, uses keys x_{i+j},…,x_l and the count |X_{1,l}| = l+1−i, which need l ≥ i+j−1. A lower bound such as l ≥ i+j−1 seems to be intended. The theorem itself is not affected.
Second check: another model agreed
Report a problem with this finding
Wording Section 3.1.1 states "In conclusion, |X_{1,l}| = l + 1 − i", but by the stated repetition structure the count is l − i. The printed chain then gives only s_l ≤ l − i = |X_{1,l}|, which is not the strict deficit the proof needs.
- p. 11 Section 3.1.1, last paragraph
In conclusion, |X1,l| = l + 1 − i
Only the authors can say what is right here.
Judge's note: Read on the page 11 image and reworked myself. The keys x_1..x_{j−1} are distinct (j−1 keys). The keys x_j..x_{i+j−1} are i repeats. The keys x_{i+j}..x_l are new (l−i−j+1 keys). The total is (j−1)+(l−i−j+1) = l−i. Check with i=1, j=4, l=4: X_{1,4} = {x1,x2,x3}, size 3, while the printed formula gives 4. The printed chain is s_l ≤ s_{j−2}+l+1−j−i with s_{j−2} ≤ j−1, so s_l ≤ l−i: equal to the true |X_{1,l}|, not below it. Using s_{j+i−1} = s_{j−2} (since X_{1,j+i−1} = X_{1,j−1}) gives s_l ≤ l−i−1 < l−i. That repairs the step, so the result stands.
Second check: another model agreed
Report a problem with this finding
Wording In Equation (3), "1+Σ_{t=2}^∞ 2c(1+ϵ)^{−(2t−1)/3+1} = 1 + 2c(1+ϵ)^{4/3} Σ_{t=0}^∞ ((1+ϵ)^{−2/3})^t" is joined by '=', but the right side is strictly larger. It should be '≤'.
- p. 11 Equation (3)
= 1 + 2c(1 + ϵ)4/3
Only the authors can say what is right here.
Judge's note: Checked on the page 11 image. The exponent is −(2t−1)/3+1 = 4/3 − 2t/3, so each term equals 2c(1+ϵ)^{4/3}q^t with q = (1+ϵ)^{−2/3}. Rewriting the t ≥ 2 sum with the prefactor kept but the sum started at t = 0 adds the positive t = 0 and t = 1 terms. Exact equality would need either the prefactor dropped or the sum kept from t = 2. The final O(1+1/ϵ) bound is unaffected.
Second check: another model agreed
Report a problem with this finding
Wording P.17 (PDF p19): "This means that R and T are the only parameters not dependent on the methods used." But R is read from Figure 5 "for the various hashing schemes", so it depends on the method. The parameters described as independent and well known are C and T.
- p. 19 Section 5, second paragraph
This means that R and T are the only parameters not dependent on the methods used.
Only the authors can say what is right here.
Judge's note: I viewed p19. The same section says: "The size C of the cache and the size T of the dictionary are well known. From Figure 5 we can, for the various hashing schemes ... read the average number R". Figure 5 gives different values for each scheme. The sentence most likely means C and T. It could instead mean that R and T are known and not estimated, so the authors should confirm.
Second check: another model agreed
Report a problem with this finding
20 minor (typos and the like; most checked by the judge only)
Reference or label Reference [1] (Andersson, Miltersen, Riis, Thorup, "Static dictionaries on AC0 RAMs ...") appears in the reference list but is never cited in the text.
- p. 21 Reference [1]
Arne Andersson, Peter Bro Miltersen, Søren Riis, and Mikkel Thorup.
Judge's note: I searched the layout text for '[1]', '[1,' and any bracketed list containing 1. The only hit is the reference-list entry itself. I did not scan every body page image, but the text layer reliably preserves the other bracketed citations ([2], [3], [17] and so on). An uncited bibliography entry is a minor consistency point.
Second check: another model agreed
Report a problem with this finding
Wording Section 2 (p.5) says "For c = O(log n) the new keys are of length 2 log n + O(1)", but the keys have range {0,1}^{2log(n)+c}, so their length is 2 log n + O(1) only when c = O(1).
- p. 7 Section 2, end of universe-reduction paragraph
For c = O(log n) the new keys are of length 2 log n + O(1).
- p. 7 Section 2
For c = O(log n)
Only the authors can say what is right here.
Judge's note: Checked on page 7 image. The function's range is {0,1}^{2 log(n)+c}, so the new key length is 2 log n + c. The sentence just before reduces the universe to O(n^2), which also needs c = O(1). With c = O(log n) the length is 2 log n + O(log n). So the condition and the conclusion in the printed sentence disagree. Only the authors can say whether they meant 'c = O(1)' or a length of O(log n).
Second check: another model agreed
Report a problem with this finding
Wording Section 3.1.1 says "the number of cells is not sufficient to accommodate X_{i,l}", but the formal proof that follows compares s_l with |X_{1,l}|, so X_{1,l} seems to be meant.
- p. 11 Section 3.1.1, second paragraph
not sufficient to accommodate X_{i,l}
Judge's note: The page 11 image shows subscript 'i,l' in the prose. The proof defines s_k as the cells available to X_{1,k} and concludes with |X_{1,l}|. X_{i,l} = {x_i..x_l} is a different set, and the argument does not use it.
Second check: another model agreed
Report a problem with this finding
Wording The Growing and Shrinking Dictionaries test opens with "The third test concerns the cost of insertions...", although the only test described before it is "Our first test" (stable size). No second test is identified.
- p. 16 Growing and Shrinking Dictionaries
The third test concerns the cost of insertions in growing dictionaries
- p. 15 Dictionaries of Stable Size
Our first test was designed to model
- p. 16
The third test concerns the cost of insertions in gro wing
Only the authors can say what is right here.
Judge's note: Page 15 image: 'Our first test was designed to model...'. Page 16 image: 'The third test concerns...', followed by the unnumbered DIMACS tests. A text search found no 'second test' anywhere, and page 18 (cache-miss experiments) is not numbered as a test either. The numbering is inconsistent; only the authors can say whether a test is missing or the label is wrong.
Second check: another model agreed
Report a problem with this finding
Wording P.14 (PDF p16): "During deletions all schemes had average load factor 0.28. Again the fastest method is Linear Probing, followed by Chained Hashing and Cuckoo Hashing." In the Figure 4 Delete panel, though, Cuckoo (circles) is below Chained Hashing (squares) for large n.
- p. 16 Growing and Shrinking Dictionaries
followed by Chained Hashing and Cuckoo Hashing
- p. 17 Figure 4, Delete panel
Delete
Only the authors can say what is right here.
Judge's note: I viewed the p16 text and the Figure 4 crop and full page. In the Insert panel the order for large n is Linear < Chained < Cuckoo < Two-Way, which matches the text. In the Delete panel, from log n ≈ 16 upward, the circles (Cuckoo, about 545–660) sit below the squares (Chained, about 590–710). For deletions the order is Linear, Cuckoo, Chained. The sentence comes straight after the deletion statistics, so it reads as covering deletions too. It may have been meant for insertions only. The authors should say which.
Second check: another model agreed
Report a problem with this finding
Typo Stray word in Section 1: "the expected time for all operations can be made a within a factor of (1 + ϵ) from optimal".
- p. 4 Section 1, first paragraph
can be made a within a factor of (1 + ϵ)
- p. 4 Section 1, paragraph 2
can be made a within a factor of (1 + ϵ) from optimal
Judge's note: Checked the page 4 image. The printed text reads "can be made a within a factor of (1 + ϵ)". The extra "a" is in the typeset text, so it is not an extraction artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling in Section 1.1.1: "the expected number of memory probes for succesful and unsuccessful lookups" (should be 'successful').
- p. 5 Section 1.1.1, Linear Probing
memory probes for succesful
- p. 5 Section 1.1.1, Linear Probing paragraph
expected number of memory probes for succesful
- p. 5 Section 1.1.1
succesful
Judge's note: Page 5 image, Linear Probing paragraph: the word is printed as "succesful".
Second check: none (judge only)
Report a problem with this finding
Typo Typo in Section 1.1.2: "Is seems that recent experimental work" (should be 'It seems'). The same review note also lists "bacause" (p. 13) and "accomodated" (Fig. 1 caption, p. 8).
- p. 6 Section 1.1.2, third paragraph
Is seems that recent experimental work
- p. 5 Section 1.1.1
succesful
- p. 6 Section 1.1.2
strucures
- p. 6 Section 1.1.2
Is seems that recent
Judge's note: Page 6 image: the paragraph begins "Is seems that recent experimental work on 'classical' dictionaries". The p. 13 crop shows "bacause we expect" and the Fig. 1 caption crop shows "cannot be accomodated"; both are real misspellings. The text layer also contains 'preceeding' and 'Algoritm'. 'succesful' and 'strucures' are judged under C003 and C014.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling in Section 1.1.2: "versions of the data strucures with packed representations" (should be 'structures').
- p. 6 Section 1.1.2
versions of the data strucures with packed
- p. 6 Section 1.1.2
data strucures
- p. 6
data strucures with
Judge's note: Page 6 image, Silverstein paragraph: the word is printed as "strucures".
Second check: none (judge only)
Report a problem with this finding
Typo Theorem 1 (Siegel) has a stray comma: "There is a constant c such that for, k = 2^{Ω(w)}, there exists ...".
- p. 7 Theorem 1 (Siegel)
such that for, k = 2Ω(w)
Judge's note: The page 7 image shows the comma between 'for' and 'k'.
Second check: none (judge only)
Report a problem with this finding
Typo The Figure 1 caption has a misspelling: "(b) Key x cannot be accomodated and a rehash is necessary." It should read 'accommodated'.
- p. 8 Figure 1 caption
accomo dated
Judge's note: The page 8 image shows 'accomodated' in the caption, with one 'm'. The gaps between letters are an extraction artefact, but the missing 'm' is real.
Second check: none (judge only)
Report a problem with this finding
Typo Section 3.1.1 has a misspelling: "The topmost configuration is the one preceeding the insertion of x1." It should read 'preceding'.
- p. 9 Section 3.1.1
the one preceeding the insertion of x1
- p. 8 Figure 1 caption
Key x cannot be accomodated
- p. 9 Section 3.1.1
preceeding
- p. 9
preceeding the insertion
Judge's note: The page 9 image shows 'preceeding'. The 'accomodated' item in this cluster is the same defect as C018 and is counted there.
Second check: none (judge only)
Report a problem with this finding
Typo Section 3.1.2 has a misspelling: "If there is no repetion this is obvious." It should read 'repetition'.
- p. 11 Section 3.1.2
If there is no repetion this is obvious.
Judge's note: The page 11 image shows 'repetion'.
Second check: none (judge only)
Report a problem with this finding
Typo "[17, Algoritm R]" appears twice (p.10 Linear Probing description, p.12 Linear Probing implementation). It should read 'Algorithm R'.
- p. 12 Section 4, Linear Probing
see [17, Algoritm R] for details
- p. 14 Section 4.1, Linear Probing
in [17, Algoritm R] was considerably faster
- p. 12 Linear Probing paragraph
Algoritm R
- p. 12
Algoritm R]
Judge's note: The page 12 and page 14 images both show 'Algoritm R'.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4.1 has a subject-verb disagreement: "slightly faster versions of the insertion procedure is used". It should read 'are used'.
- p. 12 Section 4.1
slightly faster versions of the insertion procedure is used
Judge's note: The page 12 image shows the sentence as quoted.
Second check: none (judge only)
Report a problem with this finding
Typo The Chained Hashing paragraph has a misspelling: "every non-empty chained list is one element shorter and bacause we expect". It should read 'because'.
- p. 13 Section 4.1, Chained Hashing
shorter and bacause we expect
- p. 13 Chained Hashing paragraph
bacause
- p. 13
bacause w e exp ect more
Judge's note: The page 13 image shows 'bacause'.
Second check: none (judge only)
Report a problem with this finding
Typo P.16 (PDF p18): "This is in good correspondance with (3)" should read "correspondence".
- p. 18 Text below Figure 5
This is in good correspondance with (3)
Judge's note: The p18 image shows 'correspondance'. It is a misspelling.
Second check: none (judge only)
Report a problem with this finding
Typo P.17 (PDF p19): "the two parameters were estimated for time timings with 2^16 ≤ T ≥ 2^23". The second inequality should evidently be ≤ (2^16 ≤ T ≤ 2^23), and "time timings" should be "the timings".
- p. 19 Section 5, last paragraph
estimated for time timings with 216 ≤ T ≥ 223
- p. 19 Section 5, last paragraph
estimated for time timings
- p. 19 Section 5
2 16 ≤ T ≥ 223
- p. 19 Section 5, last paragraph
with 216 ≤T ≥223
Judge's note: The p19 image shows '2^16 ≤ T ≥ 2^23' with ≥ in the second position, so this is not an extraction artefact. It also shows 'for time timings'. The text is about excluding the largest sets, so the intended range is bounded above. Both are typographical slips with evident fixes.
Second check: none (judge only)
Report a problem with this finding
Typo P.17 (PDF p19): "Note that the model in not valid when the table size T is smaller than the cache size C." Here 'in' should be 'is'.
- p. 19 Section 5
Note that the model in not valid when the table
- p. 19 Section 5, paragraph after the parameter list
Note that the model in not valid
- p. 19 Section 5, after Eq. (4)
Note that the model in not valid when the table size T is smaller than the cache size C.
Judge's note: The p19 image shows 'the model in not valid'. It is a typo.
Second check: none (judge only)
Report a problem with this finding
Typo The RS-01-32 entry in the BRICS report listing on PDF page 24 reads "9th Annual European Symposiumon on Algorithms"; it should read "Symposium on".
- p. 24 RS-01-32 entry
Symposiumon on Al-
Judge's note: Looked at crop C048-a. The run-together word "Symposiumon" followed by "on" is printed in the image, so it is not an extraction artefact. The error is in the BRICS back-matter listing (page 24, which is in scope), not in the paper's body. It is a cosmetic typo.
Second check: none (judge only)