Hash Tables: Hash Functions, Buckets and Collisions
PlayHash a key, jump straight to its bucket, and watch collisions chain
This concept builds on Binary Numbers — How Computers Count, Modular Arithmetic, Linked Lists — Pointers & Connections. Consider exploring them first for the best experience.
The Hash Function: Key In, Bucket Out
A hash table stores keys in an array of buckets and uses a hash function to turn each key into a bucket index, so a lookup jumps straight to one bucket instead of searching them all. The row of numbered boxes is the bucket array. The hash function turns any key into one big number, and dividing that number by the bucket count leaves a remainder — the bucket index. Watch the red arrow carry each sample key to its bucket. Then type your own word into the key box and press 'Insert'.
Insert: Jump Straight to the Bucket
Your key appears in the bucket the arrow points at, and the line under the key shows its full hash and the remainder. No other bucket was searched, which is why an insert takes about the same time whether the table holds 3 keys or 3,000. The 'Entries' card counts every stored key. Insert a few more words and watch where each lands.
Worked Example: cat in 8 Buckets
Press 'Try cat'. The table empties to 8 buckets and inserts cat. The hash starts at 5381 and, for each letter, multiplies by 33 and adds the letter's code: c = 99 gives 177,672, a = 97 gives 5,863,273 and t = 116 gives 193,488,125. Dividing 193,488,125 by 8 leaves remainder 5, so cat lands in bucket 5, exactly where the arrow points.
Lookup: Hash Again, Check One Bucket
Type cat again and press 'Search'. The table recomputes the same hash, jumps straight to bucket 5 and compares keys only inside that bucket. A solid outline means found; a dashed red outline means the key is missing. Press 'Delete' and the same lookup runs first, then the key is unlinked from its bucket.
Collision: Two Keys, One Bucket
With only 8 buckets, different keys must sometimes leave the same remainder. Insert act after cat: it also lands in bucket 5, the bucket turns orange and act hangs below cat in a chain. That is chaining — each bucket keeps a short list, and a lookup scans only that list. The 'Longest Chain' card shows the most crowded bucket.
Load Factor and Resizing
The 'Load Factor' card is entries divided by buckets: 6 keys in 8 buckets give 0.75. As it climbs, chains grow and lookups slow. Drag the 'Buckets' slider to 16 and every key is rehashed: cat moves from bucket 5 to bucket 13, the load factor halves and most chains split. Real hash tables resize automatically, often doubling once the load factor passes a threshold such as 0.75.
How It Works — Step by Step
-
1
The Hash Function: Key In, Bucket Out
A hash table stores keys in an array of buckets and uses a hash function to turn each key into a bucket index, so a lookup jumps straight to one bucket instead of searching them all. The row of numbered boxes is the bucket array. The hash function turns any key into one big number, and dividing that number by the bucket count leaves a remainder — the bucket index. Watch the red arrow carry each sample key to its bucket. Then type your own word into the key box and press 'Insert'.
-
2
Insert: Jump Straight to the Bucket
Your key appears in the bucket the arrow points at, and the line under the key shows its full hash and the remainder. No other bucket was searched, which is why an insert takes about the same time whether the table holds 3 keys or 3,000. The 'Entries' card counts every stored key. Insert a few more words and watch where each lands.
-
3
Worked Example: cat in 8 Buckets
Press 'Try cat'. The table empties to 8 buckets and inserts cat. The hash starts at 5381 and, for each letter, multiplies by 33 and adds the letter's code: c = 99 gives 177,672, a = 97 gives 5,863,273 and t = 116 gives 193,488,125. Dividing 193,488,125 by 8 leaves remainder 5, so cat lands in bucket 5, exactly where the arrow points.
-
4
Lookup: Hash Again, Check One Bucket
Type cat again and press 'Search'. The table recomputes the same hash, jumps straight to bucket 5 and compares keys only inside that bucket. A solid outline means found; a dashed red outline means the key is missing. Press 'Delete' and the same lookup runs first, then the key is unlinked from its bucket.
-
5
Collision: Two Keys, One Bucket
With only 8 buckets, different keys must sometimes leave the same remainder. Insert act after cat: it also lands in bucket 5, the bucket turns orange and act hangs below cat in a chain. That is chaining — each bucket keeps a short list, and a lookup scans only that list. The 'Longest Chain' card shows the most crowded bucket.
-
6
Load Factor and Resizing
The 'Load Factor' card is entries divided by buckets: 6 keys in 8 buckets give 0.75. As it climbs, chains grow and lookups slow. Drag the 'Buckets' slider to 16 and every key is rehashed: cat moves from bucket 5 to bucket 13, the load factor halves and most chains split. Real hash tables resize automatically, often doubling once the load factor passes a threshold such as 0.75.
Key Takeaways
Hash functions convert keys to array indices
Any key — a string, number, or object — can be converted to an integer index that points to a position in an array.
Average O(1) lookup time
With a good hash function and a reasonable load factor, looking up a value by key requires only one computation and one array access.
Collisions are resolved with chaining or open addressing
Chaining uses a linked list per bucket. Open addressing finds the next empty slot. Both keep the table functional when keys collide.
Load factor decides when to resize
Entries divided by buckets measures how crowded the table is. Doubling the buckets and rehashing every key halves the load factor and keeps chains short.
Connected Concepts
Linked Lists
Chaining stores every key that shares a bucket in a small linked list hanging below it.
Modular Arithmetic
The bucket index is the remainder of the hash divided by the bucket count — pure mod arithmetic.
Big O Notation
Hashing gives average constant-time lookup, while a scan of an unsorted list grows linearly.
Bloom Filters
A Bloom filter runs several hash functions over one bit array to answer "maybe present" in tiny space.
Sorting
Hash tables and sorting are complementary: sorting enables binary search, hashing enables O(1) lookup.
Binary Numbers
Hash functions often use binary arithmetic to compute bucket indices.
Consistent Hashing
Hash keys and servers onto one ring, and adding a server moves only a small share of the keys instead of nearly all of them.
Updated
- — Title, description and step 1 now say what a hash table is and name hash function, collision and load factor.
- — New connection to Consistent Hashing.
- — Six hands-on steps: insert, a worked "cat" example, lookup, collisions and resizing, plus 2 new quiz items.