Welcome to the world of Hash Tables, where finding information feels less like a treasure hunt and more like a direct teleportation! If you've ever wondered how websites can instantly pull up search results or how your email client manages to find that specific message in milliseconds, hash tables are a significant part of the magic.
At its core, a hash table is a data structure designed for extremely fast lookups, insertions, and deletions. Unlike arrays or linked lists where you might have to traverse through elements, hash tables aim for constant time (O(1)) complexity for these operations. This is achieved through a clever mechanism called hashing.
A hash function is the heart of a hash table. It takes an input (often called a 'key') and converts it into an index, which is a specific location within an underlying array (often called 'buckets' or 'slots'). Think of it like a librarian who can instantly tell you which shelf a book belongs on based on its title. The better the hash function, the more evenly distributed your data will be, leading to better performance.
graph LR;
A[Key] --> B(Hash Function);
B --> C[Index];
C --> D[Array Bucket];
The simplest way to visualize this is with a key-value pair. When you want to store something, you provide a key and a value. The hash function transforms the key into an index, and the value is stored at that index in the underlying array. When you want to retrieve the value, you provide the same key, the hash function calculates the same index, and you can directly access the value.
class HashTable {
constructor(size = 10) {
this.buckets = new Array(size);
}
hash(key) {
let hashValue = 0;
for (let i = 0; i < key.length; i++) {
hashValue += key.charCodeAt(i);
}
return hashValue % this.buckets.length;
}
set(key, value) {
const index = this.hash(key);
if (!this.buckets[index]) {
this.buckets[index] = [];
}
this.buckets[index].push({ key, value });
}
get(key) {
const index = this.hash(key);
const bucket = this.buckets[index];
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i].key === key) {
return bucket[i].value;
}
}
}
return undefined; // Key not found
}
}