FunctionalStableHashMap

Mutable hash map (aka Hashtable)

This module is a direct deconstruction of the object oriented HashMap.mo class in motoko-base (https://github.com/dfinity/motoko-base/blob/master/src/HashMap.mo) into a series of functions and is meant to be persistent across updates, with the tradeoff being larger function signatures.

One of the main additions/difference between the two modules at this time besides class deconstruction is the differing initialization methods if an initialCapacity is known (to prevent array doubling slowdown during map initialization)

The rest of this documentation and code therefore follows directly from HashMap.mo, with minor modifications that do not attempt to change implementation. Please raise and issue if a discrepancy in implementation is found.

The class is parameterized by the key's equality and hash functions, and an initial capacity. However, as with the Buffer class, no array allocation happens until the first set.

Internally, table growth policy is very simple, for now: Double the current capacity when the expected bucket list size grows beyond a certain constant.

type StableHashMap<K, V> = { initCapacity : Nat; var table : [var KVs<K, V>]; var _count : Nat }

Type signature for the StableHashMap object.

public func init<K, V>() : StableHashMap<K, V>

Initializes a HashMap with initCapacity and table size zero

public func initPreSized<K, V>(initCapacity : Nat) : StableHashMap<K, V>

Initializes a hashMap with given initCapacity. No array allocation will occur until the first item is inserted

public func size<K, V>(map : StableHashMap<K, V>) : Nat

Returns the number of entries in this HashMap.

public func delete<K, V>(
  map : StableHashMap<K, V>,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash,
  k : K
) : ()

Deletes the entry with the key k. Doesn't do anything if the key doesn't exist.

public func remove<K, V>(
  map : StableHashMap<K, V>,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash,
  k : K
) : ?V

Removes the entry with the key k and returns the associated value if it existed or null otherwise.

public func get<K, V>(
  map : StableHashMap<K, V>,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash,
  k : K
) : ?V

Gets the entry with the key k and returns its associated value if it existed or null otherwise.

public func put<K, V>(
  map : StableHashMap<K, V>,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash,
  k : K,
  v : V
) : ()

Insert the value v at key k. Overwrites an existing entry with key k Does not return a value if updating an existing key

public func replace<K, V>(
  map : StableHashMap<K, V>,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash,
  k : K,
  v : V
) : ?V

Insert the value v at key k and returns the previous value stored at k or null if it didn't exist.

public func keys<K, V>(map : StableHashMap<K, V>) : Iter.Iter<K>

An Iter over the keys.

public func vals<K, V>(map : StableHashMap<K, V>) : Iter.Iter<V>

An Iter over the values.

public func entries<K, V>(map : StableHashMap<K, V>) : Iter.Iter<(K, V)>

Returns an iterator over the key value pairs in this HashMap. Does not modify the HashMap.

public func clone<K, V>(
  h : StableHashMap<K, V>,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash
) : StableHashMap<K, V>

clone cannot be an efficient object method, ...but is still useful in tests, and beyond.

public func fromIter<K, V>(
  iter : Iter.Iter<(K, V)>,
  initCapacity : Nat,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash
) : StableHashMap<K, V>

Clone from any iterator of key-value pairs

public func map<K, V1, V2>(
  h : StableHashMap<K, V1>,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash,
  mapFn : (K, V1) -> V2
) : StableHashMap<K, V2>

public func mapFilter<K, V1, V2>(
  h : StableHashMap<K, V1>,
  keyEq : (K, K) -> Bool,
  keyHash : K -> Hash.Hash,
  mapFn : (K, V1) -> ?V2
) : StableHashMap<K, V2>