hashtables-1.0.1.2: Mutable hash tables in the ST monad

Data.HashTable.ST.Basic

Description

A basic open-addressing hash table using linear probing. Use this hash table if you...

  • want the fastest possible lookups, and very fast inserts.
  • don't care about wasting a little bit of memory to get it.
  • don't care that a table resize might pause for a long time to rehash all of the key-value mappings.
  • 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.

Details:

Of the hash tables in this collection, this hash table has the best insert and lookup performance, with the following caveats.

Space overhead

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.

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 m as the number of slots in the table and n as the number of key value mappings. If the load factor is k=n/m, the amount of space wasted is:

w(n) = 1*n + 3(m-n)

Since m=n/k,

w(n) = n + 3(n/k - n)
= n (3/k-2)

Solving for k=0.83, the maximum load factor, gives a minimum overhead of 2 words per mapping. If k=0.5, under normal usage the maximum overhead situation, then the overhead would be 4 words per mapping.

Space overhead: experimental results

In randomized testing (see test/compute-overhead/ComputeOverhead.hs 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.

Expensive resizes

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 insert might take O(n) 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.

References:

  • Knuth, Donald E. The Art of Computer Programming, vol. 3 Sorting and Searching. Addison-Wesley Publishing Company, 1973.

Synopsis

Documentation

data HashTable s k v Source

An open addressing hash table using linear probing.

Instances

new :: ST s (HashTable s k v)Source

See the documentation for this function in Data.HashTable.Class.

newSized :: Int -> ST s (HashTable s k v)Source

See the documentation for this function in Data.HashTable.Class.

delete :: (Hashable k, Eq k) => HashTable s k v -> k -> ST s ()Source

See the documentation for this function in Data.HashTable.Class.

lookup :: (Eq k, Hashable k) => HashTable s k v -> k -> ST s (Maybe v)Source

See the documentation for this function in Data.HashTable.Class.

insert :: (Eq k, Hashable k) => HashTable s k v -> k -> v -> ST s ()Source

See the documentation for this function in Data.HashTable.Class.

mapM_ :: ((k, v) -> ST s b) -> HashTable s k v -> ST s ()Source

See the documentation for this function in Data.HashTable.Class.

foldM :: (a -> (k, v) -> ST s a) -> a -> HashTable s k v -> ST s aSource

See the documentation for this function in Data.HashTable.Class.

computeOverhead :: HashTable s k v -> ST s DoubleSource

See the documentation for this function in Data.HashTable.Class.