Hash Table
In one line
A hash table stores key-value pairs and uses a hash function to compute an index, enabling fast O(1) average lookup.
In simple words
A hash table (hash map) stores key-value pairs and uses a hash function to convert each key into a numeric index in an internal array. This lets you store, find, and delete values by key in O(1) average time — much faster than searching an array element by element.
The hash function takes a key (like a string "name") and returns an integer index. Two different keys might hash to the same index — a collision. Hash tables handle collisions with chaining (store a list of entries at each index) or open addressing (probe for the next free slot). A good hash function distributes keys evenly to minimize collisions.
Hash tables are the backbone of JavaScript objects and Maps, Python dicts, Java HashMaps, and database indexes. They are the go-to structure whenever you need fast lookup by key, deduplication, or counting frequencies.
Example
// Simple hash table with chaining
class HashTable {
#buckets = Array.from({ length: 5 }, () => []);
#hash(key) {
let h = 0;
for (const ch of key) h += ch.charCodeAt(0);
return h % this.#buckets.length;
}
set(key, val) {
const i = this.#hash(key);
const bucket = this.#buckets[i];
const entry = bucket.find(e => e[0] === key);
if (entry) entry[1] = val; else bucket.push([key, val]);
}
get(key) {
const bucket = this.#buckets[this.#hash(key)];
return bucket.find(e => e[0] === key)?.[1];
}
}
const ht = new HashTable();
ht.set("name", "Ada"); ht.set("age", 36);
console.log(ht.get("name")); // "Ada"The hash function sums char codes and mods by bucket count. Collisions are handled by chaining — each bucket holds a list of key-value pairs.
Related terms
Related Resources
Related Lessons
- Data Structures
Learn hash tables and maps.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.