A hash table you don't need to rehash

This data structure is called a Hash Array Mapped Trie, or HAMT. It's a hash table built as a tree of small tables, and it has two properties that make it really useful.

It grows without ever being rehashed. When a normal hash table is getting pretty full, you create a bigger one, recalculate where every value goes and add them all again. That can be pretty slow, and it happens right in the middle of adding something. A HAMT only ever allocates one small node at a time.

It's also immutable. Nothing in it is ever changed: setting a key gives you a new version, which shares every node with the old version except the few on the path to that key. The old version stays valid for as long as you hold on to it, so undo, snapshots and handing data to other parts of a program without it changing under them all come almost for free. This is why HAMTs are behind the immutable maps in Clojure, Scala and Immutable.js.

Let's start with a small one, and then build the real thing.

The idea

Let's make a small hash table that has four slots and that we index using two bits of a hash value.

Now we add some items to it, A (hash 00), B (hash 10) and C (hash 01):

Let's say that we want to add D, whose hash also ends in 10. The problem is that it would collide with B. Instead of making a bigger table, let's allocate a new small table, put it in slot 10, and move B down into it.

Now we need more bits from the hash values. Let's say the hash of B ends with 0010 and the hash of D ends with 0110. The lowest two bits (10) were already used for the index in the first table, so we use the next two bits as the index in the second table: 00 for B and 01 for D.

If we continue like this, we can add as many values as we like without needing to rehash or do any other expensive operation, other than allocating some memory.

To find a value, we first calculate the hash (0110 for D). Then we look at the lowest two bits (10) in the root table. There's a table there rather than a value, so we continue with the next two bits (01) in the second table. Here we find the value D that we are looking for.

Removing a value is really easy too. If we remove D, the second table only has B left in it, so B moves back up into slot 10 and the second table goes away.

32 slots and a bitmap

Four slots make a deep tree. A real HAMT uses 32 slots in each node, indexed by five bits of the hash at a time, so a 32-bit hash lasts for seven levels: six of five bits, and one of two.

Most nodes only use a few of their 32 slots, though, so storing all 32 would waste a lot of memory. Instead, each node (called a branch) holds a 32-bit bitmap with a bit set for each slot that's in use, and an array of just those entries, in slot order.

To find the entry for a slot, count how many bits are set below that slot's bit. That count is the entry's position in the array. Counting bits is called popcount, and most CPUs do it in a single instruction.

That's the "array mapped" part of the name: the bitmap maps 32 slots onto a short array.

There's one more difference from the small example. Values only live in leaves at the ends of the tree, never in a branch, and a slot holds either a leaf or another branch. When two keys collide, the one that was there moves down into a new branch along with the new one, just as B did.

The code

Here's a complete persistent HAMT in JavaScript, mapping string keys to values. Let's go through it one operation at a time. The whole file is at the bottom of the page.

Hashing and indexing

First, the hash. Any good 32-bit hash will do. This one is FNV-1a, which is short and spreads strings out well:

const BITS = 5;               //  Bits of the hash used at each level
const WIDTH = 1 << BITS;      //  32 slots in a node
const MASK = WIDTH - 1;       //  0b11111

//  FNV-1a, a simple 32-bit string hash
function hash(key) {
  let h = 0x811c9dc5;
  for (let i = 0; i < key.length; i++) {
    h ^= key.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

Then three small functions do all the indexing. fragment takes the five bits for a level, popcount counts the bits set in a number, and index uses it to turn a slot into a position in a branch's array. JavaScript has no popcount built in, so it adds the bits up in pairs, then fours, then bytes:

//  The number of bits set in a 32-bit value
function popcount(x) {
  x = x - ((x >>> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
  x = (x + (x >>> 4)) & 0x0f0f0f0f;
  return Math.imul(x, 0x01010101) >>> 24;
}

//  Which of the 32 slots a hash falls in at this level
function fragment(h, shift) {
  return (h >>> shift) & MASK;
}

//  Where a slot's entry is in the packed array: the number of used slots below it
function index(bitmap, bit) {
  return popcount(bitmap & (bit - 1));
}

bit - 1 has every bit below the slot's bit set, so bitmap & (bit - 1) keeps just the used slots below it.

The nodes

There are three kinds of node: a leaf with one key and value, a branch with its bitmap and entries, and a collision node for keys whose hashes are exactly the same (more on those below). An empty map is a branch with nothing in it:

//  A leaf holds one key, its value and the key's full hash
function Leaf(h, key, value) {
  return { type: 'leaf', hash: h, key, value };
}

//  A branch holds a bitmap of its used slots and an array of just those entries
function Branch(bitmap, entries) {
  return { type: 'branch', bitmap, entries };
}

//  Keys whose whole 32-bit hash is the same share a collision node
function Collision(h, leaves) {
  return { type: 'collision', hash: h, leaves };
}

const EMPTY = Branch(0, []);

Once a node is made, it's never changed. Every change to a map makes new nodes instead, and these three helpers are all that takes: each one returns a copy of an array with one entry replaced, inserted or removed.

function arraySet(array, i, value) {
  const copy = array.slice();
  copy[i] = value;
  return copy;
}

function arrayInsert(array, i, value) {
  return [...array.slice(0, i), value, ...array.slice(i)];
}

function arrayRemove(array, i) {
  return [...array.slice(0, i), ...array.slice(i + 1)];
}

Looking up a key

A lookup hashes the key and walks down from the root. At each branch it takes the next five bits of the hash: if that slot's bit isn't set, the key isn't in the map, and if it is, it goes down into the slot's entry. When it reaches a leaf, it compares the key.

function get(map, key) {
  const h = hash(key);
  let node = map;
  let shift = 0;

  while (true) {
    if (node.type === 'leaf')
      return node.key === key ? node.value : undefined;

    if (node.type === 'collision') {
      const leaf = node.leaves.find(l => l.key === key);
      return leaf ? leaf.value : undefined;
    }

    //  A branch: if the slot is empty the key isn't here, otherwise go down into it
    const bit = 1 << fragment(h, shift);
    if ((node.bitmap & bit) === 0)
      return undefined;

    node = node.entries[index(node.bitmap, bit)];
    shift += BITS;
  }
}

Each step is a few bit operations and an array read, and there's one step per level. With 32 slots per level, a map of n keys is about log₃₂(n) levels deep, so a lookup is O(log n), and never more than seven branches whatever the size. In practice it's very shallow: with a million keys, a lookup goes through four or five branches on average.

Adding a key

Adding a key walks down the same way. If the slot is empty, the new leaf goes straight in. If it's used, the new leaf goes into whatever is there, one level down.

Either way, the branch can't be changed, so it's copied, with the new entry or the new child in place. Its parent then has to be copied to point at the copy, and so on up to the root. This is called path copying. Only the nodes on the way down to the key are copied, and everything else is shared by the old and the new version:

//  Returns a new map with key set to value
function set(map, key, value) {
  return insert(map, Leaf(hash(key), key, value), 0);
}

//  Inserts an entry (a leaf, or a collision node being pushed down) into a node at this level
function insert(node, entry, shift) {
  if (node.type === 'branch') {
    const bit = 1 << fragment(entry.hash, shift);
    const i = index(node.bitmap, bit);

    //  An empty slot: set its bit and put the entry in the packed array
    if ((node.bitmap & bit) === 0)
      return Branch(node.bitmap | bit, arrayInsert(node.entries, i, entry));

    //  A used slot: insert into whatever is there, and copy this branch to point at the result
    return Branch(node.bitmap, arraySet(node.entries, i, insert(node.entries[i], entry, shift + BITS)));
  }

  //  A leaf or collision node with a different hash: push it down into a new branch, then insert
  //  the entry beside it. If their next five bits are the same too, this happens again a level down.
  if (node.hash !== entry.hash)
    return insert(insert(EMPTY, node, shift), entry, shift);

  //  The same key: replace the value
  if (node.type === 'leaf' && node.key === entry.key)
    return entry;

  //  A different key with exactly the same hash: more bits won't separate them, so keep both
  if (node.type === 'leaf')
    return Collision(node.hash, [node, entry]);

  const i = node.leaves.findIndex(l => l.key === entry.key);
  return Collision(node.hash, i >= 0 ? arraySet(node.leaves, i, entry) : [...node.leaves, entry]);
}

A change copies one branch per level, up to 32 entries each, so it's O(log n) like a lookup. It's also small in practice: in a map of 100,000 keys, setting one makes 5 new nodes, and the other 132,452 are shared with the old version.

Splitting a leaf

The interesting case is when the slot holds a leaf for a different key. That's the collision from the small example. The old leaf is pushed down into a new branch, using the next five bits of its hash, and then the new leaf is inserted into that branch beside it:

grape and lemon both start 16, 14, so they meet in slot 14 of the branch in slot 16. Their next five bits are 28 and 16, so the new branch separates them. If those were the same too, the insert would find grape again in the new branch and push it down another level, until their bits differ.

The leaf for grape isn't copied. The same leaf is just referenced from the new branch, which is why it's still shared with the old version.

Collisions

Different keys can have exactly the same 32-bit hash. It's rare, but it happens, and then no number of levels will separate them. When that happens, both leaves go into a collision node, which is a plain list:

A lookup that reaches a collision node compares the keys one by one, so it's slower, but with a good hash it almost never has more than two keys in it. If a later key has a different hash, the collision node is pushed down into a new branch just like a leaf.

Removing a key

Removing is adding in reverse. It walks down to the leaf, takes it out, and copies the branches on the way back up.

The one thing to look after is a branch that's left with a single leaf. That leaf doesn't need the branch any more, so it moves up into its parent's slot, and the branch goes away. That keeps the tree as shallow as it would be if the key had never been added:

//  Returns a new map without key, or the same map if key wasn't in it
function remove(map, key) {
  return removeFrom(map, key, hash(key), 0) || EMPTY;
}

//  Returns the node without the key: the same node if the key isn't there, or null if nothing is left
function removeFrom(node, key, h, shift) {
  if (node.type === 'leaf')
    return node.key === key ? null : node;

  if (node.type === 'collision') {
    const i = node.leaves.findIndex(l => l.key === key);
    if (i < 0)
      return node;

    //  Down to one leaf: it doesn't need a collision node any more
    if (node.leaves.length === 2)
      return node.leaves[1 - i];

    return Collision(node.hash, arrayRemove(node.leaves, i));
  }

  const bit = 1 << fragment(h, shift);
  if ((node.bitmap & bit) === 0)
    return node;

  const i = index(node.bitmap, bit);
  const child = node.entries[i];
  const newChild = removeFrom(child, key, h, shift + BITS);

  //  Not found further down: nothing changes, and nothing is copied
  if (newChild === child)
    return node;

  //  The slot is now empty: clear its bit and take its entry out
  if (newChild === null) {
    const bitmap = node.bitmap & ~bit;
    if (bitmap === 0)
      return null;

    const entries = arrayRemove(node.entries, i);

    //  A branch left with one leaf is replaced by the leaf, which moves up a level (but not at the root)
    if (shift > 0 && entries.length === 1 && entries[0].type !== 'branch')
      return entries[0];

    return Branch(bitmap, entries);
  }

  //  The child collapsed to a single leaf, and it's the only thing here: move it up again
  if (shift > 0 && node.entries.length === 1 && newChild.type !== 'branch')
    return newChild;

  return Branch(node.bitmap, arraySet(node.entries, i, newChild));
}

If the key isn't there, every level hands back the node it was given, so nothing is copied and remove returns the same map. That makes it cheap to tell whether anything changed: remove(map, key) === map. Like adding, removing is O(log n).

Going through every entry

To list the whole map, walk the tree depth first, taking each branch's entries in slot order:

//  Every [key, value] pair, depth first, in hash order
function* entries(node) {
  if (node.type === 'leaf') {
    yield [node.key, node.value];
  } else if (node.type === 'collision') {
    for (const leaf of node.leaves)
      yield [leaf.key, leaf.value];
  } else {
    for (const entry of node.entries)
      yield* entries(entry);
  }
}

That visits every node once, so it's O(n). The order comes from the hashes, so it looks random, and it isn't the order the keys were added in. The same set of keys always comes out in the same order, though, however it was built, apart from keys that share a collision node.

Using it

Each function takes a map and returns a new one, so you keep the result, and any older version you hold on to stays exactly as it was:

import { EMPTY, get, set, remove, entries } from './hamt.js';

let fruit = EMPTY;
fruit = set(fruit, 'apple', 3);
fruit = set(fruit, 'banana', 5);

const before = fruit;
fruit = set(fruit, 'apple', 4);

get(fruit, 'apple');               //  4
get(before, 'apple');              //  3, the old version hasn't changed
remove(fruit, 'kiwi') === fruit;   //  true, there was nothing to remove
[...entries(fruit)];               //  [['banana', 5], ['apple', 4]]

Complexity

The logarithm is base 32, so it grows very slowly. Here's how deep this code's trie really is:

A normal hash table finds a key in one or two steps on average, so it's faster for lookups, and if you only ever have one version of the data it's usually the better choice. It's also O(1) for adding, but only on average: every so often it doubles in size and moves everything, which is O(n) for that one insert. A HAMT never has a slow step like that, and the old versions it keeps for free are often what you wanted in the first place.