/usr/share/doc/libghc-hashtables-doc/html/Data-HashTable-ST-Cuckoo.html is in libghc-hashtables-doc 1.2.1.0-1build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | <!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><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Data.HashTable.ST.Cuckoo</title><link href="ocean.css" rel="stylesheet" type="text/css" title="Ocean" /><script src="haddock-util.js" type="text/javascript"></script><script type="text/javascript">//<![CDATA[
window.onload = function () {pageLoad();setSynopsis("mini_Data-HashTable-ST-Cuckoo.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-HashTable-ST-Cuckoo.html">Source</a></li><li><a href="index.html">Contents</a></li><li><a href="doc-index.html">Index</a></li></ul><p class="caption">hashtables-1.2.1.0: Mutable hash tables in the ST monad</p></div><div id="content"><div id="module-header"><table class="info"><tr><th>Safe Haskell</th><td>None</td></tr><tr><th>Language</th><td>Haskell98</td></tr></table><p class="caption">Data.HashTable.ST.Cuckoo</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>A hash table using the cuckoo strategy. (See
<a href="http://en.wikipedia.org/wiki/Cuckoo_hashing">http://en.wikipedia.org/wiki/Cuckoo_hashing</a>). Use this hash table if you...</p><ul><li>want the fastest possible inserts, and very fast lookups.</li><li>are conscious of memory usage; this table has less space overhead than
<a href="Data-HashTable-ST-Basic.html">Data.HashTable.ST.Basic</a> or <a href="Data-HashTable-ST-Linear.html">Data.HashTable.ST.Linear</a>.</li><li>don't care that a table resize might pause for a long time to rehash all
of the key-value mappings.</li></ul><p><em>Details:</em></p><p>The basic idea of cuckoo hashing, first introduced by Pagh and Rodler in 2001,
is to use <em>d</em> hash functions instead of only one; in this implementation d=2
and the strategy we use is to split up a flat array of slots into <code>k</code> buckets,
each cache-line-sized:</p><pre>+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+----------+
|x0|x1|x2|x3|x4|x5|x6|x7|y0|y1|y2|y3|y4|y5|y6|y7|z0|z1|z2........|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+----------+
[ ^^^ bucket 0 ^^^ ][ ^^^ bucket 1 ^^^ ]...
</pre><p>There are actually three parallel arrays: one unboxed array of <code><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Int.html#t:Int">Int</a></code>s for hash
codes, one boxed array for keys, and one boxed array for values. When looking
up a key-value mapping, we hash the key using two hash functions and look in
both buckets in the hash code array for the key. Each bucket is cache-line
sized, with its keys in no particular order. Because the hash code array is
unboxed, we can search it for the key using a highly-efficient branchless
strategy in C code, using SSE instructions if available.</p><p>On insert, if both buckets are full, we knock out a randomly-selected entry
from one of the buckets (using a random walk ensures that "key cycles" are
broken with maximum probability) and try to repeat the insert procedure. This
process may not succeed; if all items have not successfully found a home after
some number of tries, we give up and rehash all of the elements into a larger
table.</p><p><em>Space overhead: experimental results</em></p><p>The implementation of cuckoo hash given here is almost as fast for lookups as
the basic open-addressing hash table using linear probing, and on average is
more space-efficient: in randomized testing on my 64-bit machine (see
<code>test/compute-overhead/ComputeOverhead.hs</code> in the source distribution), mean
overhead is 0.77 machine words per key-value mapping, with a standard deviation
of 0.29 words, and 1.23 words per mapping at the 95th percentile.</p><p><em>References:</em></p><ul><li>A. Pagh and F. Rodler. Cuckoo hashing. In /Proceedings of the 9th
Annual European Symposium on Algorithms/, pp. 121-133, 2001.</li></ul></div></div><div id="synopsis"><p id="control.syn" class="caption expander" onclick="toggleSection('syn')">Synopsis</p><ul id="section.syn" class="hide" onclick="toggleSection('syn')"><li class="src short"><span class="keyword">data</span> <a href="#t:HashTable">HashTable</a> s k v</li><li class="src short"><a href="#v:new">new</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s (<a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v)</li><li class="src short"><a href="#v:newSized">newSized</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Int.html#t:Int">Int</a> -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s (<a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v)</li><li class="src short"><a href="#v:delete">delete</a> :: (<a href="file:///usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Eq.html#t:Eq">Eq</a> k) => <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> k -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s ()</li><li class="src short"><a href="#v:lookup">lookup</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Eq.html#t:Eq">Eq</a> k, <a href="file:///usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k) => <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> k -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#t:Maybe">Maybe</a> v)</li><li class="src short"><a href="#v:insert">insert</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Eq.html#t:Eq">Eq</a> k, <a href="file:///usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k) => <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> k -> v -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s ()</li><li class="src short"><a href="#v:mapM_">mapM_</a> :: ((k, v) -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s a) -> <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s ()</li><li class="src short"><a href="#v:foldM">foldM</a> :: (a -> (k, v) -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s a) -> a -> <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s a</li></ul></div><div id="interface"><h1>Documentation</h1><div class="top"><p class="src"><span class="keyword">data</span> <a name="t:HashTable" class="def">HashTable</a> s k v <a href="src/Data-HashTable-ST-Cuckoo.html#HashTable" class="link">Source</a></p><div class="doc"><p>A cuckoo hash table.</p></div><div class="subs instances"><p id="control.i:HashTable" class="caption collapser" onclick="toggleSection('i:HashTable')">Instances</p><div id="section.i:HashTable" class="show"><table><tr><td class="src clearfix"><span class="inst-left"><a href="Data-HashTable-Class.html#t:HashTable">HashTable</a> <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a></span> <a href="src/Data-HashTable-ST-Cuckoo.html#line-123" class="link">Source</a></td><td class="doc empty"> </td></tr><tr><td class="src clearfix"><span class="inst-left"><a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Text-Show.html#t:Show">Show</a> (<a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v)</span> <a href="src/Data-HashTable-ST-Cuckoo.html#line-135" class="link">Source</a></td><td class="doc empty"> </td></tr></table></div></div></div><div class="top"><p class="src"><a name="v:new" class="def">new</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s (<a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v) <a href="src/Data-HashTable-ST-Cuckoo.html#new" class="link">Source</a></p><div class="doc"><p>See the documentation for this function in
<a href="Data-HashTable-Class.html#v:new">Data.HashTable.Class</a>.</p></div></div><div class="top"><p class="src"><a name="v:newSized" class="def">newSized</a> :: <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Int.html#t:Int">Int</a> -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s (<a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v) <a href="src/Data-HashTable-ST-Cuckoo.html#newSized" class="link">Source</a></p><div class="doc"><p>See the documentation for this function in
<a href="Data-HashTable-Class.html#v:newSized">Data.HashTable.Class</a>.</p></div></div><div class="top"><p class="src"><a name="v:delete" class="def">delete</a> :: (<a href="file:///usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k, <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Eq.html#t:Eq">Eq</a> k) => <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> k -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s () <a href="src/Data-HashTable-ST-Cuckoo.html#delete" class="link">Source</a></p><div class="doc"><p>See the documentation for this function in
<a href="Data-HashTable-Class.html#v:delete">Data.HashTable.Class</a>.</p></div></div><div class="top"><p class="src"><a name="v:lookup" class="def">lookup</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Eq.html#t:Eq">Eq</a> k, <a href="file:///usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k) => <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> k -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Maybe.html#t:Maybe">Maybe</a> v) <a href="src/Data-HashTable-ST-Cuckoo.html#lookup" class="link">Source</a></p><div class="doc"><p>See the documentation for this function in
<a href="Data-HashTable-Class.html#v:lookup">Data.HashTable.Class</a>.</p></div></div><div class="top"><p class="src"><a name="v:insert" class="def">insert</a> :: (<a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Data-Eq.html#t:Eq">Eq</a> k, <a href="file:///usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k) => <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> k -> v -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s () <a href="src/Data-HashTable-ST-Cuckoo.html#insert" class="link">Source</a></p><div class="doc"><p>See the documentation for this function in
<a href="Data-HashTable-Class.html#v:insert">Data.HashTable.Class</a>.</p></div></div><div class="top"><p class="src"><a name="v:mapM_" class="def">mapM_</a> :: ((k, v) -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s a) -> <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s () <a href="src/Data-HashTable-ST-Cuckoo.html#mapM_" class="link">Source</a></p><div class="doc"><p>See the documentation for this function in
<a href="Data-HashTable-Class.html#v:mapM_">Data.HashTable.Class</a>.</p></div></div><div class="top"><p class="src"><a name="v:foldM" class="def">foldM</a> :: (a -> (k, v) -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s a) -> a -> <a href="Data-HashTable-ST-Cuckoo.html#t:HashTable">HashTable</a> s k v -> <a href="file:///usr/share/doc/ghc-doc/html/libraries/base-4.8.2.0/Control-Monad-ST.html#t:ST">ST</a> s a <a href="src/Data-HashTable-ST-Cuckoo.html#foldM" class="link">Source</a></p><div class="doc"><p>See the documentation for this function in
<a href="Data-HashTable-Class.html#v:foldM">Data.HashTable.Class</a>.</p></div></div></div></div><div id="footer"><p>Produced by <a href="http://www.haskell.org/haddock/">Haddock</a> version 2.16.1</p></div></body></html>
|