/usr/share/doc/libghc-hashtables-doc/html/Data-HashTable-ST-Linear.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 72 73 74 75 | <!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.Linear</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-Linear.html");};
//]]>
</script></head><body><div id="package-header"><ul class="links" id="page-menu"><li><a href="src/Data-HashTable-ST-Linear.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.Linear</p></div><div id="description"><p class="caption">Description</p><div class="doc"><p>An implementation of linear hash tables. (See
<a href="http://en.wikipedia.org/wiki/Linear_hashing">http://en.wikipedia.org/wiki/Linear_hashing</a>). Use this hash table if you...
</p><ul><li> care a lot about fitting your data set into memory; of the hash tables
included in this collection, this one has the lowest space overhead
</li><li> don't care that inserts and lookups are slower than the other hash table
implementations in this collection (this one is slightly faster than
<code>Data.HashTable</code> from the base library in most cases)
</li><li> have a soft real-time or interactive application for which the risk of
introducing a long pause on insert while all of the keys are rehashed is
unacceptable.
</li></ul><p><em>Details:</em>
</p><p>Linear hashing allows for the expansion of the hash table one slot at a time,
by moving a "split" pointer across an array of pointers to buckets. The
number of buckets is always a power of two, and the bucket to look in is
defined as:
</p><pre>
bucket(level,key) = hash(key) mod (2^level)
</pre><p>The "split pointer" controls the expansion of the hash table. If the hash
table is at level <code>k</code> (i.e. <code>2^k</code> buckets have been allocated), we first
calculate <code>b=bucket(level-1,key)</code>. If <code>b < splitptr</code>, the destination bucket is
calculated as <code>b'=bucket(level,key)</code>, otherwise the original value <code>b</code> is used.
</p><p>The split pointer is incremented once an insert causes some bucket to become
fuller than some predetermined threshold; the bucket at the split pointer
(*not* the bucket which triggered the split!) is then rehashed, and half of its
keys can be expected to be rehashed into the upper half of the table.
</p><p>When the split pointer reaches the middle of the bucket array, the size of the
bucket array is doubled, the level increases, and the split pointer is reset to
zero.
</p><p>Linear hashing, although not quite as fast for inserts or lookups as the
implementation of linear probing included in this package, is well suited for
interactive applications because it has much better worst case behaviour on
inserts. Other hash table implementations can suffer from long pauses, because
it is occasionally necessary to rehash all of the keys when the table grows.
Linear hashing, on the other hand, only ever rehashes a bounded (effectively
constant) number of keys when an insert forces a bucket split.
</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 is approximately 1.51 machine words per
key-value mapping with a very low standard deviation of about 0.06 words, 1.60
words per mapping at the 95th percentile.
</p><p><em>Unsafe tricks</em>
</p><p>Then the <code>unsafe-tricks</code> flag is on when this package is built (and it is on by
default), we use some unsafe tricks (namely <code>unsafeCoerce#</code> and
<code>reallyUnsafePtrEquality#</code>) to save indirections in this table. These
techniques rely on assumptions about the behaviour of the GHC runtime system
and, although they've been tested and should be safe under normal conditions,
are slightly dangerous. Caveat emptor. In particular, these techniques are
incompatible with HPC code coverage reports.
</p><p>References:
</p><ul><li> W. Litwin. Linear hashing: a new tool for file and table addressing. In
<em>Proc. 6th International Conference on Very Large Data Bases, Volume 6</em>,
pp. 212-223, 1980.
</li><li> P-A. Larson. Dynamic hash tables. <em>Communications of the ACM</em> 31:
446-457, 1988.
</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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.html#HashTable" class="link">Source</a></p><div class="doc"><p>A linear 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"><a href="Data-HashTable-Class.html#t:HashTable">HashTable</a> <a href="Data-HashTable-ST-Linear.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-Linear.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-Linear.html#t:HashTable">HashTable</a> s k v)<a href="src/Data-HashTable-ST-Linear.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-Linear.html#t:HashTable">HashTable</a> s k v)<a href="src/Data-HashTable-ST-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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-Linear.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>
|