Implementing a Hash Map

The plain-language idea

A hash map is a lookup table: give it a key, get a value back, in roughly constant time no matter how many entries it holds. The trick is turning an arbitrary key — a string, usually — into an array index. You run the key through a hash function that produces a number, then use that number (mod the array's length) as the slot to store the entry in.

Two different keys can hash to the same slot. That's a collision, and it's not a bug — it's guaranteed to happen once you have more possible keys than slots (pigeonhole principle). The whole design of a hash map is: pick a hash function that spreads keys out evenly, then have a plan for when two keys land in the same bucket anyway. The most common plan is chaining: each bucket holds a small list, and a collision just appends to that list instead of overwriting.

See it in a real thing: a hash map with chaining

class HashMap {
  #buckets;
  #size = 0;

  constructor(capacity = 16) {
    this.#buckets = Array.from({ length: capacity }, () => []);
  }

  #hash(key) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) | 0; // keep it a 32-bit int
    }
    return Math.abs(hash) % this.#buckets.length;
  }

  set(key, value) {
    const bucket = this.#buckets[this.#hash(key)];
    const existing = bucket.find((entry) => entry[0] === key);
    if (existing) {
      existing[1] = value;
      return;
    }
    bucket.push([key, value]);
    this.#size++;
    if (this.#size / this.#buckets.length > 0.75) this.#resize();
  }

  get(key) {
    const bucket = this.#buckets[this.#hash(key)];
    return bucket.find((entry) => entry[0] === key)?.[1];
  }

  #resize() {
    const old = this.#buckets;
    this.#buckets = Array.from({ length: old.length * 2 }, () => []);
    this.#size = 0;
    for (const bucket of old) {
      for (const [k, v] of bucket) this.set(k, v);
    }
  }
}

#hash walks the string and folds each character code into a running total (the * 31 is the classic Java-string-hash trick — a prime multiplier that spreads output well for short strings). set and get both hash the key to find the right bucket, then do a plain linear scan of that bucket's array for a matching key — that scan is the "chain." As long as buckets stay small, that scan is effectively free, which is why average-case lookup is O(1). #resize is what keeps buckets small: once the map gets more than 75% full, it doubles the bucket count and re-hashes everything, because every bucket index depends on #buckets.length.

What people usually miss

Watch out

• Worst case isn't O(1). If every key collided into one bucket, get would degrade to O(n) — a linear scan through everything. Good distribution and resizing are what keep that from happening in practice; they don't make it impossible in theory.
• This is genuinely what's under the hood. JavaScript's Map and Object (for string keys) are implemented with exactly this idea in the engine — a hash table with some collision strategy — just written in C++ with far more tuning than a teaching example needs.
• Order isn't guaranteed by the algorithm. Map in JS actually does preserve insertion order as a language guarantee, but that's a spec promise layered on top, not something hashing gives you for free — a naive hash map like the one above has no defined iteration order at all.

The genealogy: built on the same idea as object property lookup

Reaching into an object with obj[key] or a Map with map.get(key) is this same hash-then-chain lookup happening beneath the language surface — you're just usually not the one writing the hash function. Understanding the mechanism is what makes "why is this O(1)" stop being something you take on faith.