Data Structure

Hash Table

Turns a key into a bucket number with a hash function, so instead of searching everything you jump straight to one small bucket. Keys that land in the same bucket (collisions) are chained together. When buckets get crowded, the table grows and rehashes.

PutO(1) avg
GetO(1) avg
Worst caseO(n)
Resize at0.75 load

Try It — Animated Flow

[0]
empty
[1]
empty
[2]
owl
338
[3]
empty
[4]
cat
312
fox
333
[5]
empty
[6]
dog
314
bee
300
Each key is hashed to a bucket number. "cat" and "fox" both land in bucket 4, a collision, so they share a chain. Pick an operation and press Run.
Step 1 / 1
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

The small number under each key is its hash: the sum of its character codes. Its bucket is that number modulo the bucket count.

Java Implementation

Real-Life Usage

Caches
Redis, Memcached, and browser caches look values up by key in O(1), whatever the size.
Counting and de-duplicating
Word counts or “have I seen this before?” checks take a single O(n) pass with a HashMap or HashSet.
Database joins
A hash join builds a hash table on one table's keys, then probes it once for each row of the other.
Programming languages
JavaScript objects, Python dicts, and compiler symbol tables are all hash tables under the hood.

Trade-offs

Reach for a hash table when
  • You look things up by an exact key: IDs, names, URLs
  • You're counting, grouping, or removing duplicates
  • The order of items doesn't matter
Avoid it when
  • You need sorted order, ranges, or min/max (use a BST/TreeMap)
  • The hash is poor: everything piles into one bucket and becomes O(n)
  • Memory is tight: empty buckets and per-entry overhead add up