/usr/share/doc/libghc-hashtables-doc/html/Data-HashTable-ST-Basic.html is in libghc-hashtables-doc 1.0.1.8-2build2.
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 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 | <!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.Basic</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-Basic.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-HashTable-ST-Basic.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.0.1.8: 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></table><p class="caption">Data.HashTable.ST.Basic</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>A basic open-addressing hash table using linear probing. Use this hash table if
you...
</p><ul><li> want the fastest possible lookups, and very fast inserts.
</li><li> don't care about wasting a little bit of memory to get it.
</li><li> don't care that a table resize might pause for a long time to rehash all
of the key-value mappings.
</li><li> have a workload which is not heavy with deletes; deletes clutter the table
with deleted markers and force the table to be completely rehashed fairly
often.
</li></ul><p><em>Details:</em>
</p><p>Of the hash tables in this collection, this hash table has the best insert and
lookup performance, with the following caveats.
</p><p><em>Space overhead</em>
</p><p>This table is not especially memory-efficient; firstly, the table has a maximum
load factor of 0.83 and will be resized if load exceeds this value. Secondly,
to improve insert and lookup performance, we store the hash code for each key
in the table.
</p><p>Each hash table entry requires three words, two for the pointers to the key and
value and one for the hash code. We don't count key and value pointers as
overhead, because they have to be there -- so the overhead for a full slot is
one word -- but empty slots in the hash table count for a full three words of
overhead. Define <code>m</code> as the number of slots in the table and <code>n</code> as the number
of key value mappings. If the load factor is <code>k=n/m</code>, the amount of space
wasted is:
</p><pre>
w(n) = 1*n + 3(m-n)
</pre><p>Since <code>m=n/k</code>,
</p><pre>
w(n) = n + 3(n/k - n)
= n (3/k-2)
</pre><p>Solving for <code>k=0.83</code>, the maximum load factor, gives a <em>minimum</em> overhead of 2
words per mapping. If <code>k=0.5</code>, under normal usage the <em>maximum</em> overhead
situation, then the overhead would be 4 words per mapping.
</p><p><em>Space overhead: experimental results</em>
</p><p>In randomized testing (see <code>test/compute-overhead/ComputeOverhead.hs</code> in the
source distribution), mean overhead (that is, the number of words needed to
store the key-value mapping over and above the two words necessary for the key
and the value pointers) is approximately 2.29 machine words per key-value
mapping with a standard deviation of about 0.44 words, and 3.14 words per
mapping at the 95th percentile.
</p><p><em>Expensive resizes</em>
</p><p>If enough elements are inserted into the table to make it exceed the maximum
load factor, the table is resized. A resize involves a complete rehash of all
the elements in the table, which means that any given call to <code><a href="Data-HashTable-ST-Basic.html#v:insert">insert</a></code> might
take <em>O(n)</em> time in the size of the table, with a large constant factor. If a
long pause waiting for the table to resize is unacceptable for your
application, you should choose the included linear hash table instead.
</p><p><em>References:</em>
</p><ul><li> Knuth, Donald E. <em>The Art of Computer Programming</em>, vol. 3 Sorting and
Searching. Addison-Wesley Publishing Company, 1973.
</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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s (<a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v)</li><li class="src short"><a href="#v:newSized">newSized</a> :: <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s (<a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v)</li><li class="src short"><a href="#v:delete">delete</a> :: (<a href="/usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> k) => <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> k -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s ()</li><li class="src short"><a href="#v:lookup">lookup</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> k, <a href="/usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k) => <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> k -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> v)</li><li class="src short"><a href="#v:insert">insert</a> :: (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> k, <a href="/usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k) => <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> k -> v -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s ()</li><li class="src short"><a href="#v:mapM_">mapM_</a> :: ((k, v) -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s b) -> <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s ()</li><li class="src short"><a href="#v:foldM">foldM</a> :: (a -> (k, v) -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s a) -> a -> <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s a</li><li class="src short"><a href="#v:computeOverhead">computeOverhead</a> :: <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Prelude.html#t:Double">Double</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-Basic.html#HashTable" class="link">Source</a></p><div class="doc"><p>An open addressing hash table using linear probing.
</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"><a href="Data-HashTable-Class.html#t:HashTable">HashTable</a> <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a></td><td class="doc empty"> </td></tr><tr><td class="src"><a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Text-Show.html#t:Show">Show</a> (<a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v)</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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s (<a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v)<a href="src/Data-HashTable-ST-Basic.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Int.html#t:Int">Int</a> -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s (<a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v)<a href="src/Data-HashTable-ST-Basic.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="/usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k, <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> k) => <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> k -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s ()<a href="src/Data-HashTable-ST-Basic.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> k, <a href="/usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k) => <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> k -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s (<a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Maybe.html#t:Maybe">Maybe</a> v)<a href="src/Data-HashTable-ST-Basic.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Data-Eq.html#t:Eq">Eq</a> k, <a href="/usr/share/doc/libghc-hashable-doc/html/Data-Hashable.html#t:Hashable">Hashable</a> k) => <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> k -> v -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s ()<a href="src/Data-HashTable-ST-Basic.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s b) -> <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s ()<a href="src/Data-HashTable-ST-Basic.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="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s a) -> a -> <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s a<a href="src/Data-HashTable-ST-Basic.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 class="top"><p class="src"><a name="v:computeOverhead" class="def">computeOverhead</a> :: <a href="Data-HashTable-ST-Basic.html#t:HashTable">HashTable</a> s k v -> <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Control-Monad-ST-Safe.html#t:ST">ST</a> s <a href="/usr/share/doc/ghc-doc/html/libraries/base-4.6.0.1/Prelude.html#t:Double">Double</a><a href="src/Data-HashTable-ST-Basic.html#computeOverhead" class="link">Source</a></p><div class="doc"><p>See the documentation for this function in
<a href="Data-HashTable-Class.html#v:computeOverhead">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.13.2</p></div></body></html>
|