Collision Handling

When Keys Collide

Here's the thing about hash tables — sometimes two different keys produce the same hash. It's like two people having the same apartment number. That's called a collision, and if you don't handle it, you'll overwrite data or lose it completely.

Collisions are inevitable unless your hash table is huge and your keys are few. The question isn't whether they'll happen, but how you deal with them when they do.

There are two main strategies: chaining and open addressing. Both work, but they have different trade-offs you should understand.

Chaining

Chaining is the simpler approach. Instead of storing a single value at each index, you store a linked list (or any collection). When a collision happens, both values just live in the same bucket as separate nodes in the list.

When you look something up, you hash the key, go to that index, then walk through the list until you find a match. It's like having a building where multiple people share the same address — the mail carrier just checks each name on the door.

The downside? If lots of keys collide, those chains get long, and your lookups slow down. But in practice, a good hash function keeps chains short.

function createChainTable(size) {
  const table = new Array(size).fill(null);

  function hash(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h += key.charCodeAt(i);
    }
    return h % size;
  }

  function set(key, value) {
    const idx = hash(key);
    if (!table[idx]) {
      table[idx] = [];
    }
    const pair = table[idx].find(p => p[0] === key);
    if (pair) {
      pair[1] = value;
    } else {
      table[idx].push([key, value]);
    }
  }

  function get(key) {
    const idx = hash(key);
    if (!table[idx]) return undefined;
    const pair = table[idx].find(p => p[0] === key);
    return pair ? pair[1] : undefined;
  }

  return { set, get };
}

const map = createChainTable(10);
map.set("apple", 5);
map.set("banana", 3);
console.log(map.get("apple"));

Open Addressing

Open addressing takes a different approach — everything lives in the array itself. When a collision happens, you probe for the next open slot. It's like showing up to a restaurant and being told "your table is taken, try the next one."

Linear probing checks the next slot, then the one after that, and so on. Quadratic probing jumps by 1², then 2², then 3² slots. Double hashing uses a second hash function to determine the step size.

The catch with open addressing is the load factor — once your table gets more than 70% full, collisions multiply and performance tanks. That's when you rehash: create a bigger table and redistribute everything.

function createLinearTable(size) {
  const table = new Array(size).fill(null);

  function hash(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h += key.charCodeAt(i);
    }
    return h % size;
  }

  function set(key, value) {
    let idx = hash(key);
    while (table[idx] && table[idx][0] !== key) {
      idx = (idx + 1) % size;
    }
    table[idx] = [key, value];
  }

  function get(key) {
    let idx = hash(key);
    while (table[idx]) {
      if (table[idx][0] === key) return table[idx][1];
      idx = (idx + 1) % size;
    }
    return undefined;
  }

  return { set, get };
}

const cache = createLinearTable(10);
cache.set("x", 42);
cache.set("y", 99);
console.log(cache.get("x"));