Copyright | (c) Peter Robinson |
---|---|
License | BSD3 (see the file LICENSE) |
Maintainer | Peter Robinson <pwr@lowerbound.io> |
Stability | provisional |
Portability | non-portable (requires concurrency, stm) |
Safe Haskell | None |
Language | Haskell2010 |
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 as the load fraction 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
, lookup
, delete
, readAssocs
, resize
Synopsis
- data HashTable k v
- data Chain k v
- new :: Eq k => Int -> Config k -> IO (HashTable k v)
- newWithDefaults :: (Eq k, Hashable k) => Int -> IO (HashTable k v)
- mkDefaultConfig :: Hashable k => IO (Config k)
- data Config k = Config {
- _scaleFactor :: Float
- _threshold :: Float
- _numResizeWorkers :: Int
- _hashFunc :: k -> Int
- lookup :: Eq k => HashTable k v -> k -> IO (Maybe v)
- insert :: Eq k => HashTable k v -> k -> v -> IO Bool
- insertIfNotExists :: Eq k => HashTable k v -> k -> v -> IO Bool
- update :: Eq k => HashTable k v -> k -> v -> IO Bool
- delete :: Eq k => HashTable k v -> k -> IO Bool
- readAssocs :: Eq k => HashTable k v -> STM [(k, v)]
- readSizeIO :: HashTable k v -> IO Int
- readSize :: HashTable k v -> STM Int
Documentation
Used for chain-hashing.
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
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) Source #
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
Configuration options that may affect the performance of the hash table
Config | |
|
lookup :: Eq k => HashTable k v -> k -> IO (Maybe v) Source #
Lookup the value for the key in the hash table if it exists.
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
.
Updates the value for key k
. If k
is not in the hash table, it skips the update and returns False
.
Deletes the entry for the given key from the hash table. Returns True
if and only if an entry was deleted from the table.
readAssocs :: Eq k => HashTable k v -> STM [(k, v)] Source #
Atomically retrieves list of key-value pairs. If there is a lot of contention going on, this may be very inefficient.