HashMap

A HashMap stores key–value pairs and finds a key in about one step: a hash function turns the key into a bucket number, so it looks in one bucket instead of searching everything.

An empty HashMap

Operation

Press Play to run the operations below.

  1. PUT apple=10
  2. PUT banana=20
  3. PUT lemon=30
  4. PUT melon=40
  5. GET melon

Buckets

  1. 0
    empty
  2. 1
    empty
  3. 2
    empty
  4. 3
    empty
  5. 4
    empty
  6. 5
    empty
  7. 6
    empty
  8. 7
    empty

8 buckets, all empty. Every key will be turned into a bucket number.

Step 1 / 24
Entries
0
Collisions
0
Load factor
0.00

Try PUT "lemon" then "melon" — anagrams have the same character sum, so they land in the same bucket.

What's happening?

  1. The key is hashed — here, its character codes are added up — and the hash modulo the number of buckets picks the bucket.
  2. PUT stores the entry in that bucket; GET and REMOVE go straight to the same bucket.
  3. When two keys land in one bucket (a collision), the bucket keeps a short list and is walked entry by entry.

Complexity

Time
O(1) on average for put, get and remove; O(n) in the worst case
Space
O(n)

Where you'll meet it

Caches, counting word frequencies, de-duplicating, database indexes in memory, session stores, and the two-sum style of interview problem.

Common mistake

Using a mutable object as a key, or overriding equals() without hashCode() in Java — the map then looks in the wrong bucket and "loses" entries.

FAQ

Why is a HashMap O(1)?

The hash tells it which bucket to look in, so the work does not grow with the number of entries — as long as buckets stay short.

What is a collision?

Two different keys hashing to the same bucket. Chaining keeps both in a small list in that bucket.

What is the load factor?

Entries divided by buckets. Java's HashMap doubles its buckets when it passes 0.75, keeping lists short.

Is this the hash function real HashMaps use?

No — summing character codes is chosen to be easy to follow, and it collides a lot. Real hashes spread keys far more evenly.