Hash Tables: Hash Functions, Buckets and Collisions

Play

Hash a key, jump straight to its bucket, and watch collisions chain

Computer Science Data Structures intermediate 12 min

This concept builds on Binary Numbers — How Computers Count, Modular Arithmetic, Linked Lists — Pointers & Connections. Consider exploring them first for the best experience.

Step 1 of 6

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.

Play Hash Hotel A game about Hash Tables

How It Works — Step by Step

Step 1 of 6
  1. 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. 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. 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. 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. 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. 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.

Added
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.