Maps & HashTables
Learn how hash-based data structures provide O(1) average-time operations for storing and retrieving key-value pairs.
What is a HashMap?
A HashMap stores key-value pairs and provides fast access using a hash function. Think of it like a dictionary where you can instantly look up a word (key) to find its definition (value).
map.put("apple", 5);
map.get("apple"); // returns 5
map.get("apple"); // returns 5
What is a HashSet?
A HashSet stores unique elements only. It's implemented using a HashMap internally, where elements are stored as keys. Perfect for checking membership or removing duplicates.
set.add("apple");
set.add("apple"); // duplicate rejected
set.contains("apple"); // true
set.add("apple"); // duplicate rejected
set.contains("apple"); // true
Time Complexity Comparison
| Operation | HashMap | TreeMap | ArrayList |
|---|---|---|---|
| Insert | O(1)* | O(log n) | O(1) / O(n) |
| Search | O(1)* | O(log n) | O(n) |
| Delete | O(1)* | O(log n) | O(n) |
| Ordered? | No | Yes | Yes |
* Average case. Worst case is O(n) with poor hash function or many collisions.
Topics
Hashing Basics
Learn how hash functions work and how keys map to bucket indices.
HashMap
Explore put, get, remove operations with visual table view.
HashSet
Understand sets and how duplicates are rejected.
Load Factor & Rehashing
Watch hash tables resize when they get too full.
Practice
Test your understanding with hands-on exercises.
When to Use HashMap vs HashSet
Use HashMap when:
- • You need to associate values with keys
- • Counting occurrences (word frequency)
- • Caching computed results
- • Looking up data by ID
- • Phone book (name → number)
Use HashSet when:
- • You only need to track unique items
- • Removing duplicates from a list
- • Checking if item exists (membership)
- • Finding intersection/union of collections
- • Tracking visited nodes in graph traversal