· By John Kavanagh

Design a Hash Map in TypeScript: Make Collisions Boring

Rows of numbered metal mailboxes mounted on a wall.
Image by Crystal Robinson, licensed from Unsplash.

A hash map feels straightforward until two keys want the same place. At that point, either the implementation remembers that a hash is only a routing decision, or somebody's value quietly disappears. I prefer data structures that keep the quiet surprises to a minimum.

LeetCode's Design HashMap problem asks us to build the familiar insert, lookup, and remove operations without using a built‑in hash table. The keys and values are non‑negative integers, and a missing lookup returns ‑1. Those restrictions make a compact implementation possible, but they also give us a useful opportunity to distinguish a general technique from a solution tailored to a small key universe.

I'll use separate chaining: an array of buckets, with a small array of key‑value pairs inside each bucket. It makes collisions visible and gives us something specific to test. It isn't a replacement for JavaScript's Map in application code.


A Bucket is an Address, Not an Identity

Suppose there are 1009 buckets. The expression key % 1009 picks one of them for every allowed key. Keys 7 and 1016 both select bucket 7, even though they are different keys. The bucket must therefore store the original key alongside its value.

A lookup has two stages. First, calculate the bucket number. Then search that bucket for an exact key match. Hashing narrows the search; equality finishes it. Confusing those jobs is the fundamental collision bug, and choosing a larger bucket count merely makes it harder to notice.

Each bucket contains at most one pair for a particular key. Calling put twice with key 7 changes the existing pair. It must not append a second copy, because then a later lookup or removal would depend on which duplicate happened to be encountered first.

There is another small trap in the initial allocation. Filling an outer array with one empty array would give every position the same bucket object. Array.from calls the factory separately, so each bucket is independent. A neat‑looking initialiser is not a bargain if all the drawers open onto the same cupboard.


The Complete Implementation

The class name and public methods match the exercise. Arrow methods keep the implementation style consistent, though conventional class methods would work equally well here. Each instance owns its own bucket array.

class MyHashMap {
  private readonly buckets: Array<Array<[number, number]>> =
    Array.from({ length: 1009 }, () => []);

  put = (key: number, value: number): void => {
    const bucket = this.buckets[key % this.buckets.length];
    const existing = bucket.find(pair => pair[0] === key);
    if (existing) existing[1] = value;
    else bucket.push([key, value]);
  };

  get = (key: number): number => {
    const bucket = this.buckets[key % this.buckets.length];
    return bucket.find(pair => pair[0] === key)?.[1] ?? -1;
  };

  remove = (key: number): void => {
    const bucket = this.buckets[key % this.buckets.length];
    const index = bucket.findIndex(pair => pair[0] === key);
    if (index !== -1) bucket.splice(index, 1);
  };
}

The optional lookup returns undefined when the key is absent, and nullish coalescing turns that into ‑1. I wouldn't use a truthiness check here: zero is a legitimate stored value. Likewise, findIndex returns zero for the first pair, so removal checks specifically for ‑1.

Removing an absent key does nothing. Removing a present key removes just that pair. Splicing shifts the remaining pairs within its bucket, which contributes to the operation's bucket‑length cost. There is no requirement to preserve insertion order, but the simple implementation does preserve the order of surviving pairs as a side effect.


Following a Deliberate Collision

Start by storing key 7 with value 20, then key 1016 with value 30. Both pairs live in bucket 7. Looking up 1016 skips the first pair and returns 30 from the second. Looking up 2025 searches the same bucket and returns ‑1 because neither stored key matches.

Now update key 7 to value zero. The bucket still has two pairs. The first becomes [7, 0], and the second remains [1016, 30]. A lookup for 7 returns zero rather than treating the value as missing.

Remove key 7 next. Key 1016 remains retrievable, even though it has moved to the first position in the bucket. Finally, remove 7 again: nothing changes. That short sequence exercises collision handling, replacement, zero values, shifting, and absent removal. A test containing only unrelated keys wouldn't cover most of the interesting behaviour.

The invariant after every operation is simple enough to check by hand: each stored key is in the bucket selected by its remainder, and appears there exactly once. The implementation preserves it because replacement doesn't change the key, insertion uses the same routing expression, and removal cannot move a pair into another bucket.


Be Precise About the Complexity

Let n be the number of stored keys and b the number of buckets. Initialisation takes O(b) time and space. An operation takes O(1 + k), where k is the length of the selected bucket. Storage takes O(b + n), because each stored pair appears once.

With evenly distributed keys, the expected bucket length is roughly n divided by b. That can make operations pleasantly short, but this implementation does not resize, randomise its hash, or promise a constant load factor as n grows. Worst‑case operations remain O(n) when keys collect in one bucket.

The allowed finite key range limits how many distinct keys can share one remainder in this particular exercise. That restriction doesn't make the design a general worst‑case constant‑time hash map. I would rather explain the assumption than decorate the code with an optimistic complexity label.

A resizing version would allocate more buckets once the load factor passes a chosen threshold and reinsert every pair using the new bucket count. Rehashing is essential: changing the divisor changes where keys belong. The occasional resize costs linear time, so an average‑cost argument needs to account for those expensive operations too.


Why Not Index Directly by Key?

The problem bounds keys at one million. A direct‑address array with one slot per possible key is therefore a valid alternative, using ‑1 for an empty slot. It gives constant‑time operations and avoids collisions entirely, at the cost of allocating storage for the full key universe even when only a handful of keys are present.

That trade‑off can be sensible. A typed integer array provides predictable numeric storage, but still needs initialising to the missing‑value sentinel. Calling this structure a hash table would obscure how it works: there is no compression of the key space and no collision policy to explain.

For ordinary application code, I'd choose the built‑in Map unless there were a measured reason otherwise. The JavaScript specification for Map requires average access times that are sublinear in collection size; it does not prescribe this bucket implementation or guarantee worst‑case constant time. The exercise's restriction is educational, not advice to maintain a home‑grown collection in every project.


Tests That Inspect Behaviour, Not Private Arrays

I compare operation sequences against a reference Map, translating a missing reference lookup to ‑1. Using Map in the test is fine: the restriction applies to the submitted implementation. Random sequences are useful, but explicit colliding keys ensure the difficult path actually runs.

I also create two instances and insert into only one, test keys zero and one million, overwrite the same key repeatedly, and remove the first, middle, and last pairs of a crowded bucket. These checks protect the public behaviour without tying the test to a particular private representation.

My circular queue walkthrough makes a similar distinction between logical contents and storage positions. My Kth Largest in a Stream article uses a different structure to maintain a smaller useful summary. Here the lesson is narrower: routing can be approximate, identity cannot. Once those two responsibilities are separate, a collision becomes ordinary bookkeeping.


Want to find out more?

If you need senior hands‑on support with a complex React or Next.js platform, migration, performance issue, or technical SEO problem, send me the context and I'll tell you where I can help.