Data.HashTable

You can find benchmarks and more information about the internals of this package here: https://lowerbound.io/blog/2019-10-24_concurrent_hash_table_performance.html

Usage Example:

> ht <- newWithDefaults 4     -- creates hash table of initial size 4
> insert ht 1 "hello"         -- adds key-value pair (1,"hello")
> insert ht 2 "world"         -- adds key-value pair (2,"world")
> atomically $ readAssocs ht  -- convert to a key-value list
 [(1,"hello"),(2,"world")]
> readSizeIO ht               -- returns 4
> insert ht 3 "!"             -- adds key-value pair (3,"!") and triggers a resize since load/size is ≥ 0.75
> readSizeIO ht               -- returns 8
> atomically $ readAssocs ht  -- convert to a key-value list
 [(1,"hello"),(3,"!"),(2,"world")]

List of atomic operations: insert, insertIfNotExists, update, modify, lookup, delete, readAssocs, resize

Data Type

data HashTable k v

A thread-safe hash table that supports dynamic resizing.

data Chain k v

Used for chain-hashing.

Instances

Eq (Chain k v)

Defined in Data.HashTable.Internal

Methods

(==) :: Chain k v -> Chain k v -> Bool

(/=) :: Chain k v -> Chain k v -> Bool

Construction

new

Arguments

:: Eq k

=> Int

Initial size of the hash table

-> Config k

-> IO (HashTable k v)

Creates a new hash table with an initial size. See newWithDefaults for more details. You probably either want to use newWithDefaults instead or something like this: > mkDefaultConfig { _field = myValue } >>= new 10

newWithDefaults

Arguments

:: (Eq k, Hashable k)

=> Int

Initial size of the hash table

-> IO (HashTable k v)

Creates a new hash table with the given initial vector size, scale factor 2.0, a resizing load threshold of 0.75, and we use as many threads for resizing as we have cores available. This will use a hash function with a (single) random salt, so if you need security, you MUST supply your own hash function. To be replaced by universal hashing in future versions.

mkDefaultConfig :: Hashable k => IO (Config k)

Default configuration: scale factor = 2.0; resizing threshold = 0.75; number of worker threads for resizing = getNumCapabilities; hash function = use hashWithSalt with a random salt.

data Config k

Configuration options that may affect the performance of the hash table

Constructors

Config

Fields

• _scaleFactor :: Float

  scale factor for resizing

• _threshold :: Float

  load threshold for initiating resizing.

• _numResizeWorkers :: Int

  maximum number of worker threads used during resizing

• _hashFunc :: k -> Int

Instances

Show (Config k)

Defined in Data.HashTable.Internal

Methods

showsPrec :: Int -> Config k -> ShowS

show :: Config k -> String

showList :: [Config k] -> ShowS

Atomic Operations

lookup :: Eq k => HashTable k v -> k -> IO (Maybe v)

Lookup the value for the key in the hash table if it exists.

insert

Arguments

:: Eq k

=> HashTable k v

-> k

key

-> v

value

-> IO Bool

Inserts the key-value pair k v into the hash table. Uses chain hashing to resolve collisions. If you want to update the entry only if it already exists, use update. If you want to update the entry only if it does *not* exist, use insertIfNotExists.

insertIfNotExists

Arguments

:: Eq k

=> HashTable k v

-> k

key

-> v

value

-> IO Bool

Inserts a key and value pair into the hash table only if the key does not exist yet. Returns True if the insertion was successful, i.e., the hash table did not contain this key before. To get the same behaviour as insert, use insert. If you want to update an entry only if it exists, use update.

update

Arguments

:: Eq k

=> HashTable k v

-> k

key

-> v

value

-> IO Bool

Updates the value for key k. If k is not in the hash table, it skips the update and returns False.

modify

Arguments

:: Eq k

=> HashTable k v

-> k

key

-> (v -> v)

update-function

-> IO Bool

Applies an update-function to the value for key k. If k is not in the hash table, it just returns False.

delete

Arguments

:: Eq k

=> HashTable k v

-> k

key of entry that will be deleted

-> IO Bool

Deletes the entry for the given key from the hash table. Returns True if and only if an entry was deleted from the table.

Utilities

readAssocs :: Eq k => HashTable k v -> STM [(k, v)]

Atomically retrieves list of key-value pairs. If there is a lot of contention going on, this may be very inefficient.

readSizeIO :: HashTable k v -> IO Int

Returns the size of the vector representing the hash table. (Atomic)

readSize :: HashTable k v -> STM Int

Returns the size of the vector representing the hash table.