HashMap

HashMap module: persistent hash-array-mapped-trie map.

HashMap(k, v) is an immutable, hash-indexed key-value store. Unlike Map(k, v), no comparator is needed: key equality uses structural == and hashing uses the built-in polymorphic hash.

Performance (n entries): get / put / delete O(log₃₂ n) ≈ O(1) size / fold / keys O(n)

Key order is hash-traversal order (not insertion order, not sorted). Use Map if you need sorted iteration or Ord-derived equality.

Types

ptypeHEntryHEntry(k, v) =#

ptypeHashMapHashMap(k, v) = HamtHashMap(HEntry(k, v))#

Functions

fndeletedelete(m, key)#

Removes a key from the map. Returns the map unchanged if key is absent.

march> HashMap.has(HashMap.delete(HashMap.put(HashMap.new(), "a", 1), "a"), "a")
false

fnentriesentries(m)#

Returns all (key, value) pairs as a list (hash-traversal order).

fnfilterfilter(m, pred)#

Returns a map containing only entries where pred(key)(value) is true. pred : k -> v -> Bool (curried).

fnfoldfold(m, acc, f)#

Left fold over all entries. f is called as f(acc, key, value) -> new_acc. Iteration order is hash-traversal order (not sorted, not insertion order).

fnfrom_listfrom_list(pairs)#

Builds a HashMap from a list of (key, value) pairs. Later entries overwrite earlier ones for duplicate keys.

march> HashMap.size(HashMap.from_list([("a",1),("b",2),("a",99)]))
2

fngetget(m, key)#

Returns Some(value) if key is present, or None.

march> HashMap.get(HashMap.new(), "missing")
None

fnget_orget_or(m, key, default)#

Returns the value for key, or default if the key is absent.

fnhashas(m, key)#

Returns true if key is present.

fnis_emptyis_empty(m)#

Returns true if the map contains no entries.

fnkeyskeys(m)#

Returns all keys as a list (hash-traversal order).

fnmap_valuesmap_values(m, f)#

Applies f to each value, returning a new map with the same keys.

fnmergemerge(a, b)#

Merges two maps. When a key appears in both, the value from b takes precedence. O(n log n) in the size of b.

fnmerge_withmerge_with(a, b, f)#

Merges two maps with a combining function for conflicting keys. When key exists in both, value is f(val_from_a)(val_from_b). f : v -> v -> v (curried).

fnnewnew()#

Returns an empty HashMap. No comparator needed.

march> HashMap.is_empty(HashMap.new())
true

fnputput(m, key, val)#

Inserts or replaces a key-value pair. Returns the new map.

march> HashMap.get(HashMap.put(HashMap.new(), "a", 1), "a")
Some(1)

fnsizesize(m)#

Returns the number of key-value pairs. O(n).

fnto_listto_list(m)#

Converts a HashMap to a list of (key, value) pairs (hash-traversal order).

fnupdateupdate(m, key, f)#

Updates a key using a function from Option(v) -> v. None is passed when the key is absent; Some(existing) when present. The function's return value becomes the new value for that key.

march> HashMap.get(HashMap.update(HashMap.new(), "k", fn _ -> 42), "k")
Some(42)

fnvaluesvalues(m)#

Returns all values as a list (hash-traversal order).