hashtables-1.2.1.0: Mutable hash tables in the ST monad

Safe HaskellSafe
LanguageHaskell98

Data.HashTable.Class

Description

This module contains a HashTable 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.:

import qualified Data.HashTable.IO as H

type HashTable k v = H.BasicHashTable k v

foo :: IO (HashTable Int Int)
foo = do
    ht <- H.new
    H.insert ht 1 1
    return ht

or

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 <- H.new
    H.insert ht 1 1
    return ht

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.

Note that the functions in this typeclass are in the ST monad; if you want hash tables in IO, use the convenience wrappers in Data.HashTable.IO.

Synopsis

Documentation

class HashTable h where Source #

A typeclass for hash tables in the ST monad. The operations on these hash tables are typically both key- and value-strict.

Minimal complete definition

new, newSized, insert, delete, lookup, foldM, mapM_, computeOverhead

Methods

new :: ST s (h s k v) Source #

Creates a new, default-sized hash table. O(1).

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

Creates a new hash table sized to hold n elements. O(n).

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

Inserts a key/value mapping into a hash table, replacing any existing mapping for that key.

O(n) worst case, O(1) amortized.

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

Deletes a key-value mapping from a hash table. O(n) worst case, O(1) amortized.

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

Looks up a key-value mapping in a hash table. O(n) worst case, (O(1) for cuckoo hash), O(1) amortized.

foldM :: (a -> (k, v) -> ST s a) -> a -> h s k v -> ST s a Source #

A strict fold over the key-value records of a hash table in the ST monad. O(n).

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

A side-effecting map over the key-value records of a hash table. O(n).

computeOverhead :: h s k v -> ST s Double Source #

Computes the overhead (in words) per key-value mapping. Used for debugging, etc; time complexity depends on the underlying hash table implementation. O(n).

Instances

HashTable HashTable Source # 

Methods

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

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

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

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

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

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

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

computeOverhead :: HashTable s k v -> ST s Double Source #

HashTable HashTable Source # 

Methods

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

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

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

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

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

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

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

computeOverhead :: HashTable s k v -> ST s Double Source #

HashTable HashTable Source # 

Methods

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

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

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

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

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

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

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

computeOverhead :: HashTable s k v -> ST s Double Source #

fromList :: (HashTable h, Eq k, Hashable k) => [(k, v)] -> ST s (h s k v) Source #

Create a hash table from a list of key-value pairs. O(n).

fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) => Int -> [(k, v)] -> ST s (h s k v) Source #

Create a hash table from a list of key-value pairs, with a size hint. O(n).

toList :: HashTable h => h s k v -> ST s [(k, v)] Source #

Given a hash table, produce a list of key-value pairs. O(n).