Loading...
Master hash table concepts, hash functions, collision resolution strategies, and performance characteristics. Learn how to design efficient hash-based data structures.
A hash table (or hash map) is a data structure that implements an associative array abstract data type, mapping keys to values using a hash function.
Same key always produces same hash value
Spreads keys evenly across hash table
Quick to calculate to maintain O(1) performance
Minimizes keys mapping to same index
Simple and fast. Choose m as prime number.
Works well with any table size. A ≈ 0.618 (golden ratio).
Randomly choose a, b. Provides theoretical guarantees.
Strong hash functions for security applications.
Collisions happen when different keys hash to the same index. This is inevitable when the key space is larger than the hash table size.
If you have n keys and m buckets where n > m, at least one bucket must contain more than one key.
With just √m random keys in a table of size m, there's a 50% chance of collision. For m=365 (days), only 23 people needed for 50% birthday collision chance.
Store multiple elements at the same index using linked lists or arrays.
Find another slot within the table when collision occurs using probing sequences.
Check next slot sequentially
Use quadratic function for probing
Use second hash function
n = number of elements stored
m = table size (number of buckets)
Although resizing takes O(n) time, it happens infrequently. Amortized cost per operation remains O(1).
| Operation | Average | Worst |
|---|---|---|
| Search | O(1) | O(n) |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
Good hash function with low load factor gives true O(1) performance.
All keys hash to same bucket, degrading to O(n) linear search.
Open addressing generally provides better cache locality than chaining due to data being stored contiguously in the main table.
class HashTable {
constructor(size = 10) {
this.size = size;
this.table = new Array(size).fill(null).map(() => []);
this.count = 0;
}
// Simple hash function
hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size;
}
// Insert key-value pair
set(key, value) {
const index = this.hash(key);
const bucket = this.table[index];
// Check if key already exists
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket[i][1] = value; // Update existing
return;
}
}
// Add new key-value pair
bucket.push([key, value]);
this.count++;
// Resize if load factor > 0.75
if (this.count / this.size > 0.75) {
this.resize();
}
}
// Get value by key
get(key) {
const index = this.hash(key);
const bucket = this.table[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
return bucket[i][1];
}
}
return undefined;
}
// Delete key-value pair
delete(key) {
const index = this.hash(key);
const bucket = this.table[index];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1);
this.count--;
return true;
}
}
return false;
}
// Resize and rehash
resize() {
const oldTable = this.table;
this.size *= 2;
this.table = new Array(this.size).fill(null).map(() => []);
this.count = 0;
// Rehash all elements
for (let bucket of oldTable) {
for (let [key, value] of bucket) {
this.set(key, value);
}
}
}
// Get load factor
loadFactor() {
return this.count / this.size;
}
}Hash indexes provide fast record lookup by primary key.
Quick access to frequently used data and memoization.
Built-in data structures in programming languages.
Security applications and data integrity verification.
Consistent hashing for load balancing and sharding.
Symbol tables and optimization techniques.