Hash Array Mapped Tries in Javascript

The hash array mapped trie (HAMT) is a hash trie storage optimization that uses less space and performs better than a regular hash trie. Building on my coverage of a Javascript hash trie, I overview hash array mapped tries and cover a basic Javascript HAMT implementation.

The example code is written in Khepri and taken from the hamt library. HAMT is based on Clojure’s PersistentHashMap.

Overview

A HAMT is a hash trie where internal node store dense child arrays. A h bit hash is the trie key, and each hash is split into sections of m bits. Internal nodes contain at most 2^m entries for a section of the hash, and the trie has at most h/m levels.

Hash Trie Storage Inefficiency

An internal node may have up to 2^m children, but they usually are only partially full. In a regular hash trie, internal nodes get their children by offset in a 2^m array. Every internal node, even those with a single entry, must maintain this 2^m children array.

// h=4, m=2
// insert 0000 and 1100
{root
    {00 entry:0000}
    {01 empty}
    {10 empty}
    {11 entry:1100}}

Hash tries may be optimized to allocate only real child nodes and expand paths when only needed.

But root in this example would still need an internal array of size 4 to store 2 children. In languages like C++, this storage scheme is a major problem. Every internal node will allocate an array of size 2^m * sizeof(NODE_TYPE).

Javascript does not have the same allocation problem since its arrays are conceptually dynamic objects with index keys. We can treat Javascript arrays as sparse arrays, but most Javascript implementations are optimized for dense arrays and operations like reduce will perform poorly on sparsely populated arrays.

HAMTs

Hash array mapped tries solve the sparsely populated array storage problem. HAMT internal nodes maintain a dense array of children, along with fixed size data for mapping an index in the conceptual 2^m child array to an index in the actual dense child array.

HAMT indexed internal nodes use a 2^m bitmap to track which children exist. The dense child array is kept sorted.

// same as before, but we dont need empty nodes
{root bitmap:1001
    {00 entry:0000}
    {11 entry:1100}}

Lookup

Lookups are performed the same as with hash tries. Sections of a hash are progressively matched against internal nodes until the entire hash has been matched. This checks at most h / m nodes.

Indexed node lookup is a bit more complicated than with a hash trie because internal nodes have to convert an index in a 2^m child array to an index in their dense array of children.

We can check if a child at an index exists by checking if the node’s bitmap is set at that index.

// pseudo code
var exists = \node_mask, hash_fragment ->
    node_mask & (1 << hash_fragment);

exists(0b1001, 0); // 0b1001 & 0b0001 // true
exists(0b1001, 1); // 0b1001 & 0b0010 // false
exists(0b1001, 2); // 0b1001 & 0b0100 // false
exists(0b1001, 3); // 0b1001 & 0b1000 // true

If a child exists, we need to determine its position in the dense children array. For a given index, the number of bits set in the bitmap below that index (the population count) is the number of children before the target child. This becomes the index of the target child in the dense array.

// pseudo code
// assume `exists` was trie
var getChild = \node, hash_fragment ->
    node.dense_children.(
        get_count_before(node.mask, hash_fragment));

Updates

Updates rebuild at most h/m internal nodes on a path, with the cost of rebuilding an internal node being at most the cost to rebuild an array of size 2^m.

Indexed node updates use the same lookup logic to see if a child exists. If it does, the dense child array is rebuilt with the new child replacing the existing one. If the child does not exist, an entry is inserted in order into the dense array and the bitmap is set at the index.

Javascript Implementation

In Javascript, we will use a 32 bit hash, split into 5 bit sections.

var HASH_SIZE = 32;

var SIZE = 5;

var BUCKET_SIZE = Math.pow(2, SIZE); // 32

Once indexed node reaches a set capacity, they will be converted to an array. An array node is a hash trie style internal node with a sparse child array. Our indexed nodes will contain at most 16 entries and use a 32 bit bitmap. Array Nodes will contain at most 32 entries.

// Size when we convert an indexed node to an array node
var MAX_INDEX_NODE = BUCKET_SIZE / 2; // 16

// Size when we convert an array node to an indexed node
var MIN_ARRAY_NODE = BUCKET_SIZE / 4; // 8

Hash Fragments

The hash function from hash trie converts a string key to a hash.

hashFragment gets the part of a hash we are interested in at a given level. It takes a hash h and a shift (which is a multiple of SIZE), and returns only the SIZE bit section of the hash we are interested in.

var MASK = BUCKET_SIZE - 1; // 0b11111

var hashFragment = \shift h ->
    (h >>> shift) & MASK;

Bit operations

HAMTs use two additional bit operations.

toBitmap converts a hash fragment (true child index) to a 32bit bitmap with the bit at index frag set.

var toBitmap = \frag -> 1 << frag;

fromBitmap converts a hash fragment (true child index) to an index in a dense child array with a given bitmap. fromBitmap gets the bit population count using popcount.

/// Taken from: http://jsperf.com/hamming-weight
var popcount = let
    m1 = 0x55555555,
    m2 = 0x33333333,
    m4 = 0x0f0f0f0f
in
    \x -> let
        x = x - ((x >> 1) & m1),
        x = (x & m2) + ((x >> 2) & m2),
        x = (x + (x >> 4)) & m4,
        x = x + (x >> 8),
        x = x + (x >> 16)
    in
        (x & 0x7f);


var fromBitmap = \bitmap, frag ->
    popcount(bitmap & (toBitmap(frag) - 1));

Node Structures

The leaf nodes types are the same as in a hash trie.

var LeafNode = function \hash key value =self-> {
    self.hash = hash;   // Complete hash of the key
    self.key = key;     // Key of the leaf
    self.value = value; // Value stored for key.
};

var CollisionNode = function \hash children =self-> {
    // Complete hash of the leaf
    self.hash = hash;           
    
     // List of `LeafNode` with same hash but different keys
    self.children = children;  
};

The empty leaf node empty, is used in the implementation and to represent an empty trie.

empty = null;

IndexedNode stores a dense array of children and a bitmap of which children in a 2^m array exist.

var InternalNode = function \mask children =self-> {
    // bitmap of which children exist in the real child array.
    self.mask = count;
    
    // Dense array of children
    self.children = children;
};

ArrayNode is the same as the hash trie InternalNode. It manages an array children, addressable by hash fragment offsets into a sparsely populated array. Only children that actual exist are set in the array.

var ArrayNode = function \count children =self-> {
    self.count = count; // Number of real children
    self.children = children; // Array mapping hash fragment to child.
};

Lookups

Looking up an entry is the same process as with a hash trie; simply descend a path of internal nodes using progressive hash fragments until a leaf is found. The same nothing values will also be used in HAMT

lookup takes a node n, the current shift (level * SIZE), the complete lookup hash h, and the lookup key k

var isEmpty = (!);

var lookup = \shift h k n ->
    ?isEmpty n
        :nothing
        :n.lookup(shift, h, k);

Lookup operations are specialized for each node type.

LeafNode::get

Leaf nodes return nothing if the lookup key is not equal to the node’s key.

LeafNode.prototype.get = \_ _ k =self->
    ?k === self.key
        :self.value
        :nothing;

CollisionNode::get

Collision nodes return the first matching value in their collision list, or nothing.

CollisionNode.prototype.get = \_ _ k ={children}-> {
    for (var i = 0, len = children.length; i < len; i = i + 1)
    with {key value} = children.(i) in {
        if (k === key)
            return value;
    }
    return nothing;
};

IndexedNode::get

IndexedNodes use shift to calculate a hash fragment and check if the target child exists using their mask. If the child does exist, its index in the dense array children is computed using fromBitmap. Lookup continues on the child. Since the child lookup happens at the next level of the tree, the shift is incremented. When the child does not exist, lookup returns nothing.

IndexedNode.prototype.lookup = \shift h k =self-> let
    frag = hashFragment(shift, h),
    bit = toBitmap frag,
    exists = self.mask & bit
in
    ?exists
        :lookup(
            self.children.(fromBitmap(self.mask, frag)),
            shift + SIZE,
            h,
            k)
        :nothing;

ArrayNode::get

Array nodes use shift to calculate a hash fragment, get a child from children using the hash fragment, and perform a lookup on this child. When the child is undefined, lookup returns nothing.

ArrayNode.prototype.lookup = \shift h k =self-> let
    frag = hashFragment(shift, h),
    child = self.children.(frag)
in
    lookup(child, shift + SIZE, h, k);  

API

/// Get value for `k` or return `alt`.
tryGet = \alt k m  ->
    maybe(
        lookup(m, 0, hash k, k),
        alt);

/// Get the value for `k` or return `null`
getHash = tryGet @ null;

/// Does an entry for `k` exist?
has = \k m ->
    !isNothing lookup(m, 0, hash k, k);

Updates

Updates take a hash trie and return a new hash trie with the update applied. Like lookup, updates walk a path of internal nodes until finding a leaf. But instead of returning a value, updates edit the leaf and then reconstruct all nodes on the path back to the root in reverse order.

HAMT update logic is much the same as hash trie. A single alter function handles updates, deletes, and modifications. alter takes a node n, shift, function f which maps the current node value to a new node value, target hash h, traget key k.

var alter = \n shift f h k ->
    ?isEmpty n
        :alterEmpty(shift, f, h, k)
        :n.modify(shift, f, h, k);

Deletes occur when f returns nothing, while inserts occur when an empty node is edited and f does not return nothing. Otherwise the edit is a modification.

empty::modify

Editing an empty node calls the modify function f with zero arguments. If f does not return nothing, a new node is inserted.

var alterEmpty = \_ f h k ->
    v = f()
in
    ?isNothing v
        :empty // noop
        :new Leaf(h, k, v); // insert node

LeafNode::modify

Leaf nodes are handled the much same as with hashtrie. There are two cases: the leaf itself is being modified, or the leaf is the last element of a path and may be expanded to an IndexedNode.

Leaves are edited if their key matches the target key. In this case, the edit function may either delete the node by returning nothing, or edit the node by returning a new value.

When modify is called on a leaf node and the target key does not match the node, instead of editing the leaf, a new node may be inserted. If a new leaf is inserted, the current leaf and new leaf nodes are merged to become descendants of a new internal node.

LeafNode.prototype.modify = \shift f h k =self->
    ?k === self.key
        // Editing leaf
        :let v = f(self.value) in
            ?isNothing v
                :empty  // delete
                :new LeafNode(h, k, v) // edit
        
    // Potential expansion
    :let v = f() in
    ?isNothing v
        :self // noop
        :mergeLeaves(shift, self, new LeafNode(h, k, v)); // insertion

Two leaf nodes are merged recursively. Internal node levels are inserted until the two nodes no longer have conflicting hash fragments. Collisions occur when nodes have the same hash.

var mergeLeaves = \shift n1 n2 -> let
    h1 = n1.hash,
    h2 = n2.hash
in
    ?h1 === h2
        :new CollisionNode(h1, [n2, n1])
    
    :let
        subH1 = hashFragment(shift, h1),
        subH2 = hashFragment(shift, h2)
    in new IndexedNode(toBitmap subH1 | toBitmap subH2,
        ?subH1 === subH2
            // recursively merge next level
            :[mergeLeaves(shift + SIZE, n1, n2)]
            
            // Found lowest level, insert both children in order.
            :?subH1 < subH2 :[n1, n2] :[n2, n1]);

CollisionNode::modify

Collision nodes modify the matching leaf in their collision list. Deleted nodes are removed from the collision list. If a deletion results in a collision with one entry, the list is collapsed into a leaf node.

CollisionNode.prototype.modify = \_ f h k =self-> let
    list = updateCollisionList(self.children, f, k)
in
    ?list.length > 1
        :new CollisionNode(self.hash, list)
        
        // collapse collision to leaf
        :list.(0); 

updateCollisionList takes a list of leaf nodes and returns a new list with the leaf with key k updated. If f returns nothing,

var updateCollisionList = \list f k ->
    ? !list.length
        :[]
    
    :let first = list.(0), rest = list.slice(1) in
    ?first.key === k
        // found node to edit
        :let v = f(first.value) in
            ?isNothing v
                :rest // deletion
                :[v].concat(rest) // edit
                
        // continue search on rest of list.
        :[first].concat(updateCollisionList(rest, f, k));

IndexedNode::modify

Modifying an indexed node is the most complicated operation. Child modification may either edit an existing child, insert a new child, or delete an existing child. Empty internal nodes are collapsed, while large indexed nodes are expanded to ArrayNode.

The child is edited with alter, increasing the shift by SIZE since the child is at the next level of the trie.

IndexedNode.prototype.modify = \shift f h k =self-> let
    frag = hashFragment(shift, h),
    bit = toBitmap frag,
    indx = fromBitmap(self.mask, frag),
    exists = self.mask & bit,
    
    // New child
    child = alter(
        ?exists
            :self.children.(indx)
            :empty,
        shift + size,
        f,
        h,
        k),
    
    // What type of edit was this
    removed = exists && isEmpty child,
    added = !exists && !isEmpty child,
    
    // Number of children after edit.
    bound = ?removed
        :self.children.length - 1
        :?added
            :self.children.length + 1
            :self.children.length,
    
    // New dense array of children
    subNodes = ?removed
        :arraySpliceOut(indx, self.children)
        :?added
            :arraySpliceIn(indx, child, self.children)
            :arrayUpdate(indx, child, self.children),
    
    // New bitmap
    bitmap = ?removed
        :self.mask & ~bit // Unset index bit
        :?added
            :self.mask | bit // Set index bit
            :self.mask
in
    ?!bitmap
        // The node has no children. Collapse to empty
        :empty
        
    :?bound <= 0 && isLeaf(self.children.(0))
        // We have a single, leaf child. Collapse to it
        :self.children.(0)
        
    :?bound >= MAX_INDEX_NODE
        // Build ArrayNode for this node
        :expand(bitmap, subNodes)
    
    // Rebuild node
    :new IndexedNode(bitmap, subNodes);

The child array update operations copy the array, then update it. This copies at most 16 elements.

var arrayUpdate = \at v arr -> {
    var out = arr.slice(); // copy
    out.(at) = v;
    return out;
};

var arraySpliceIn = \at v arr -> {
    var out = arr.slice(); // copy
    out.splice(at, 0, v);
    return out;
};

var arrayRemove = \at arr -> {
    var out = arr.slice(); // copy
    delete out.(at);
    return out;
};

expand take IndexedNode data and expands it to an ArrayNode. This iterates though the bitmap, inserting children that exist into a new sparse array.

var expand = \bitmap subNodes -> {
    var arr = [],
        count = 0;
    for (var bit = bitmap; bit; bit = bit >>> 1) {
        if (bit & 1) {
            arr.(i) = subNodes.(count);
            count = count + 1;
        }
    }
    return new ArrayNode(count, arr);
};

ArrayNode::modify

Modifying an ArrayNode is much the same as with a hash trie. A (potentially empty) child is edited and the children array is rebuilt with the modified child.

Once an array node drops below a set occupancy, it is collapsed back to an IndexedNode with pack.

ArrayNode.prototype.modify = \shift f h k =self-> let
    frag = hashFragment(shift, h),
    child = self.children.(frag), // may be empty
    newChild = alter(child, shift + size, f, h, k)
in
    ?isEmpty child && !isEmpty newChild
        // add
        :new ArrayNode(
            self.count + 1,
            arrayUpdate(frag, newChild, self.children))
        
    :?!isEmpty child && isEmpty newChild
        // remove
        :?self.count - 1 <= minArrayNode
            // Collapse
            :pack(frag, self.children)
            :new ArrayNode(
                self.count - 1,
                arrayRemove(frag, self.children))
        
    // Modify
    :new ArrayNode(
        self.count,
        arrayUpdate(frag, newChild, self.children));

pack takes ArrayNode children and builds a dense array and bitmap for a new IndexedNode.

var pack = \removed elements -> {
    var children = [],
        bitmap = 0;
    
    for (var i = 0, len = elements.length; i < len; i = i + 1)
    with elem = elements.(i) in {
        if (i !== removed && !isEmpty elem) {
            children.push(elem);
            bitmap = bitmap | (1 << i);
        }
    }
    
    return new IndexedNode(bitmap, children);
};

Update API

var constant = \x -> \() -> x;

/// Edit entry for `k` with `f`.
/// `f` maps the current value to a new value.
/// `f` may create a new node if the target does not exist
modify = \k f m ->
    alter(m, 0, f, hash k, k);

// Set entry for `k` to `v`.
setHash = \k v m ->
    modify(m, k, constant v);

/// Remove entry for `k`.
/// Noop if entry does not exist
removeHash = let del = constant nothing in
    \h k m ->
        modify(k, del, m);
var h = set(a, x,
    set(b, y,
        empty);

// Edit node
var h1 = modify(b, \x -> x.charCodeAt(0), h);
get(b, h1); // 121
get(b, h); // ‘y’

// Insert Node
var h2 = set(c, z, h);
get(c, h2); // ‘z’
get(c, h); // null

// Set Node
var h3 = set(b, n, h);
get(b, h3); // ‘n’
get(b, h); // ‘y’

// Remove Node
var h4 = remove(b, h);
get(b, h4); // null
get(b, h); // ‘y’

Folds

Fold aggregates information about every entry in the trie. HAMTs are unordered, so only order independent operations can be used.

Fold operations are one area where HAMT offers a significant performance boost over a regular hash trie. Array.prototype.reduce unfortunately is not optimized for sparse arrays, so dense arrays can be folded much quicker.

fold takes a function f, initial value z, and trie m. f is called with the previous result and the current key and value as in a object:

fold = \f z m ->
    ?isEmpty m
        :z
        :m.fold(f, z);

The specialization for the nodes:

Leaf.prototype.fold = \f z =self->
    f(z, self);

Collision.prototype.fold = \f z ={children}->
    children.reduce(f, z);

IndexedNode.prototype.fold = \f z =self->
    self.children.reduce(fold@f, z);

ArrayNode.prototype.fold = \f z =self->
    self.children.reduce(fold@f, z);

Summary

HAMTs are the fastest persistent hash trie implementation I could find. They perform well, even as the size of the trie grows very large. Fold operations are often up to 10x on HAMTs than on regular hash tries.

The hamt library provides functionality beyond what I have covered here.

Benchmarks

The more optimized hamt library performs very well, and is the fastest persistent hash trie Javascript library that I could find overall, although hash trie is faster in a few cases.

The complete comparison results and the benchmarks are available here.

# Get nth
hamt(10)                      :      5267300.20 +/- 0.18% op/s
hamt(100)                     :      4954966.94 +/- 0.08% op/s
hamt(1000)                    :      4407368.85 +/- 0.23% op/s
hamt(10000)                   :      3695337.18 +/- 0.58% op/s
hamt(100000)                  :      1243284.12 +/- 1.88% op/s


# put nth
hamt(10)                      :      2411455.82 +/- 1.09% op/s
hamt(100)                     :      1207404.50 +/- 3.22% op/s
hamt(1000)                    :      1412272.94 +/- 3.77% op/s
hamt(10000)                   :       910400.84 +/- 1.43% op/s
hamt(100000)                  :       763270.93 +/- 0.87% op/s

# Put n elements
hamt(10)                      :       207869.60 +/- 1.26% op/s
hamt(100)                     :        13720.51 +/- 1.38% op/s
hamt(1000)                    :         1137.66 +/- 1.00% op/s
hamt(10000)                   :           83.73 +/- 4.31% op/s

# remove nth
hamt(10)                      :      1852861.00 +/- 0.99% op/s
hamt(100)                     :      1351888.10 +/- 2.15% op/s
hamt(1000)                    :      1112764.10 +/- 0.90% op/s
hamt(10000)                   :       837521.94 +/- 1.85% op/s
hamt(100000)                  :       515390.29 +/- 1.16% op/s

# Remove n elements
hamt(10)                      :       213287.68 +/- 1.09% op/s
hamt(100)                     :        15783.71 +/- 1.19% op/s
hamt(1000)                    :         1171.56 +/- 0.97% op/s
hamt(10000)                   :           81.63 +/- 5.49% op/s

# Sum with fold
hamt(10)                      :      3381904.03 +/- 0.49% op/s
hamt(100)                     :       329751.18 +/- 0.50% op/s
hamt(1000)                    :        15326.25 +/- 5.44% op/s
hamt(10000)                   :         3322.86 +/- 0.88% op/s

# Keys with fold
hamt(10)                      :      2099750.38 +/- 3.12% op/s
hamt(100)                     :       229922.38 +/- 3.80% op/s
hamt(1000)                    :        14014.31 +/- 1.39% op/s
hamt(10000)                   :         2429.46 +/- 3.07% op/s

Other Notes

Allocation

In languages like C++, HAMT node allocation is more difficult to optimize than with a regular hash trie. HAMT indexed node child arrays may contain between 1 and MAX_INDEX_NODE children, while hash trie children arrays are a fixed size and can be easily allocated from a pool.

popcount

In lower level languages with a small h popcount is a single instruction.