libghc-hashtables-doc 1.2.1.0-1build1 / usr / share / doc / libghc-hashtables-doc / html / hashtables.txt

-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Mutable hash tables in the ST monad
--   
--   This package provides a couple of different implementations of mutable
--   hash tables in the ST monad, as well as a typeclass abstracting their
--   common operations, and a set of wrappers to use the hash tables in the
--   IO monad.
--   
--   <i>QUICK START</i>: documentation for the hash table operations is
--   provided in the <a>Data.HashTable.Class</a> module, and the IO
--   wrappers (which most users will probably prefer) are located in the
--   <a>Data.HashTable.IO</a> module.
--   
--   This package currently contains three hash table implementations:
--   
--   <ol>
--   <li><a>Data.HashTable.ST.Cuckoo</a> contains an implementation of
--   "cuckoo hashing" as introduced by Pagh and Rodler in 2001 (see
--   <a>http://en.wikipedia.org/wiki/Cuckoo_hashing</a>). Cuckoo hashing
--   has worst-case <i>O(1)</i> lookups and can reach a high "load factor",
--   in which the table can perform acceptably well even when approaching
--   90% full. Randomized testing shows this implementation of cuckoo
--   hashing to be slightly faster on insert and slightly slower on lookup
--   than <a>Data.Hashtable.ST.Basic</a>, while being more space efficient
--   by about a half-word per key-value mapping. Cuckoo hashing, like the
--   basic hash table implementation using linear probing, can suffer from
--   long delays when the table is resized.</li>
--   <li><a>Data.HashTable.ST.Basic</a> contains a basic open-addressing
--   hash table using linear probing as the collision strategy. On a pure
--   speed basis it should currently be the fastest available Haskell hash
--   table implementation for lookups, although it has a higher memory
--   overhead than the other tables and can suffer from long delays when
--   the table is resized because all of the elements in the table need to
--   be rehashed.</li>
--   <li><a>Data.HashTable.ST.Linear</a> contains a linear hash table (see
--   <a>http://en.wikipedia.org/wiki/Linear_hashing</a>), which trades some
--   insert and lookup performance for higher space efficiency and much
--   shorter delays when expanding the table. In most cases, benchmarks
--   show this table to be currently slightly faster than
--   <tt>Data.HashTable</tt> from the Haskell base library.</li>
--   </ol>
--   
--   It is recommended to create a concrete type alias in your code when
--   using this package, i.e.:
--   
--   <pre>
--   import qualified Data.HashTable.IO as H
--   
--   type HashTable k v = H.BasicHashTable k v
--   
--   foo :: IO (HashTable Int Int)
--   foo = do
--       ht &lt;- H.new
--       H.insert ht 1 1
--       return ht
--   </pre>
--   
--   Firstly, this makes it easy to switch to a different hash table
--   implementation, and secondly, using a concrete type rather than
--   leaving your functions abstract in the HashTable class should allow
--   GHC to optimize away the typeclass dictionaries.
--   
--   This package accepts a couple of different cabal flags:
--   
--   <ul>
--   <li><tt>unsafe-tricks</tt>, default <i>ON</i>. If this flag is
--   enabled, we use some unsafe GHC-specific tricks to save indirections
--   (namely <tt>unsafeCoerce#</tt> and <tt>reallyUnsafePtrEquality#</tt>.
--   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.</li>
--   <li><tt>sse42</tt>, default <i>OFF</i>. If this flag is enabled, we
--   use some SSE 4.2 instructions (see
--   <a>http://en.wikipedia.org/wiki/SSE4</a>, first available on Intel
--   Core 2 processors) to speed up cache-line searches for cuckoo
--   hashing.</li>
--   <li><tt>bounds-checking</tt>, default <i>OFF</i>. If this flag is
--   enabled, array accesses are bounds-checked.</li>
--   <li><tt>debug</tt>, default <i>OFF</i>. If turned on, we'll rudely
--   spew debug output to stdout.</li>
--   <li><tt>portable</tt>, default <i>OFF</i>. If this flag is enabled, we
--   use only pure Haskell code and try not to use unportable GHC
--   extensions. Turning this flag on forces <tt>unsafe-tricks</tt> and
--   <tt>sse42</tt> <i>OFF</i>.</li>
--   </ul>
--   
--   Please send bug reports to
--   <a>https://github.com/gregorycollins/hashtables/issues</a>.
@package hashtables
@version 1.2.1.0


-- | This module contains a <a>HashTable</a> typeclass for the hash table
--   implementations in this package. This allows you to provide functions
--   which will work for any hash table implementation in this collection.
--   
--   It is recommended to create a concrete type alias in your code when
--   using this package, i.e.:
--   
--   <pre>
--   import qualified Data.HashTable.IO as H
--   
--   type HashTable k v = H.BasicHashTable k v
--   
--   foo :: IO (HashTable Int Int)
--   foo = do
--       ht &lt;- H.new
--       H.insert ht 1 1
--       return ht
--   </pre>
--   
--   or
--   
--   <pre>
--   import qualified Data.HashTable.ST.Cuckoo as C
--   import qualified Data.HashTable.Class as H
--   
--   type HashTable s k v = C.HashTable s k v
--   
--   foo :: ST s (HashTable s k v)
--   foo = do
--       ht &lt;- H.new
--       H.insert ht 1 1
--       return ht
--   </pre>
--   
--   Firstly, this makes it easy to switch to a different hash table
--   implementation, and secondly, using a concrete type rather than
--   leaving your functions abstract in the <a>HashTable</a> class should
--   allow GHC to optimize away the typeclass dictionaries.
--   
--   Note that the functions in this typeclass are in the <a>ST</a> monad;
--   if you want hash tables in <a>IO</a>, use the convenience wrappers in
--   <a>Data.HashTable.IO</a>.
module Data.HashTable.Class

-- | A typeclass for hash tables in the <a>ST</a> monad. The operations on
--   these hash tables are typically both key- and value-strict.
class HashTable h

-- | Creates a new, default-sized hash table. <i>O(1)</i>.
new :: HashTable h => ST s (h s k v)

-- | Creates a new hash table sized to hold <tt>n</tt> elements.
--   <i>O(n)</i>.
newSized :: HashTable h => Int -> ST s (h s k v)

-- | Inserts a key/value mapping into a hash table, replacing any existing
--   mapping for that key.
--   
--   <i>O(n)</i> worst case, <i>O(1)</i> amortized.
insert :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> v -> ST s ()

-- | Deletes a key-value mapping from a hash table. <i>O(n)</i> worst case,
--   <i>O(1)</i> amortized.
delete :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> ST s ()

-- | Looks up a key-value mapping in a hash table. <i>O(n)</i> worst case,
--   (<i>O(1)</i> for cuckoo hash), <i>O(1)</i> amortized.
lookup :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> ST s (Maybe v)

-- | A strict fold over the key-value records of a hash table in the
--   <a>ST</a> monad. <i>O(n)</i>.
foldM :: HashTable h => (a -> (k, v) -> ST s a) -> a -> h s k v -> ST s a

-- | A side-effecting map over the key-value records of a hash table.
--   <i>O(n)</i>.
mapM_ :: HashTable h => ((k, v) -> ST s b) -> h s k v -> ST s ()

-- | Computes the overhead (in words) per key-value mapping. Used for
--   debugging, etc; time complexity depends on the underlying hash table
--   implementation. <i>O(n)</i>.
computeOverhead :: HashTable h => h s k v -> ST s Double

-- | Create a hash table from a list of key-value pairs. <i>O(n)</i>.
fromList :: (HashTable h, Eq k, Hashable k) => [(k, v)] -> ST s (h s k v)

-- | Create a hash table from a list of key-value pairs, with a size hint.
--   <i>O(n)</i>.
fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) => Int -> [(k, v)] -> ST s (h s k v)

-- | Given a hash table, produce a list of key-value pairs. <i>O(n)</i>.
toList :: (HashTable h) => h s k v -> ST s [(k, v)]


-- | A basic open-addressing hash table using linear probing. Use this hash
--   table if you...
--   
--   <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>
--   
--   Of the hash tables in this collection, this hash table has the best
--   lookup performance, while maintaining competitive insert performance.
--   
--   <i>Space overhead</i>
--   
--   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 a
--   16-bit hash code for each key in the table.
--   
--   Each hash table entry requires at least 2.25 words (on a 64-bit
--   machine), two for the pointers to the key and value and one quarter
--   word 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 at least one quarter word -- but empty slots in the hash table
--   count for a full 2.25 words of overhead. Define <tt>m</tt> as the
--   number of slots in the table, <tt>n</tt> as the number of key value
--   mappings, and <tt>ws</tt> as the machine word size in <i>bytes</i>. If
--   the load factor is <tt>k=n/m</tt>, the amount of space <i>wasted</i>
--   per mapping in words is:
--   
--   <pre>
--   w(n) = (m*(2*ws + 2) - n*(2*ws)) / ws
--   </pre>
--   
--   Since <tt>m=n/k</tt>,
--   
--   <pre>
--   w(n) = n/k * (2*ws + 2) - n*(2*ws)
--        = (n * (2 + 2*ws*(1-k)) <i> k) </i> ws
--   </pre>
--   
--   Solving for <tt>k=0.83</tt>, the maximum load factor, gives a
--   <i>minimum</i> overhead of 0.71 words per mapping on a 64-bit machine,
--   or 1.01 words per mapping on a 32-bit machine. If <tt>k=0.5</tt>,
--   which should be under normal usage the <i>maximum</i> overhead
--   situation, then the overhead would be 2.5 words per mapping on a
--   64-bit machine, or 3.0 words per mapping on a 32-bit machine.
--   
--   <i>Space overhead: experimental results</i>
--   
--   In randomized testing on a 64-bit machine (see
--   <tt>test/compute-overhead/ComputeOverhead.hs</tt> 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 1.24 machine words
--   per key-value mapping with a standard deviation of about 0.30 words,
--   and 1.70 words per mapping at the 95th percentile.
--   
--   <i>Expensive resizes</i>
--   
--   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 <a>insert</a> might take <i>O(n)</i> 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.
--   
--   <i>References:</i>
--   
--   <ul>
--   <li>Knuth, Donald E. <i>The Art of Computer Programming</i>, vol. 3
--   Sorting and Searching. Addison-Wesley Publishing Company, 1973.</li>
--   </ul>
module Data.HashTable.ST.Basic

-- | An open addressing hash table using linear probing.
data HashTable s k v

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:new</a>.
new :: ST s (HashTable s k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:newSized</a>.
newSized :: Int -> ST s (HashTable s k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:delete</a>.
delete :: (Hashable k, Eq k) => (HashTable s k v) -> k -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:lookup</a>.
lookup :: (Eq k, Hashable k) => (HashTable s k v) -> k -> ST s (Maybe v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:insert</a>.
insert :: (Eq k, Hashable k) => (HashTable s k v) -> k -> v -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:mapM_</a>.
mapM_ :: ((k, v) -> ST s b) -> HashTable s k v -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:foldM</a>.
foldM :: (a -> (k, v) -> ST s a) -> a -> HashTable s k v -> ST s a

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:computeOverhead</a>.
computeOverhead :: HashTable s k v -> ST s Double
instance GHC.Show.Show Data.HashTable.ST.Basic.Slot
instance Data.HashTable.Class.HashTable Data.HashTable.ST.Basic.HashTable
instance GHC.Show.Show (Data.HashTable.ST.Basic.HashTable s k v)
instance GHC.Base.Monoid Data.HashTable.ST.Basic.Slot


-- | A hash table using the cuckoo strategy. (See
--   <a>http://en.wikipedia.org/wiki/Cuckoo_hashing</a>). Use this hash
--   table if you...
--   
--   <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>Data.HashTable.ST.Basic</a> or
--   <a>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>
--   
--   <i>Details:</i>
--   
--   The basic idea of cuckoo hashing, first introduced by Pagh and Rodler
--   in 2001, is to use <i>d</i> 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 <tt>k</tt> buckets, each cache-line-sized:
--   
--   <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>
--   
--   There are actually three parallel arrays: one unboxed array of
--   <a>Int</a>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.
--   
--   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.
--   
--   <i>Space overhead: experimental results</i>
--   
--   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 <tt>test/compute-overhead/ComputeOverhead.hs</tt>
--   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.
--   
--   <i>References:</i>
--   
--   <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>
module Data.HashTable.ST.Cuckoo

-- | A cuckoo hash table.
data HashTable s k v

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:new</a>.
new :: ST s (HashTable s k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:newSized</a>.
newSized :: Int -> ST s (HashTable s k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:delete</a>.
delete :: (Hashable k, Eq k) => HashTable s k v -> k -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:lookup</a>.
lookup :: (Eq k, Hashable k) => HashTable s k v -> k -> ST s (Maybe v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:insert</a>.
insert :: (Eq k, Hashable k) => HashTable s k v -> k -> v -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:mapM_</a>.
mapM_ :: ((k, v) -> ST s a) -> HashTable s k v -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:foldM</a>.
foldM :: (a -> (k, v) -> ST s a) -> a -> HashTable s k v -> ST s a
instance Data.HashTable.Class.HashTable Data.HashTable.ST.Cuckoo.HashTable
instance GHC.Show.Show (Data.HashTable.ST.Cuckoo.HashTable s k v)


-- | An implementation of linear hash tables. (See
--   <a>http://en.wikipedia.org/wiki/Linear_hashing</a>). Use this hash
--   table if you...
--   
--   <ul>
--   <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 <tt>Data.HashTable</tt> 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>
--   
--   <i>Details:</i>
--   
--   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:
--   
--   <pre>
--   bucket(level,key) = hash(key) mod (2^level)
--   </pre>
--   
--   The "split pointer" controls the expansion of the hash table. If the
--   hash table is at level <tt>k</tt> (i.e. <tt>2^k</tt> buckets have been
--   allocated), we first calculate <tt>b=bucket(level-1,key)</tt>. If
--   <tt>b &lt; splitptr</tt>, the destination bucket is calculated as
--   <tt>b'=bucket(level,key)</tt>, otherwise the original value <tt>b</tt>
--   is used.
--   
--   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.
--   
--   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.
--   
--   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.
--   
--   <i>Space overhead: experimental results</i>
--   
--   In randomized testing (see
--   <tt>test/compute-overhead/ComputeOverhead.hs</tt> 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.
--   
--   <i>Unsafe tricks</i>
--   
--   Then the <tt>unsafe-tricks</tt> flag is on when this package is built
--   (and it is on by default), we use some unsafe tricks (namely
--   <tt>unsafeCoerce#</tt> and <tt>reallyUnsafePtrEquality#</tt>) 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.
--   
--   References:
--   
--   <ul>
--   <li>W. Litwin. Linear hashing: a new tool for file and table
--   addressing. In <i>Proc. 6th International Conference on Very Large
--   Data Bases, Volume 6</i>, pp. 212-223, 1980.</li>
--   <li>P-A. Larson. Dynamic hash tables. <i>Communications of the ACM</i>
--   31: 446-457, 1988.</li>
--   </ul>
module Data.HashTable.ST.Linear

-- | A linear hash table.
data HashTable s k v

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:new</a>.
new :: ST s (HashTable s k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:newSized</a>.
newSized :: Int -> ST s (HashTable s k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:delete</a>.
delete :: (Hashable k, Eq k) => (HashTable s k v) -> k -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:lookup</a>.
lookup :: (Eq k, Hashable k) => (HashTable s k v) -> k -> ST s (Maybe v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:insert</a>.
insert :: (Eq k, Hashable k) => (HashTable s k v) -> k -> v -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:mapM_</a>.
mapM_ :: ((k, v) -> ST s b) -> HashTable s k v -> ST s ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:foldM</a>.
foldM :: (a -> (k, v) -> ST s a) -> a -> HashTable s k v -> ST s a

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:computeOverhead</a>.
computeOverhead :: HashTable s k v -> ST s Double
instance Data.HashTable.Class.HashTable Data.HashTable.ST.Linear.HashTable
instance GHC.Show.Show (Data.HashTable.ST.Linear.HashTable s k v)


-- | This module provides wrappers in <a>IO</a> around the functions from
--   <a>Data.HashTable.Class</a>.
--   
--   This module exports three concrete hash table types, one for each hash
--   table implementation in this package:
--   
--   <pre>
--   type BasicHashTable  k v = IOHashTable (B.HashTable)  k v
--   type CuckooHashTable k v = IOHashTable (Cu.HashTable) k v
--   type LinearHashTable k v = IOHashTable (L.HashTable)  k v
--   </pre>
--   
--   The <a>IOHashTable</a> type can be thought of as a wrapper around a
--   concrete hashtable type, which sets the <tt>ST</tt> monad state type
--   to <a>PrimState</a> <a>IO</a>, a.k.a. <tt>RealWorld</tt>:
--   
--   <pre>
--   type IOHashTable tabletype k v = tabletype (PrimState IO) k v
--   </pre>
--   
--   This module provides <a>stToIO</a> wrappers around the hashtable
--   functions (which are in <tt>ST</tt>) to make it convenient to use them
--   in <a>IO</a>. It is intended to be imported qualified and used with a
--   user-defined type alias, i.e.:
--   
--   <pre>
--   import qualified Data.HashTable.IO as H
--   
--   type HashTable k v = H.CuckooHashTable k v
--   
--   foo :: IO (HashTable Int Int)
--   foo = do
--       ht &lt;- H.new
--       H.insert ht 1 1
--       return ht
--   </pre>
--   
--   Essentially, anywhere you see <tt><a>IOHashTable</a> h k v</tt> in the
--   type signatures below, you can plug in any of
--   <tt><a>BasicHashTable</a> k v</tt>, <tt><a>CuckooHashTable</a> k
--   v</tt>, or <tt><a>LinearHashTable</a> k v</tt>.
module Data.HashTable.IO

-- | A type alias for a basic open addressing hash table using linear
--   probing. See <a>Data.HashTable.ST.Basic</a>.
type BasicHashTable k v = IOHashTable (HashTable) k v

-- | A type alias for the cuckoo hash table. See
--   <a>Data.HashTable.ST.Cuckoo</a>.
type CuckooHashTable k v = IOHashTable (HashTable) k v

-- | A type alias for the linear hash table. See
--   <a>Data.HashTable.ST.Linear</a>.
type LinearHashTable k v = IOHashTable (HashTable) k v

-- | A type alias for our hash tables, which run in <tt>ST</tt>, to set the
--   state token type to <a>PrimState</a> <a>IO</a> (aka
--   <tt>RealWorld</tt>) so that we can use them in <a>IO</a>.
type IOHashTable tabletype k v = tabletype (PrimState IO) k v

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:new</a>.
new :: HashTable h => IO (IOHashTable h k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:newSized</a>.
newSized :: HashTable h => Int -> IO (IOHashTable h k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:insert</a>.
insert :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> v -> IO ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:delete</a>.
delete :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> IO ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:lookup</a>.
lookup :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> IO (Maybe v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:fromList</a>.
fromList :: (HashTable h, Eq k, Hashable k) => [(k, v)] -> IO (IOHashTable h k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:fromListWithSizeHint</a>.
fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) => Int -> [(k, v)] -> IO (IOHashTable h k v)

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:toList</a>.
toList :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> IO [(k, v)]

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:mapM_</a>.
mapM_ :: (HashTable h) => ((k, v) -> IO a) -> IOHashTable h k v -> IO ()

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:foldM</a>.
foldM :: (HashTable h) => (a -> (k, v) -> IO a) -> a -> IOHashTable h k v -> IO a

-- | See the documentation for this function in
--   <a>Data.HashTable.Class#v:computeOverhead</a>.
computeOverhead :: (HashTable h) => IOHashTable h k v -> IO Double