| |||||||||||||||||||||||

| |||||||||||||||||||||||

| |||||||||||||||||||||||

Description | |||||||||||||||||||||||

An implementation of extensible hash tables, as described in
Per-Ake Larson, Dynamic Hash Tables, CACM 31(4), April 1988,
pp. 446--457. The implementation is also derived from the one
in GHC's runtime system (ghc/rts/Hash.{c,h}).
| |||||||||||||||||||||||

Synopsis | |||||||||||||||||||||||

| |||||||||||||||||||||||

Basic hash table operations | |||||||||||||||||||||||

data HashTable key val | |||||||||||||||||||||||

| |||||||||||||||||||||||

new | |||||||||||||||||||||||

| |||||||||||||||||||||||

insert :: HashTable key val -> key -> val -> IO () | |||||||||||||||||||||||

Inserts an key/value mapping into the hash table. Note that | |||||||||||||||||||||||

delete :: HashTable key val -> key -> IO () | |||||||||||||||||||||||

Remove an entry from the hash table. | |||||||||||||||||||||||

lookup :: HashTable key val -> key -> IO (Maybe val) | |||||||||||||||||||||||

Looks up the value of a key in the hash table. | |||||||||||||||||||||||

update :: HashTable key val -> key -> val -> IO Bool | |||||||||||||||||||||||

Updates an entry in the hash table, returning
| |||||||||||||||||||||||

Converting to and from lists | |||||||||||||||||||||||

fromList :: Eq key => (key -> Int32) -> [(key, val)] -> IO (HashTable key val) | |||||||||||||||||||||||

Convert a list of key/value pairs into a hash table. Equality on keys is taken from the Eq instance for the key type. | |||||||||||||||||||||||

toList :: HashTable key val -> IO [(key, val)] | |||||||||||||||||||||||

Converts a hash table to a list of key/value pairs. | |||||||||||||||||||||||

Hash functions | |||||||||||||||||||||||

This implementation of hash tables uses the low-order If your keyspace is integrals such that the low-order bits between
keys are highly variable, then you could get away with using We provide some sample hash functions for | |||||||||||||||||||||||

hashInt :: Int -> Int32 | |||||||||||||||||||||||

A sample hash function for Int, implemented as simply (x
where P is a suitable prime (currently 1500007). Should give
reasonable results for most distributions of mod P)Int values, except
when the keys are all multiples of the prime!
| |||||||||||||||||||||||

hashString :: String -> Int32 | |||||||||||||||||||||||

A sample hash function for hashString = fromIntegral . foldr f 0 where f c m = ord c + (m * 128) `rem` 1500007 which seems to give reasonable results. | |||||||||||||||||||||||

prime :: Int32 | |||||||||||||||||||||||

A prime larger than the maximum hash table size | |||||||||||||||||||||||

Diagnostics | |||||||||||||||||||||||

longestChain :: HashTable key val -> IO [(key, val)] | |||||||||||||||||||||||

This function is useful for determining whether your hash function is working well for your data set. It returns the longest chain of key/value pairs in the hash table for which all the keys hash to the same bucket. If this chain is particularly long (say, longer than 10 elements), then it might be a good idea to try a different hash function. | |||||||||||||||||||||||

Produced by Haddock version 0.7 |