Hash Table
Last updated
A hash table stores items in an array of buckets. To place or find a key, it runs the key through a hash function and takes the result modulo the number of buckets - that gives the bucket index in O(1). Press play above to watch each key get hashed to a bucket and stored, then a lookup jump straight to the right bucket.
When two keys hash to the same bucket - a collision - this visualization uses separate chaining: each bucket holds a small list, and colliding keys are appended to it. As long as the table isn't too full (a low load factor) and the hash spreads keys well, chains stay short and insert, lookup, and delete are O(1) on average.
Time complexity
| Operation | Average | Worst case |
|---|---|---|
| Insert | O(1) | O(n) (all keys collide) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Space | O(n) | O(n) |
Key concepts
| Term | Meaning |
|---|---|
| Hash function | Maps a key to a bucket index |
| Collision | Two keys land in the same bucket |
| Separate chaining | Each bucket holds a list of colliding entries |
| Open addressing | Alternative: probe for the next free slot |
| Load factor | entries / buckets - drives resize |
Worked example
Inserting keys 20, 34, 9, 13 into a table with 7 buckets, using hash(k) = k % 7:
| Step | Structure | Action |
|---|---|---|
Insert 20 | bucket 6: [20] | 20 % 7 = 6, bucket 6 empty, store 20 |
Insert 34 | bucket 6: [20, 34] | 34 % 7 = 6, collision with 20, append 34 to the chain |
Insert 9 | bucket 2: [9] | 9 % 7 = 2, bucket 2 empty, store 9 |
Insert 13 | bucket 6: [20, 34, 13] | 13 % 7 = 6, collision, append 13 to bucket 6's chain |
Lookup 34 | bucket 6: [20, 34, 13] | 34 % 7 = 6, scan chain: 20 no, 34 match - found |
When to use a hash table
| Use it when | Avoid it when |
|---|---|
You need average O(1) insert, lookup, and delete by key | You need keys kept in sorted order - use a balanced BST |
| Keys have no useful ordering and you only test exact-match membership | You need range queries or nearest-key lookups |
| You can afford some extra memory for buckets and low load factor | Memory is extremely tight and every byte counts |
| A good hash function exists for your key type | Worst-case latency must be bounded - collisions make it O(n) |
Hash Table code
A clean, runnable Hash Table implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Hash Table code in Python
Python
1class HashTable:2 def __init__(self, size=8):3 self.size = size4 self.buckets = [[] for _ in range(size)]5
6 def _index(self, key):7 # Hash the key to a bucket; different keys can collide8 return sum(ord(ch) for ch in key) % self.size9
10 def set(self, key, value):11 bucket = self.buckets[self._index(key)]12 for i, (k, _) in enumerate(bucket):13 if k == key:14 bucket[i] = (key, value) # update existing key15 return16 bucket.append((key, value)) # chain on collision17
18 def get(self, key):19 for k, v in self.buckets[self._index(key)]:20 if k == key:21 return v22 raise KeyError(key)23
24 def delete(self, key):25 bucket = self.buckets[self._index(key)]26 for i, (k, _) in enumerate(bucket):27 if k == key:28 del bucket[i]29 return30 raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])Hash Table code in JavaScript
JavaScript
1class HashTable {2 constructor(size = 8) {3 this.size = size;4 this.buckets = Array.from({ length: size }, () => []);5 }6
7 // Fold character codes into a bucket index8 hash(key) {9 let h = 0;10 for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11 return h;12 }13
14 set(key, value) {15 const bucket = this.buckets[this.hash(key)];16 const pair = bucket.find(([k]) => k === key);17 if (pair) pair[1] = value;18 else bucket.push([key, value]); // Separate chaining on collision19 }20
21 get(key) {22 const bucket = this.buckets[this.hash(key)];23 const pair = bucket.find(([k]) => k === key);24 return pair ? pair[1] : undefined;25 }26
27 delete(key) {28 const bucket = this.buckets[this.hash(key)];29 const index = bucket.findIndex(([k]) => k === key);30 if (index === -1) return false;31 bucket.splice(index, 1);32 return true;33 }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));Hash Table code in Java
Java
1public class Main {2 static class Entry {3 String key; int value;4 Entry next; // chain for keys sharing a bucket5 Entry(String key, int value) { this.key = key; this.value = value; }6 }7
8 static final int CAPACITY = 8;9 static Entry[] buckets = new Entry[CAPACITY];10
11 static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13 static void put(String key, int value) {14 int i = index(key);15 for (Entry e = buckets[i]; e != null; e = e.next) {16 if (e.key.equals(key)) { e.value = value; return; }17 }18 Entry entry = new Entry(key, value);19 entry.next = buckets[i]; // prepend to the chain20 buckets[i] = entry;21 }22
23 static Integer get(String key) {24 for (Entry e = buckets[index(key)]; e != null; e = e.next) {25 if (e.key.equals(key)) return e.value;26 }27 return null;28 }29
30 static void remove(String key) {31 int i = index(key);32 Entry prev = null;33 for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34 if (e.key.equals(key)) {35 if (prev == null) buckets[i] = e.next;36 else prev.next = e.next;37 return;38 }39 }40 }41
42 public static void main(String[] args) {43 put("apple", 3); put("banana", 7); put("cherry", 5);44 System.out.println("apple -> " + get("apple"));45 put("apple", 10); // update in place46 System.out.println("apple -> " + get("apple"));47 remove("banana");48 System.out.println("banana -> " + get("banana"));49 }50}Hash Table code in C++
C++
1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6 static constexpr int CAPACITY = 8;7 // Separate chaining: each bucket holds (key, value) pairs8 std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10 size_t hash(const std::string& key) const {11 size_t h = 0;12 for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13 return h % CAPACITY;14 }15
16 void set(const std::string& key, int value) {17 auto& bucket = buckets[hash(key)];18 for (auto& entry : bucket) {19 if (entry.first == key) {20 entry.second = value; // update existing key21 return;22 }23 }24 bucket.push_back({key, value});25 }26
27 const int* get(const std::string& key) const {28 for (const auto& entry : buckets[hash(key)]) {29 if (entry.first == key) return &entry.second;30 }31 return nullptr;32 }33
34 void erase(const std::string& key) {35 auto& bucket = buckets[hash(key)];36 for (size_t i = 0; i < bucket.size(); ++i) {37 if (bucket[i].first == key) {38 bucket.erase(bucket.begin() + i);39 return;40 }41 }42 }43};44
45int main() {46 HashTable table;47 table.set("apple", 3);48 table.set("banana", 7);49 table.set("apple", 4); // overwrites the old value50 for (const std::string& key : {"apple", "banana", "grape"}) {51 const int* value = table.get(key);52 if (value != nullptr) std::cout << key << " = " << *value << "\n";53 else std::cout << key << " not found\n";54 }55 table.erase("banana");56 std::cout << "banana after erase: "57 << (table.get("banana") ? "found" : "not found") << "\n";58 return 0;59}Hash Table code in C
C
1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9 char key[16];10 int value;11 struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17 unsigned int h = 5381; // djb2, then modulo the bucket count18 for (; *key; key++) h = h * 33 + (unsigned char)*key;19 return h % CAPACITY;20}21
22void set(const char* key, int value) {23 unsigned int i = hash(key);24 for (Entry* e = buckets[i]; e != NULL; e = e->next) {25 if (strcmp(e->key, key) == 0) {26 e->value = value; // update existing key27 return;28 }29 }30 Entry* e = malloc(sizeof(Entry));31 strcpy(e->key, key);32 e->value = value;33 e->next = buckets[i];34 buckets[i] = e;35}36
37int* get(const char* key) {38 for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39 if (strcmp(e->key, key) == 0) return &e->value;40 }41 return NULL;42}43
44void removeKey(const char* key) {45 Entry** link = &buckets[hash(key)];46 while (*link != NULL) {47 if (strcmp((*link)->key, key) == 0) {48 Entry* old = *link;49 *link = old->next;50 free(old);51 return;52 }53 link = &(*link)->next;54 }55}56
57void printBuckets(void) {58 for (int i = 0; i < CAPACITY; i++) {59 printf("bucket %d:", i);60 for (Entry* e = buckets[i]; e != NULL; e = e->next) {61 printf(" (%s=%d)", e->key, e->value);62 }63 printf("\n");64 }65}66
67int main(void) {68 set("apple", 3);69 set("banana", 7);70 set("apple", 4); // overwrites the old value71 set("grape", 9);72 printBuckets();73 int* value = get("apple");74 printf("get(apple): %d\n", value ? *value : -1);75 removeKey("banana");76 printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77 return 0;78}Hash Table FAQ
What is a hash collision and how is it resolved?
A collision happens when two different keys hash to the same bucket. The two common fixes are separate chaining (each bucket holds a list, and colliding keys are appended - shown here) and open addressing (probe for the next empty slot in the array). Both keep lookups correct; they differ in memory layout and performance under high load.
What is the time complexity of a hash table?
Insert, lookup, and delete are
O(1) on average when the hash function distributes keys evenly and the load factor is kept low. In the worst case - every key colliding into one bucket - they degrade to O(n), which is why a good hash function and resizing matter.What is a load factor?
The load factor is the number of stored entries divided by the number of buckets. As it grows, chains get longer and operations slow down, so most hash tables resize (rehash into a bigger array) once it crosses a threshold like 0.75.
When should I use a hash table instead of a binary search tree?
Use a hash table when you only need exact-match lookups and want average
O(1) speed with no ordering requirement. Use a balanced binary search tree when you need keys in sorted order, range queries, or predecessor/successor lookups, which a hash table can't do efficiently. A BST gives guaranteed O(log n) operations, while a hash table trades that guarantee for faster average performance.What is the difference between separate chaining and open addressing?
Separate chaining stores colliding keys in a per-bucket list, so a bucket can hold many entries and the table never truly fills up. Open addressing keeps everything in the array itself and probes for the next free slot on a collision, which is cache-friendly but degrades sharply as the load factor approaches 1 and needs careful deletion handling. Chaining tolerates higher load factors; open addressing uses memory more compactly.
Why can't I rely on a hash table to keep my keys in insertion or sorted order?
A hash function deliberately scatters keys across buckets to avoid clustering, so iteration order reflects bucket layout, not insertion or sort order. If you need ordering, use an ordered map/tree or a structure like an insertion-ordered map (e.g. Python's
dict preserves insertion order, but that's a language guarantee, not an inherent hash-table property). Never assume iteration order matches how you inserted keys unless the language explicitly promises it.Related resources
More visualizations
