51. Hash tables

Finding things by name

The VM is about to look things up by name everywhere: global variables (chapter 53), an instance’s fields, a class’s methods. The tree-walker used a JavaScript Map. The companion VM has its own table, about a hundred lines in vm/table.ts, so you can see what a Map does inside, and so the garbage collector can walk it and delete entries itself (chapter 58).

Chapter 8’s picture was a wall of pigeonholes. To build it you need two pieces: a way to turn a key into a number, and a rule for when two keys want the same pigeonhole.

A hash function

The companion VM uses FNV-1a, a hash named after Glenn Fowler, Landon Curt Noll and Phong Vo, and designed to be fast while keeping collisions rare^[2]. It starts from a fixed 32-bit number, the offset basis. Then, for each character, it XORs the character code into the hash and multiplies by a fixed prime, keeping only the low 32 bits:

function hashString(s: string) {
  let h = 2166136261;
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 16777619);
  }
  return h >>> 0;
}

2166136261 is 0x811c9dc5 and 16777619 is 0x01000193, the values in the reference implementation^[2]. Two JavaScript details matter:

• Math.imul, not *. A plain h * 16777619 is a double multiplication, and the product can be far beyond 2⁵³, so its low bits are lost. Math.imul does a C-style 32-bit multiply, wrapping around exactly^[3].
• >>> 0 at the end. XOR and Math.imul give signed 32-bit results, which may be negative. Shifting by zero with >>> reads the same 32 bits as an unsigned number^[4].

The reference code hashes bytes. This one hashes UTF-16 code units (chapter 10), which are the same thing for plain ASCII names.

function fnv(s) {
  let h = 2166136261;
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 16777619);
  }
  return h >>> 0;
}

const ks = ['x', 'y', 'vx', 'vy',
  'mass', 'health'];
for (const k of ks) {
  console.log(k, fnv(k), fnv(k) & 7);
}
// one letter apart, far apart:
console.log(fnv('health'));
console.log(fnv('healti'));

From a hash to a slot

A table with 8 slots needs a slot number from 0 to 7. Because the capacity is always a power of two, keeping the low bits does it in one instruction (chapter 16): hash & 7 keeps the last three bits^[5]. hash("x") & 7 is 7.

With more possible names than slots, two keys will sooner or later want the same slot. That’s a collision, and no hash function can prevent it.

Open addressing

One way to handle collisions hangs a little list off every slot. The companion table doesn’t. Every entry lives in the array itself, and a key whose slot is taken simply moves along. Here is the whole idea on a real 8-slot table, using the particle fields as keys:

Lookups and inserts share one function. It returns the slot where the key is, or where it should go:

static find(keys, values, key) {
  const mask = keys.length - 1;
  let index = key.hash & mask;
  let tombstone = -1;
  for (;;) {
    const k = keys[index];
    if (k === null) {
      if (values[index] === null) {
        return tombstone !== -1
          ? tombstone : index;
      }
      if (tombstone === -1) {
        tombstone = index;
      }
    } else if (k === key) {
      return index;
    }
    index = (index + 1) & mask;
  }
}

Notice k === key: keys are compared by identity, not by their characters. That is only correct because equal strings are always the same object in this VM, which is chapter 52’s job. Deleting sets the key to null and the value to true, the tombstone.

How full is too full?

Probing is quick when most slots are empty and slow when they’re not: in a nearly full table, a key might walk past half the array. And if no slot were ever truly empty, find’s loop would never end. So the table watches its load, and grows before it gets crowded:

set(key: ObjString, value: Value) {
  if (this.count + 1 >
      this.keys.length * MAX_LOAD) {
    this.grow(this.keys.length < 8
      ? 8 : this.keys.length * 2);
  }
  const i = Table.find(
    this.keys, this.values, key);
  const isNew = this.keys[i] === null;
  if (isNew && this.values[i] === null) {
    this.count++;
  }
  this.keys[i] = key;
  this.values[i] = value;
  return isNew;
}

MAX_LOAD is 0.75, and count includes tombstones, because a tombstone still takes up a slot as far as probing is concerned. Reusing a tombstone doesn’t add to count; only filling a truly empty slot does.

grow makes new, bigger arrays and inserts every live key again. It can’t just copy: the mask changes from 7 to 15, so each key’s starting slot changes too. Tombstones aren’t copied, so growing also cleans up.

Two arrays, not one

The first table.ts stored an array of { key, value } entry objects. A later commit switched to two parallel arrays, keys[] and values[]: chapter 23’s struct of arrays, inside the VM. With entry objects, every slot is a separate heap object, and probing chases a pointer to each one before it can read the key. The comment in table.ts says object-heavy programs got measurably faster; the commit records no separate number for this change.

Your turn

const TOMB = true;
function hash(s) {
  let h = 2166136261;
  for (let i = 0; i < s.length; i++) {
    h ^= s.charCodeAt(i);
    h = Math.imul(h, 16777619);
  }
  return h >>> 0;
}

class Table {
  constructor() {
    this.keys = new Array(8).fill(null);
    this.vals = new Array(8).fill(null);
  }
  find(key) {
    const mask = this.keys.length - 1;
    return hash(key) & mask;
  }
  get(key) {
    const i = this.find(key);
    if (this.keys[i] === null) {
      return undefined;
    }
    return this.vals[i];
  }
  set(key, v) {
    const i = this.find(key);
    this.keys[i] = key;
    this.vals[i] = v;
  }
  delete(key) {
    const i = this.find(key);
    if (this.keys[i] === null) return;
    this.keys[i] = null;
    this.vals[i] = null;
  }
}

function fnv1a(s) {
  let h = 2166136261;
  return h;
}

What you learned

• A hash function turns a key into a number. FNV-1a XORs in each character and multiplies by a prime. In JavaScript, use Math.imul and finish with >>> 0.
• A hash table uses hash & (capacity - 1) as the starting slot. Two keys wanting one slot is a collision.
• Open addressing keeps every entry in the array. Linear probing steps to the next slot; lookups stop at an empty slot; deletes leave tombstones.
• The load factor limit, 0.75, makes the table double and reinsert everything before probes get long.
• The companion table is a struct of arrays: keys[] and values[].

Next: the trick that lets find compare keys with a single ===.