Code Quiz

Hash Map Resize Rehashing Bug

A separate-chaining hash map rehashes entries during resize, but lookups start failing for old keys afterward.

Codejavascript
class HashMap {
  constructor() {
    this.capacity = 8;
    this.size = 0;
    this.buckets = new Array(this.capacity);
  }

  _hash(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) h = (h * 31 + key.charCodeAt(i)) | 0;
    return Math.abs(h);
  }

  set(key, value) {
    if (this.size / this.capacity > 0.75) this._resize();
    const idx = this._hash(key) % this.capacity;
    if (!this.buckets[idx]) this.buckets[idx] = [];
    for (const pair of this.buckets[idx]) {
      if (pair[0] === key) { pair[1] = value; return; }
    }
    this.buckets[idx].push([key, value]);
    this.size++;
  }

  _resize() {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    const newBuckets = new Array(this.capacity);
    for (const bucket of oldBuckets) {
      if (!bucket) continue;
      for (const [key, value] of bucket) {
        const idx = this._hash(key) % oldBuckets.length;
        newBuckets[idx] = newBuckets[idx] || [];
        newBuckets[idx].push([key, value]);
      }
    }
    this.buckets = newBuckets;
  }

  get(key) {
    const idx = this._hash(key) % this.capacity;
    const bucket = this.buckets[idx];
    if (!bucket) return undefined;
    for (const [k, v] of bucket) if (k === key) return v;
    return undefined;
  }
}

After a resize, get() returns undefined for keys that were inserted earlier. What is the bug?