 | Haskell Hierarchical Libraries (base package) | Contents | Index |
| Data.HashTable |
|
| Contents |
| data HashTable key val |
| new :: (key -> key -> Bool) -> (key -> Int32) -> IO (HashTable key val) |
| insert :: HashTable key val -> key -> val -> IO () |
| delete :: HashTable key val -> key -> IO () |
| lookup :: HashTable key val -> key -> IO (Maybe val) |
| update :: HashTable key val -> key -> val -> IO Bool |
| fromList :: Eq key => (key -> Int32) -> [(key, val)] -> IO (HashTable key val) |
| toList :: HashTable key val -> IO [(key, val)] |
| hashInt :: Int -> Int32 |
| hashString :: String -> Int32 |
| prime :: Int32 |
| longestChain :: HashTable key val -> IO [(key, val)] |
A hash table mapping keys of type key to values of type val. The implementation will grow the hash table as necessary, trying to maintain a reasonable average load per bucket in the table. |
| :: (key -> key -> Bool) | eq: An equality comparison on keys |
| -> (key -> Int32) | hash: A hash function on keys |
| -> IO (HashTable key val) | Returns: an empty hash table |
Creates a new hash table. The following property should hold for the eq and hash functions passed to new: eq A B => hash A == hash B | |
Inserts an key/value mapping into the hash table.
Note that insert doesn't remove the old entry from the table - the behaviour is like an association list, where lookup returns the most-recently-inserted mapping for a key in the table. The reason for this is to keep insert as efficient as possible. If you need to update a mapping, then we provide update.
Updates an entry in the hash table, returning True if there was already an entry for this key, or False otherwise. After update there will always be exactly one entry for the given key in the table.
insert is more efficient than update if you don't care about multiple entries, or you know for sure that multiple entries can't occur. However, update is more efficient than delete followed by insert.
This implementation of hash tables uses the low-order n bits of the hash value for a key, where n varies as the hash table grows. A good hash function therefore will give an even distribution regardless of n.
If your keyspace is integrals such that the low-order bits between keys are highly variable, then you could get away with using id as the hash function.
We provide some sample hash functions for Int and String below.
A sample hash function for Strings. The implementation is:
hashString = fromIntegral . foldr f 0
where f c m = ord c + (m * 128) `rem` 1500007
which seems to give reasonable results.