TrieMap
Class TrieMap<K, V>
provides a map from keys of type K
to values of type V
.
The class wraps and manipulates an underlying hash trie, found in the Trie
module.
The trie is a binary tree where element positions are determined using the hash of the keys.
This data structure allows at most MAX_LEAF_SIZE = 8
hash collisions.
Attempts to insert more than 8 keys (whether directly via put
or indirectly via other operations) with the same hash value will trap.
This limitation is inherited from the underlying Trie
data structure.
The class
TrieMap
exposes the same interface as HashMap
.
Runtime and space complexity assumes that hash
, equal
, and other function parameters execute in O(1)
time and space.
Where applicable, runtimes also assume the trie is reasonably balanced.
All iterator-related runtime and space costs refer to iterator construction. The iteration itself takes linear time and logarithmic space to execute.
Creating a map: The equality function is used to compare keys, and the hash function is used to hash keys. See the example below.
import TrieMap "mo:base/TrieMap";
import Nat "mo:base/Nat";
import Hash "mo:base/Hash";
import Iter "mo:base/Iter";
let map = TrieMap.TrieMap<Nat, Nat>(Nat.equal, Hash.hash)
Class TrieMap<K, V>
class TrieMap<K, V>(isEq : (K, K) -> Bool, hashOf : K -> Hash.Hash)
Function size
func size() : Nat
Returns the number of entries in the map.
Example:
map.size()
Runtime | Space |
---|---|
O(1) | O(log(1)) |
Function put
func put(key : K, value : V)
Maps key
to value
, and overwrites the old entry if the key
was already present.
Example:
map.put(0, 10);
map.put(2, 12);
Iter.toArray(map.entries())
Runtime | Space |
---|---|
O(log(size)) | O(log(size)) |
Function replace
func replace(key : K, value : V) : ?V
Maps key
to value
. Overwrites and returns the old entry as an
option if the key was already present, and null
otherwise.
Example:
map.put(0, 10);
map.replace(0, 20)
Runtime | Space |
---|---|
O(log(size)) | O(log(size)) |
Function get
func get(key : K) : ?V
Gets the value associated with the key key
in an option, or null
if it
doesn't exist.
Example:
map.put(0, 10);
map.get(0)
Runtime | Space |
---|---|
O(log(size)) | O(log(size)) |
Function delete
func delete(key : K)
Delete the entry associated with key key
, if it exists. If the key is
absent, there is no effect.
The deletion of an existing key shrinks the trie map.
Example:
map.put(0, 10);
map.delete(0);
map.get(0)
Runtime | Space |
---|---|
O(log(size)) | O(log(size)) |
Function remove
func remove(key : K) : ?V
Delete the entry associated with key key
. Return the deleted value
as an option if it exists, and null
otherwise.
The deletion of an existing key shrinks the trie map.
Example:
map.put(0, 10);
map.remove(0)
Runtime | Space |
---|---|
O(log(size)) | O(log(size)) |
Function keys
func keys() : I.Iter<K>
Returns an iterator over the keys of the map.
Each iterator gets a snapshot view of the mapping, and is unaffected by concurrent updates to the iterated map.
Example:
map.put(0, 10);
map.put(1, 11);
map.put(2, 12);
// find the sum of all the keys
var sum = 0;
for (key in map.keys()) {
sum += key;
};
// 0 + 1 + 2
sum
Runtime | Space |
---|---|
O(1) | O(1) |
Function vals
func vals() : I.Iter<V>
Returns an iterator over the values in the map.
Each iterator gets a snapshot view of the mapping, and is unaffected by concurrent updates to the iterated map.
Example:
map.put(0, 10);
map.put(1, 11);
map.put(2, 12);
// find the sum of all the values
var sum = 0;
for (key in map.vals()) {
sum += key;
};
// 10 + 11 + 12
sum
Runtime | Space |
---|---|
O(1) | O(1) |
Function entries
func entries() : I.Iter<(K, V)>
Returns an iterator over the entries (key-value pairs) in the map.
Each iterator gets a snapshot view of the mapping, and is unaffected by concurrent updates to the iterated map.
Example:
map.put(0, 10);
map.put(1, 11);
map.put(2, 12);
// find the sum of all the products of key-value pairs
var sum = 0;
for ((key, value) in map.entries()) {
sum += key * value;
};
// (0 * 10) + (1 * 11) + (2 * 12)
sum
Runtime | Space |
---|---|
O(1) | O(1) |
Function clone
func clone<K, V>(map : TrieMap<K, V>, keyEq : (K, K) -> Bool, keyHash : K -> Hash.Hash) : TrieMap<K, V>
Produce a copy of map
, using keyEq
to compare keys and keyHash
to
hash keys.
Example:
map.put(0, 10);
map.put(1, 11);
map.put(2, 12);
// Clone using the same equality and hash functions used to initialize `map`
let mapCopy = TrieMap.clone(map, Nat.equal, Hash.hash);
Iter.toArray(mapCopy.entries())
Runtime | Space |
---|---|
O(size * log(size)) | O(size) |
Function fromEntries
func fromEntries<K, V>(entries : I.Iter<(K, V)>, keyEq : (K, K) -> Bool, keyHash : K -> Hash.Hash) : TrieMap<K, V>
Create a new map from the entries in entries
, using keyEq
to compare
keys and keyHash
to hash keys.
Example:
let entries = [(0, 10), (1, 11), (2, 12)];
let newMap = TrieMap.fromEntries<Nat, Nat>(entries.vals(), Nat.equal, Hash.hash);
newMap.get(2)
Runtime | Space |
---|---|
O(size * log(size)) | O(size) |
Function map
func map<K, V1, V2>(map : TrieMap<K, V1>, keyEq : (K, K) -> Bool, keyHash : K -> Hash.Hash, f : (K, V1) -> V2) : TrieMap<K, V2>
Transform (map) the values in map
using function f
, retaining the keys.
Uses keyEq
to compare keys and keyHash
to hash keys.
Example:
map.put(0, 10);
map.put(1, 11);
map.put(2, 12);
// double all the values in map
let newMap = TrieMap.map<Nat, Nat, Nat>(map, Nat.equal, Hash.hash, func(key, value) = value * 2);
Iter.toArray(newMap.entries())
Runtime | Space |
---|---|
O(size * log(size)) | O(size) |
Function mapFilter
func mapFilter<K, V1, V2>(map : TrieMap<K, V1>, keyEq : (K, K) -> Bool, keyHash : K -> Hash.Hash, f : (K, V1) -> ?V2) : TrieMap<K, V2>
Transform (map) the values in map
using function f
, discarding entries
for which f
evaluates to null
. Uses keyEq
to compare keys and
keyHash
to hash keys.
Example:
map.put(0, 10);
map.put(1, 11);
map.put(2, 12);
// double all the values in map, only keeping entries that have an even key
let newMap =
TrieMap.mapFilter<Nat, Nat, Nat>(
map,
Nat.equal,
Hash.hash,
func(key, value) = if (key % 2 == 0) { ?(value * 2) } else { null }
);
Iter.toArray(newMap.entries())
Runtime | Space |
---|---|
O(size * log(size)) | O(size) |