Persistent Data Structure: HAMT

• Chunk 1 (least significant 5 bits):
  • 01101 = 0x0D
• Chunk 2 (next 5 bits):
  • 00101 = 0x05
• Chunk 3 (next 5 bits):
  • 10011 = 0x13
• Chunk 4 (remaining 1 bit):
  • 0 = 0x00

Hash Chunk Algorithm

It’s not hard to come up with a way to take a 16-bit number then partition it by 5 bits with the last being the remaining bits.

But, there is a way to improve upon what may be the intuitive or simple way of implementing this. Not everyone thinks of bitwise operations for doing arithmetic. That is, we can do this

def get_chunks_from_hash(hash_value: int) -> list[int]:
    # n is chunk_size: 2^n - 1 = 0x1F = 31 = 0b11111
    return [
        hash_value & 0x1F,          
        (hash_value >> 5) & 0x1F,
        (hash_value >> 10) & 0x1F,
        (hash_value >> 15) & 0x1,
    ]

You can parameterize chunk_size and hash_bits then yield values instead of returning a list, but I’ll leave that to you.

2. Sparse Node Representation

Bitmap and Values Array

These are 2 vitals components that are defined in each non-leaf node.

The bitmap: a 32-bit integer where each bit corresponds to one of the 32 possible child positions in a HAMT node. Because each chunk is 5 bits (chunk value in range [0_0000, 1_1111]), there’s 2^5 possibilities of different children at each non-leaf node.

• Bit position 0 represents the first possible child
• Bit position 1 represents the second possible child

And so on up to bit position 31 representing 32nd possible child

If a bit is set to 1, it means the corresponding child exists. If it’s 0, that child doesn’t exist.

The values array: an array of values which are each a pointer to a child node. This allows us to have sparse trie. If we were to directly use the chunked hash as an index to child node, we would allocate more memory than need be. If we used a hashmap/dict to store hash_chunk -> child pointer, we’re creating more overhead than required. A new child results in a push. A revisited branch (chunked hash) results in a lookup to the values array given an index. It begins as an empty array.

Insert in Empty Trie

Suppose we insert a key-value, user123: James whose (key) hash is 0x4cad whose first chunk is 0x0d (decimal 13):

1. An empty HAMTs is just an empty root node:

• Bitmap: 0x0000_0000
• Values array: []

2. Insert a child doing a lookup/record in the bitmap:

• Since it’s a miss in the bitmap lookup (explained later), we will record this chunk in the bitmap instead
• Set bit 13 in the bitmap resulting in bitmap being 0x0000_2000 (1 shifted left by 13 positions, that is, hex(1 << 13))
• Push a new child node in the values array

3. After insertion:

4. We continue to the next child lookup/record given the next chunk (0x05 or decimal 5):

• Bitmap miss, so create a new node with bitmap 0x0000_0020 (bit 5 set, hex(1 << 5))
• Push a new child to its values array

5. And so on until we run out of chunks then update/create a (leaf) child which holds the key-value

Each leaf node will have a null bitmap and values array values, or better yet, be a different type than the other nodes.

At each level, the bitmap efficiently tracks which of the possible 32 children actually exist, while the values array only stores those children, keeping the structure memory-efficient even as it grows.

Bitmap Lookup

What happens when the chunked bits match an existing record in the bitmap?

Previously, we inserted key-value with hash 0x4cad = 0b0100_1100_1010_1101 and started to show our the nodes are inserted into an empty trie as shown above.

Now, let’s insert a key-value whose hash starts with 0x0d = 0b0_1101.

def bitmap_lookup(bitmap: int, chunk: int) -> tuple[bool, int]:
    mask = 1 << chunk                       # 0x2000
    exists = (bitmap & mask) != 0           # True
    below = mask - 1                        # 0x1fff
    index = bin(bitmap & below).count('1')  # 0
    return exists, index

print(bitmap_lookup(0x2000, 0x0d))

Note: bin(number).count('1') is like a popcount or popcnt call which counts the numbers of bits set to 1 in a number.

With that, we can re-use the child in values array at index 0.

Values Array Insert

If you noticed, we can insert a few key-value whose hash chunk is larger, then insert another key-value whose hash chunk is smaller causing each index to be calculated as 0.

Say at depth 1, we see:

• insert key1 with chunk 2, index is 0
• insert key2 with chunk 1, index is 0

On, the 2nd insert, we need to actually insert into the list/array (or doing an array copy to help shift).

After the array update,

• calc the index for chunk 2, we get index 1
• calc the index for chunk 1, we get index 0

Since we had a bitmap hit (exists = true), we know we have a child for this chunk already. But there’s some use cases we need to account for as a new chunk can insert into this array, possibly pushing some others back.

This is an implementation detail, but the steps for this insert given the next calculated index would be:

• copy array[0:index] to new array
• push new or existing pointer to child to new array
• if we pushed new child, concat array[index:] to new array, else, concat array[index + 1:]
  • we would concat array[index + 1:] because what we pushed is replacing what was at array[index]

Hash Conflicts

If I’m telling you 65,536 is the max key-space of the trie, but also suggesting it will only take O(n) space, something may feel amiss. That is, we’ll get hash conflicts for different keys eventually.

How would we know a hash conflict would occur? We could do one or both of the following:

1. compare full hash to leaf full hash
2. compare key to leaf key

The 2nd option then requires your key to implement an interface for comparing itself to another key. Typically, your keys are all the same data type, making this easy enough.

How would we handle a hash conflict? When hash conflicts occur in persistent data structures like HAMTs, several techniques can be used to handle them effectively:

• Path copying with node extension - When a collision occurs, convert the leaf node into a collision node that stores multiple key-value pairs with the same hash path
• Nested tries - Instead of storing colliding values in a list, create a nested trie structure at the collision point using the remaining bits of the hash
• Hash function adaptation - Use a secondary hash function for keys that collide at the bottom level
• Incremental path extension - Dynamically increase the trie depth only along paths with collisions

What’s the probability a hash conflict occurs? Depends on the hash function and number of keys stored relative to the hash space.

We can use the birthday paradox as a mathematical model to calculate the approximate probability.

The birthday paradox refers to the counterintuitive probability that in a group of just 23 people, there’s about a 50% chance that at least two people share the same birthday.

The formula for the birthday paradox is

where n is the number of people (or samples)
where d is all possible values (birthdays or hash values in a hash space)

P(n) = 1 - (365! / ((365 - n)! * 365^n))
P(n) = 1 - product_reduce(i = 0 to n - 1, (365 - i) / 365)
P(n) = 1 - product_reduce(i = 0 to n - 1, (d - i) / d) 

We could then go on to determine our hash func, say python hash, measured hash space, approximate our probability for hash conflicts, and calculate/plot for values n.

But in practice, in HAMT implementations:

If using full cryptographic hashes (like SHA-256), collisions are very rare. If using simpler hash functions or truncated hashes, conflicts become more likely. When storing just thousands of elements with 32-bit hashes, you’d expect few collisions. The more bits you use for indexing at each level, the lower the probability of collisions at deep levels.

In a HAMT implementation, we would use bigger values than what I’m using throughout this article, such as:

• full hash: cryptographic SHA-256 hash (256 bits)
• truncated hash: take the first 64 bits
• use a chunk size larger than 5 bits to reduce collision probability
• handle hash collisions with a simple implementation such as hashmap {full_hash: (key, value)} at leaves

3. Path Copying for Persistence

When modifying a HAMT, only the nodes along the path to the modified element are copied, allowing efficient creation of new versions:

Performance Characteristics

HAMTs offer excellent performance characteristics:

• Lookup/Insert/Delete: O(log_base_32 n) ≈ O(log n), but practically close to O(1) for most realistic datasets
• Memory Efficiency: Much more space-efficient than naive copying for immutability
• Cache Performance: Good locality of reference due to the trie structure

Space Complexity

It’s good to note that the max children at each depth is (2^chunk_size_bits) * nodes_at_prev_depth. For this example, we’ve truncated the hash to be 4 hexadecimal digits (16 bits) with chunk_size_bits = 5. At depth = 0, we have 1 node, the root (special case). At depth = 1, we have <= (2^5) * 1 (32) children. At depth = 2, we have <= (2^5) * (2^5 * 1) (1024) children. At depth = 3, we have <= (2^5) * ((2^5) * (2^5 * 1)). At depth 4, our chunk size lowers from 5 to 1 as the prior chunks used the first 15 bits of our 16-bit hash. At depth 4, we have <= (2^1) * ((2^5) * ((2^5) * (2^5 * 1))). We know the depth will always be 4 for recording the hash of the key-values for our example meaning our trie would have 1 (root) + 32 (depth 1) + 1_024 (depth 2) + 32_768 (depth 3) + 65_536 (depth 4) + 65_536 (leafs). If we somehow built a full trie, it would have 164,897 nodes. From the (2^1) * ((2^5) * ((2^5) * (2^5 * 1))) we might derive that it takes O(32^n) space, but this is not what it actually takes thanks to the way hashing works. That’s the easy answer, there’s a proof to this, but I won’t spell out here. It takes O(n) space is the answer.

65,536 is awfully small capacity for key-space. This limit can be determined by 2^hash_bits. There’s no reason we couldn’t adjust different parameters such as the hash_bits. We chose 16 here for the sake of brief illustration by examples.

Comparison with Other Data Structures

HAMTs excel in scenarios requiring both immutability and performance:

Practical Applications

HAMTs are widely used in:

1. Functional Programming Languages

   • Clojure’s persistent collections (PersistentHashMap)
   • Scala’s immutable collections (immutable.HashMap)
   • Haskell’s unordered containers

2. Version Control Systems

   • Git-like data versioning
   • Efficient storage of multiple versions

3. Database Systems

   • Immutable databases like Datomic
   • Time-travel query capabilities

4. State Management in UIs

   • React/Redux state handling
   • Undo/redo functionality

Concrete Example: Simple HAMT Implementation

Here’s a simplified example of HAMT insertion in JavaScript:

import os
import math

assert os.environ['PYTHONHASHSEED'] == '0'  # set prior to runtime

HASH_BITS = 16
CHUNK_SIZE = 5
MAX_LEVEL = math.ceil(HASH_BITS / CHUNK_SIZE)

def insert(node, key, value, hash_val, max_level, level=0):
    # Create a copy of the node (for persistence)
    new_node = node.copy() if node else {}
    
    # At maximum level, store the value
    if level >= max_level:
        entries = new_node.get('entries', []).copy()
        entries.append({'key': key, 'value': value})
        new_node['entries'] = entries
        return new_node
    
    # Extract 5 bits from the hash at the current level
    chunk = (hash_val >> (level * 5)) & 0x1f  # 0x1f = 31 (5 bits)
    bit = 1 << chunk
    
    # Check if the path exists in the bitmap
    bitmap = new_node.get('bitmap', 0)
    exists = (bitmap & bit) != 0
    index = bin(bitmap & (bit - 1)).count('1')  # Count bits to find index
    
    # Create or update the children array
    children = new_node.get('children', []).copy()
    
    if exists:
        # Path exists, recursively update the child
        children[index] = insert(children[index], key, value, hash_val, max_level, level + 1)
    else:
        # Create a new path
        new_child = {'bitmap': 0, 'children': []}
        children.insert(index, insert(new_child, key, value, hash_val, max_level, level + 1))
        # Update bitmap to include the new bit
        new_node['bitmap'] = bitmap | bit
    
    new_node['children'] = children
    return new_node


from pprint import pprint  # std lib

# Create an empty root node
version0 = {'bitmap': 0, 'children': []}

# Insert some key-value pairs
version1 = insert(version0, 'apple', 'red', hash('apple'), MAX_LEVEL)
version2 = insert(version1, 'banana', 'yellow', hash('banana'), MAX_LEVEL)
version3 = insert(version2, 'user123', 'James', hash('user123'), MAX_LEVEL)

pprint(version3)

From the pretty print of version3 (dictionary), we get

{'bitmap': 8208,
 'children': [{'bitmap': 266240,
               'children': [{'bitmap': 8192,
                             'children': [{'bitmap': 8388608,
                                           'children': [{'bitmap': 0,
                                                         'children': [],
                                                         'entries': [{'key': 'banana',
                                                                      'value': 'yellow'}]}]}]},
                            {'bitmap': 8,
                             'children': [{'bitmap': 67108864,
                                           'children': [{'bitmap': 0,
                                                         'children': [],
                                                         'entries': [{'key': 'apple',
                                                                      'value': 'red'}]}]}]}]},
              {'bitmap': 32,
               'children': [{'bitmap': 524288,
                             'children': [{'bitmap': 1024,
                                           'children': [{'bitmap': 0,
                                                         'children': [],
                                                         'entries': [{'key': 'user123',
                                                                      'value': 'James'}]}]}]}]}]}

We can see that banana and apple keys share 2 nodes.

Future Work

• Serialization
• Encoding tables and records with record id auto-increment
• Resource locked transaction
• Query records throughout changelog
• Implement in Elixir

Conclusion

Hash Array Mapped Tries represent a remarkable engineering achievement in data structure design. They elegantly solve the seemingly contradictory requirements of performance and immutability, enabling efficient persistent data structures that are fundamental to functional programming, version control systems, and modern application development.

The combination of hash-based lookup, trie organization, and bit-level optimizations makes HAMTs a powerful tool in any programmer’s toolkit, especially when immutability and versioning are required without sacrificing performance.

As functional programming patterns and immutable data gain broader adoption, persistent data structures can get more exposure. Understanding HAMTs provides valuable insight into how efficient persistent data structures can be implemented in practice.