-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathcuckoo.html
83 lines (82 loc) · 13.5 KB
/
cuckoo.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<link href="https://adriann.github.io/feed.rss" rel="alternate" type="application/rss+xml" title="What's new on adriann.github.io" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="generator" content="pandoc" />
<meta name="author" content="Adrian Neumann ([email protected])" />
<title>Cuckoo Hashing</title>
<style type="text/css">
.displayequation{margin-left:auto;margin-right:auto;}
</style>
<style>
.caption{font-size:66%;text-align:right;}
.figure{float:right;padding-bottom:1em;padding-left:1em;}
.figure>img{display:block;margin:0 auto;}
.footnotes{font-size:80%;}
.block{border-left:1ex solid gray;padding-left:2em;}
li{padding:0.25em;}
a:hover{text-shadow: 0 0 5px;}
body{font-family:sans-serif;max-width:100ex;padding-left:3em;padding-right:2em;}
code{font-family:Consolas, Inconsolata, Monaco, monospace;}
p{text-align:justify;}
</style>
</head>
<body>
<div id="header">
<h1 class="title">Cuckoo Hashing</h1>
</div>
<div class="figure">
<img src="pictures/Cuculus_canorus_vogelartinfo.jpg" title="Common Cuckoo from Wikimedia Commons" />
</div>
<p>Hashing is a popular way to implement associative arrays. The general idea is to use one or more <em>hash functions</em> to map a very large universe of items <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>U</mi><annotation encoding="application/x-tex">U</annotation></semantics></math> down to a more compact set of positions in an array <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>A</mi><annotation encoding="application/x-tex">A</annotation></semantics></math>, the so called hash table. Typically one assumes that the hash function is picked randomly and distributes the items uniformly among the possible positions. In practice this is of course not the case as such a function would have enormous storage requirements, however one can get close enough to make the assumption valid.</p>
<p>As one inserts more and more items in the hash table, it becomes <a href="http://en.wikipedia.org/wiki/Birthday_paradox">increasingly more probable</a> that two items are mapped to the same position–a collision occurs. There are many different strategies to deal with this problem. The simplest is probably <em>chaining</em> where one stores a list of items at every position. This clearly yields constant worst case insertion time. For retrieval, the correct list is found by a hash calculation followed by a linear search through the list to return the correct item. It is very easy to show that the lists are of constant length in expectation, as long as the occupancy ratio of the hash table, i. e. the ratio items/positions, remains bounded. A balls-into-bins argument and a little more calculation shows<a href="#fn1" class="footnoteRef" id="fnref1"><sup>1</sup></a> that the expected worst case retrieval time is <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false" form="prefix">(</mo><mo>log</mo><mi>n</mi><mi>/</mi><mo>log</mo><mo>log</mo><mi>n</mi><mo stretchy="false" form="postfix">)</mo></mrow><annotation encoding="application/x-tex">O(\log n/\log \log n)</annotation></semantics></math>.</p>
<p>Hashing with chaining is already pretty efficient and very easy to implement, making it quite popular. For example the OpenJDK <a href="http://www.docjar.com/html/api/java/util/Hashtable.java.html">Hashtable implementation</a> uses this method.</p>
<p>In this post we will explore the performance of a relatively recent<a href="#fn2" class="footnoteRef" id="fnref2"><sup>2</sup></a> variation of hashing called <em>cuckoo hashing</em>. Here one uses two independent hash functions <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo>,</mo><mi>g</mi></mrow><annotation encoding="application/x-tex">f, g</annotation></semantics></math> to give every item two possible positions. For retrieval we simply check both locations, so the worst case retrieval time is improved to a constant. This can even be done in parallel.</p>
<p>The name cuckoo hashing stems from the way we deal with collisions. If the first position is already occupied, the old item is kicked out, very much like the nestmates of young cuckoos, and tries settling at its alternative position. If that is also occupied, the current item is again kicked out. This process repeats until one item finds a free position.</p>
<p>It is not clear that this procedure always terminates, or, if it does, how long it takes. We will find a bound on the maximal occupancy of the table that still guarantees termination.</p>
<!-- more -->
<h4 id="termination">Termination</h4>
<p>Before we look at the performance of the greedy insertion algorithm that I outlined above, let us first try to find an easy bound on the maximal occupancy.</p>
<p>Consider the bipartite graph of items on the left and hash table positions on the right. Every item has two possible positions to which can be assigned. Clearly a successful insertion of all items is equivalent to computing a left-perfect matching in this graph. If there is no such matching, the greedy algorithm can’t terminate.</p>
<p>A simple necessary condition for the existence of a matching is that for any subset of items we have a sufficient number of positions available. A famous result, the “Marriage Theorem” by Hall in 1935, shows this condition to be sufficient too.</p>
<p>A different way to look at this is to consider the graph in which table positions are vertices and there is an edge between two vertices when we need to insert an item that maps to them. Usually this graph is called the <em>cuckoo graph</em>. We seek a matching of edges to vertices. By Hall’s theorem it exists if and only if there is no subgraph that has more edges than vertices.</p>
<div class="figure">
<img src="pictures/dense_subgraphs.png" alt="These graphs are too dense." />
<p class="caption">These graphs are too dense.</p>
</div>
<p>We want to use the first moment method to find a bound for the appearance of such subgraphs. Hence we have to calculate their expected number. There are many graphs with more edges than vertices, too many to tackle the expectation with our limited knowledge of probability theory. Luckily we can make a clever observation. If there are no subgraphs with more edges than vertices, there can’t be subgraphs with exactly one more edge than vertices.</p>
<p>There are only two types of these graphs, see the figure to the right. Both can be characterized by three numbers. Either the length of the three paths, or the size of the two cycles and the length of the connecting path. As all of these numbers must be smaller than <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math>, there can be at most a cubic number of forbidden subgraphs. If we simplify the problem a little<a href="#fn3" class="footnoteRef" id="fnref3"><sup>3</sup></a> and consider the graph to be a <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msub><mi>G</mi><mrow><mi>n</mi><mo>,</mo><mi>p</mi></mrow></msub><annotation encoding="application/x-tex">G_{n,p}</annotation></semantics></math>, a random graph on <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>n</mi><annotation encoding="application/x-tex">n</annotation></semantics></math> vertices where every edge is present with probability <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>p</mi><annotation encoding="application/x-tex">p</annotation></semantics></math>, a fixed subgraph with <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mi>k</mi><annotation encoding="application/x-tex">k</annotation></semantics></math> edges is contained with probability <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msup><mi>p</mi><mrow><mo>−</mo><mi>k</mi></mrow></msup><annotation encoding="application/x-tex">p^{-k}</annotation></semantics></math>. Hence the probability that a fixed forbidden graph appears is certainly smaller than <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msup><mi>p</mi><mrow><mo>−</mo><mn>3</mn></mrow></msup><annotation encoding="application/x-tex">p^{-3}</annotation></semantics></math>.</p>
<p>As we have at most <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><msup><mi>n</mi><mn>3</mn></msup><annotation encoding="application/x-tex">n^3</annotation></semantics></math> forbidden subgraphs, the expected number is at most <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>n</mi><mn>3</mn></msup><msup><mi>p</mi><mrow><mo>−</mo><mn>3</mn></mrow></msup></mrow><annotation encoding="application/x-tex">n^3p^{-3}</annotation></semantics></math>. This value goes to zero for <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>p</mi><mo><</mo><mn>1</mn><mi>/</mi><mi>n</mi></mrow><annotation encoding="application/x-tex">p < 1/n</annotation></semantics></math> and thus (modulo our simplified graph model) for graphs with less than <math display="inline" xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mi>/</mi><mn>2</mn></mrow><annotation encoding="application/x-tex">n/2</annotation></semantics></math> edges. Therefore in such graphs no forbidden subgraphs occur with high probability and insertion can work in principle.</p>
<p>But how about our greedy algorithm, is it sufficient for inserting new elements? Let’s consider a directed version of the cuckoo graph. Every edge is directed towards the position where the element is moved to in case it gets kicked out of its current spot. Hence elements reside at the edges tails and every node has at most one outgoing edge. Inserting a new element corresponds to inserting a new edge and directing it. If both endpoints already have an outgoing edge, we select an arbitrary one and kick the element out of its position. This means we reverse the edge and check at the new position whether there is already an outgoing edge.</p>
<p>This process fails if we cross an edge for the third time. The first time we see it, we flip it and continue. If we see it again, there was a directed cycle somewhere further down the path, that made us return. Note that this cycle still exists, only it now has the opposite direction. If we see the edge a third time, there was also a directed cycle on the other side–the process loops forever between these cycles.</p>
<div style="clear: both; text-align: center; margin-top:1.5em;">
<img border="0" height="135" src="pictures/insert.gif" width="400" /><br />
<p class="caption" style="text-align:inherit;">
This took way longer to make than I expected.
</p>
</div>
<p>But we’ve shown that these types of subgraphs don’t appear with high probability! Hence the greedy routine works for hash tables with an occupancy of less than 0.5.</p>
<p>In another post we might explore how long it takes in the worst case to find a free spot (not long) and how many collisions we have in expectation (<em>a lot</em> fewer than with just one hash function).</p>
<h4 id="improvements">Improvements</h4>
<p>Practitioners are probably not particularly thrilled to have a hash map that uses twice the amount of storage necessary even if offers constant retrieval time. Here a simple generalization of the method provides a dramatic improvement. If instead of taking two hash functions we use more, the occupancy threshold increases rapidly. Already for three functions we achieve more than 90% space utilization.<a href="#fn4" class="footnoteRef" id="fnref4"><sup>4</sup></a> However the math needed to prove that is much harder because we have to deal with hypergraphs. With more hash functions the number of collisions also decreases, though not a sharply as when going from one to two functions and retrieval can still be done very quickly in parallel.</p>
<p>A C implementation of d-ary cuckoo hashing can be found <a href="http://www.mpi-inf.mpg.de/~sanders/programs/cuckoo/">here</a>.</p>
<div class="footnotes">
<hr />
<ol>
<li id="fn1"><p>See for example <a href="http://zufallstee.blogspot.com/2011/10/one-rule-to-distribute-them-all.html">this post</a>.<a href="#fnref1">↩</a></p></li>
<li id="fn2"><p>Original paper <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.4189">Pagh et. al. 2001</a><a href="#fnref2">↩</a></p></li>
<li id="fn3"><p>This is a simplification, because we would have to use a random graph model where we fix the number of edges to the number items. For our purposes these two models are similar enough.<a href="#fnref3">↩</a></p></li>
<li id="fn4"><p><a href="http://arxiv.org/abs/0910.5147" class="uri">http://arxiv.org/abs/0910.5147</a><a href="#fnref4">↩</a></p></li>
</ol>
</div>
<hr/>
<div style="display:inline-flex;flex-wrap:wrap;justify-content:space-between;font-size:80%">
<p style="margin-right:2ex">CC-BY-SA <a href="mailto:[email protected]">Adrian Neumann</a> (PGP Key <a href="https://adriann.github.io/ressources/pub.asc">A0A8BC98</a>)</p>
<p style="margin-left:1ex;margin-right:1ex"><a href="http://adriann.github.io">adriann.github.io</a></p>
<p style="margin-left:2ex"><a href="https://adriann.github.io/feed.rss">RSS</a></p>
</div>
</body>
</html>