16 items
12345678910111213141516
Hash Map Resize Rehashing Bug
Code QuizAmortized Cost of Hash Map Insertion
QuizLoad Factor & Amortized Hash Cost
Slides / VideoLoad Factor & Amortized Hash Map Cost
FlashcardFind First Duplicate With a Set
Code QuizChoosing Hash Maps vs Sets
QuizHash Map Chaining Update Bug
Code QuizOpen Addressing & Load Factor
QuizHash Maps, Sets & Collision Handling
Slides / VideoCollision Handling in Hash Maps
FlashcardSet vs Object Membership Check
Code QuizArrays vs Hash Maps vs Sets
QuizDuplicate Detection With a Set
Code QuizAccess Time Complexity Basics
QuizArrays, Hash Maps & Sets: Access Patterns
Slides / VideoArrays vs Hash Maps vs Sets
FlashcardCode 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?