</>
Loading
Loading
O(1) Lookup Magic
Hash tables (also called hash maps or dictionaries) provide average O(1) time complexity for insert, delete, and lookup operations. They are one of the most important data structures in practical programming.
A hash table uses a hash function to compute an index into an array of buckets, from which the desired value can be found. The key insight is that we can transform a key into an array index in constant time.
// JavaScript Map (hash table)
const map = new Map();
// Insert - O(1) average
map.set('key', 'value');
// Lookup - O(1) average
const val = map.get('key');
// Check existence - O(1) average
map.has('key'); // true
// Delete - O(1) average
map.delete('key');
// JavaScript Set (hash set)
const set = new Set();
set.add(1);
set.has(1); // true
set.delete(1);Use a hash table when you need fast lookups by key, counting frequencies, or checking for duplicates. If you need ordered data, consider a TreeMap instead.
One of the most common uses of hash tables is counting the frequency of elements. This pattern appears in anagram problems, finding duplicates, and majority element problems.
// Count frequency of each element
function countFrequency(arr) {
const freq = new Map();
for (const item of arr) {
freq.set(item, (freq.get(item) || 0) + 1);
}
return freq;
}
// Find most frequent element
function findMostFrequent(arr) {
const freq = countFrequency(arr);
let maxCount = 0;
let maxElement = null;
for (const [element, count] of freq) {
if (count > maxCount) {
maxCount = count;
maxElement = element;
}
}
return maxElement;
}Converts keys into array indices. A good hash function distributes keys uniformly.
When two keys hash to the same index. Common solutions: chaining (linked lists) or open addressing.
Ratio of entries to buckets. When it exceeds a threshold, the table resizes (rehashing).
Use a hash map to find complement in O(1)
const seen = new Map();
for (let i = 0; i < arr.length; i++) {
const complement = target - arr[i];
if (seen.has(complement)) {
return [seen.get(complement), i];
}
seen.set(arr[i], i);
}Count occurrences of elements
Move on to Stacks & Queues to learn LIFO and FIFO patterns, which often combine well with hash tables.