Beginner LevelData Structures & Algorithms
How does a Hash Table work internally?
ā Interview Prompt: Explain hash functions, hash collisions, separate chaining vs open addressing, and average vs worst-case time complexity of hash tables.
A Hash Table maps keys to values using a hash function that converts a key into a bucket index. It provides amortised $O(1)$ average-time lookup, insertion, and deletion.
Collision Resolution:
ā¢
Separate Chaining: Each bucket holds a linked list of entries that hash to the same index. Lookup: $O(1 + \alpha)$ where $\alpha$ = load factor.
ā¢
Open Addressing (Linear/Quadratic Probing): On collision, probe adjacent buckets until an empty slot is found.
Load Factor & Rehashing:
When the load factor ($\alpha = n / m$, entries/buckets) exceeds a threshold (typically $0.75$), the table rehashes ā doubles capacity and reinserts all keys ā an $O(N)$ operation amortised to $O(1)$.
Code Implementation Example
typescript
// Using JavaScript's built-in Map (backed by a hash table)
const freq = new Map<string, number>();
function frequencyCount(words: string[]): Map<string, number> {
for (const word of words) {
freq.set(word, (freq.get(word) ?? 0) + 1); // O(1) average
}
return freq;
}
console.log(frequencyCount(['apple', 'banana', 'apple']));
// Map { 'apple' => 2, 'banana' => 1 }š”O(N) word frequency count using a hash map.
šÆ Interview Key Takeaway
Hash Tables achieve O(1) average-case operations via hash functions. Manage load factor < 0.75 to keep collision chains short.
#DSA#Hash Table#Hashing#Collision#Beginner
Back to all Data Structures & Algorithms Questionsā