HashMap / Hash Table

📋 Quick Reference

Property	Value
Type	Key-value mapping with hashing
Get/Put	O(1) average, O(n) worst case
Contains	O(1) average
Memory	O(n) + load factor overhead
Ordering	No guaranteed order
Best For	Fast key-based lookup, caching, counting

One-liner: Hash-based map providing O(1) average-time key lookup via hash codes and buckets.

🎮 Interactive Visualizer

Watch how HashMap stores and retrieves values using hash codes and bucket arrays:

HashMap Operations
Avg: O(1)Worst: O(n)
1 / 20
Initialize HashMap with 8 buckets. Each bucket is a linked list for collision handling.
Real-World Use Cases
📚 Caches
🔑 Session stores
📊 Counting/Grouping
🔗 Database indexes
#️⃣ Hash Function
index = hashCode(key) % capacity
Same key → same index (deterministic) • Different keys may collide → chaining
⚠️ Good hash function minimizes collisions • Load factor > 0.75 triggers resize
Ready to hash...
Bucket Array (capacity: 8)
0
∅
1
∅
2
∅
3
∅
4
∅
5
∅
6
∅
7
∅
Pseudocode
1function put(key, value):
2  hash = hashCode(key)
3  index = hash % capacity
4  bucket = buckets[index]
5  for entry in bucket:
6    if entry.key == key:
7      entry.value = value
8      return
9  bucket.add(Entry(key, value))
10 
11function get(key):
12  hash = hashCode(key)
13  index = hash % capacity
14  bucket = buckets[index]
15  for entry in bucket:
16    if entry.key == key:
17      return entry.value
18  return null
Variables
—
Keyboard Shortcuts
P Play / Pause
[ Step back
] Step forward
R Reset
Speed
Current bucket
Current bucket
Insert/Update
Insert/Update
Found
Found
Not found
Not found
P · [ ] · R
Loading visualizer...

Try these operations:

Put key-value pairs - see hash calculation and bucket placement
Cause a collision - watch chaining in action
Get a value - observe the O(1) lookup path
Remove an entry - see bucket cleanup

🔧 Key Operations

Creating

JAVA(11 lines)
Code
Loading syntax highlighter...

Adding/Updating

JAVA(8 lines)
Code
Loading syntax highlighter...

Retrieving

JAVA(4 lines)
Code
Loading syntax highlighter...

Removing

JAVA(3 lines)
Code
Loading syntax highlighter...

Iteration

JAVA(14 lines)
Code
Loading syntax highlighter...

📊 Complexity Analysis

Operation	Average	Worst Case	Notes
`get(key)`	O(1)	O(n)	Worst when all hash to same bucket
`put(key, val)`	O(1)	O(n)	May trigger rehash
`remove(key)`	O(1)	O(n)
`containsKey`	O(1)	O(n)
`containsValue`	O(n)	O(n)	Always scans all
`size()`	O(1)	O(1)	Stored as field

Hash Table Internals

Hash Code → Bucket Index → Search Chain

bucket[0]: null
bucket[1]: Entry("cat", 5) → Entry("act", 3) → null  // collision chain
bucket[2]: Entry("dog", 7) → null
bucket[3]: null
...

Load Factor = entries / buckets (default 0.75)

When exceeded, table doubles and rehashes all entries

✅ When to Use HashMap

Good Use Cases

Fast key lookup - caching, memoization
Counting occurrences - word frequency, etc.
Grouping data - partition by some key
De-duplication - track seen items

Avoid When

Need ordering - use LinkedHashMap (insertion) or TreeMap (sorted)
Need thread safety - use ConcurrentHashMap
Null keys matter - HashMap allows one null key, unlike some alternatives
Keys are mutable - changing key after insertion breaks the map!

⚠️ Common Pitfalls

1. Mutable Keys

JAVA(7 lines)
Code
Loading syntax highlighter...

2. Missing equals/hashCode

JAVA(8 lines)
Code
Loading syntax highlighter...

3. Null Confusion

JAVA(9 lines)
Code
Loading syntax highlighter...

4. Iteration Order Assumption

JAVA(7 lines)
Code
Loading syntax highlighter...

🎯 Interview Practice

Test your hash table knowledge with 10 curated interview questions:

HashMap (Interview Mode)
Interview ModeO(1) avgHash Table
1 / 16
Initialize HashMap with 8 buckets
Use cases:Caching, counting, grouping, indexing, deduplication
Not thread-safe:Use ConcurrentHashMap for concurrent access
Bucket Array (capacity: 8)
0
∅
1
∅
2
∅
3
∅
4
∅
5
∅
6
∅
7
∅
Speed
Current bucket
Current bucket
Insert/Update
Insert/Update
Found
Found
Not found
Not found
P · [ ] · R
Loading visualizer...

🎤 Interview Tips

Q: How does HashMap handle collisions?

"

In Java 8+, it uses chaining with linked lists that convert to red-black trees when a bucket exceeds 8 entries. This improves worst-case from O(n) to O(log n).

Q: Why is load factor 0.75 the default?

"

It's a balance between space and time. Lower means fewer collisions but more memory. Higher means more collisions. 0.75 provides good performance for most use cases.

Q: What makes a good hash function?

"

It should distribute keys uniformly across buckets, be fast to compute, and be consistent (same input always gives same output). Poor distribution causes clustering and O(n) lookups.

Q: HashMap vs Hashtable?

"

HashMap is not synchronized (faster for single-threaded), allows null key/values. Hashtable is legacy, synchronized, no nulls. Use ConcurrentHashMap for thread safety.

Previous: Part 2: LinkedList

Next: Part 4: TreeSet / BST

Visualizer: HashMap from @tomaszjarosz/react-visualizers