Why I wrote my own hash map instead of using a library

When I started thinking about how first would store variables, the obvious move was to pull in a battle-tested hash map. There are good options: uthash, khash, the GLib hash table. They're all well-tested and fast. So why did I end up writing my own 120-line implementation instead?

The dependency question

first has zero runtime dependencies. That's not an accident — it's a constraint I set early to keep the build simple and the code portable. A single cmake --preset debug should produce a working binary without fetching anything from the internet.

Adding a hash map library would break that. Even with vcpkg configured in the project, adding a dependency means another thing that can fail, another version to pin, another surface area for the build to break on a different system.

But more importantly: this is a project for learning. Using a library for the variable store means there's a black box at the heart of the runtime. That felt wrong.

Open addressing with linear probing

JMap is an open-addressing hash map. All key-value pairs live in a single flat array, not in a linked list of buckets. When two keys hash to the same slot, the second one walks forward through the array until it finds an empty slot — that's linear probing.

static size_t probe(JMap *map, const char *key) {
  size_t idx = hash(key) % map->capacity;
  while (map->slots[idx].key != NULL
      && strcmp(map->slots[idx].key, key) != 0) {
    idx = (idx + 1) % map->capacity;
  }
  return idx;
}

For a language's variable store, this is a good fit. Programs rarely have thousands of variables, so the flat array stays in CPU cache. The load factor stays low. Probing is fast.

Rehashing

The map doubles its capacity when load exceeds 0.7, then rehashes all existing entries into the new array. Getting rehash right — specifically not freeing keys mid-probe — took a few careful passes. The new array is allocated first, all live entries are re-inserted by calling the probe function against the new capacity, then the old array is freed.

The deletion problem

The hardest part wasn't probing — it was deletion. Removing a key from an open-addressing map leaves a hole that breaks the probe chain for keys that collided with the deleted slot. The standard fix is tombstones: mark deleted slots with a sentinel value so probing continues through them on future lookups.

first doesn't need variable deletion yet (there's no unlet keyword), so I deferred this entirely and added a comment in the source. When scope destruction lands, tombstones will be necessary.

What I'd do differently

If I were building a production interpreter, I'd use khash without hesitation — it's a header-only, macro-generated, genuinely excellent hash map with none of the overhead of a full library. For first, writing JMap was one of the most instructive 120 lines in the codebase. The rehash bug alone taught me more about memory layout than any amount of using someone else's implementation would have.