← Index

Hash-Based Structures

HashMap

Key → value storage with ~O(1) average lookup.

What it is

A hash map runs each key through a hash function that turns it into an array index, so get/set can jump almost straight to the right slot instead of scanning everything. Collisions (two keys hashing to the same slot) are handled by chaining a small list at that slot. In JS you reach for Map or a plain object for this — the code here shows what's actually happening underneath.

Real-world examples

• A coat check counter: you hand over your coat (value), get a numbered ticket (hashed key), and retrieval later is a direct look-up by that number, not a search through every coat.
• A library's call-number system — the number tells you almost exactly which shelf to walk to.

Where you've probably used this already

• Counting word/tag frequency, deduplicating by ID, memoization caches — Map/{} is the default tool.
• Two Sum and its many variants ("find pair/triplet that...") — trading O(n²) nested loops for O(n) with a value→index map.
• Debugging why an object used as a cache key silently 'lost' entries — objects hash by reference, not by deep value, a common gotcha.

Complexity

Code

// HashMap — key/value storage with ~O(1) average get/set.
// A hash function turns the key into an array index, so lookup skips
// straight to (roughly) the right bucket instead of scanning everything.
// In real JS you'd just use Map or {} — this is what's happening underneath.

class HashMap {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  // Turn a string key into a "random-ish" index within our array size
  _hash(key) {
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      total = (total * PRIME + key.charCodeAt(i)) % this.keyMap.length;
    }
    return total;
  }

  set(key, value) {
    const index = this._hash(key);
    if (!this.keyMap[index]) this.keyMap[index] = [];
    // handle collisions: two keys hashing to the same index live in the
    // same bucket as a small list ("separate chaining")
    const bucket = this.keyMap[index];
    const existing = bucket.find((pair) => pair[0] === key);
    if (existing) existing[1] = value;
    else bucket.push([key, value]);
  }

  get(key) {
    const index = this._hash(key);
    const bucket = this.keyMap[index];
    if (!bucket) return undefined;
    const pair = bucket.find((pair) => pair[0] === key);
    return pair ? pair[1] : undefined;
  }

  has(key) {
    return this.get(key) !== undefined;
  }
}

// --- Example Usage ---
const map = new HashMap();
map.set("name", "Marky");
map.set("role", "developer");
console.log("get('name'):", map.get("name")); // "Marky"
console.log("has('missing'):", map.has("missing")); // false

// --- The pattern you actually reach for daily: Map / plain object ---
const counts = new Map();
const words = ["a", "b", "a", "c", "b", "a"];
for (const w of words) {
  counts.set(w, (counts.get(w) || 0) + 1);
}
console.log("word counts:", counts); // Map { a:3, b:2, c:1 }

// Classic interview use — Two Sum in O(n) instead of O(n^2) nested loop
function twoSum(nums, target) {
  const seen = new Map(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
  return [];
}
console.log("twoSum([2,7,11,15], 9):", twoSum([2, 7, 11, 15], 9)); // [0,1]