This content originally appeared on DEV Community and was authored by shantanu mahakale
Java provides multiple Map implementations — each designed for different use cases such as fast lookups, sorted data, concurrency, or predictable order. Understanding their internal working helps in writing performant code.
Main Map Implementations
| Map Type | Ordering | Thread-Safe | Best For |
|---|---|---|---|
| HashMap | No order | ❌ No | Fast lookup |
| LinkedHashMap | Insertion order | ❌ No | Caching (LRU) |
| TreeMap | Sorted order | ❌ No | Range queries |
| ConcurrentHashMap | No order | ✔ Yes | Concurrent access |
1. HashMap (Most Used)
- Uses array + linked list / tree (red-black tree)
- Default capacity = 16, load factor = 0.75
- Collisions handled using chaining
Hashing Logic:
index = hash(key) & (n - 1) // n = array size
When collision occurs:
- Java 8+: if bucket size > 8 → converts list → tree (better performance)
Time Complexity:
| Operation | Average | Worst |
|-----------|---------|-------|
| get/put | O(1) | O(n) (if all collide) |
Best For: Fast lookups, general-purpose storage
Not Thread-safe
2. LinkedHashMap
- Extends
HashMap→ maintains insertion order - Uses doubly linked list + HashMap
- Can be used for LRU Cache
// LRU Cache Example
LinkedHashMap<K,V> cache = new LinkedHashMap<>(16, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > 100;
}
};
Best For: Caching / maintaining order
3. TreeMap
- Implements Red-Black Tree
- Keys sorted in natural order or using
Comparator - Supports range queries, floorKey(), ceilingKey()
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "A");
map.put(5, "B");
Time Complexity (always):
-
get()→ O(log n) -
put()→ O(log n)
Best For: Sorted data, range-based queries
Cannot store null keys
4. ConcurrentHashMap
- Thread-safe, non-blocking concurrent access
- Uses bucket-level locking (segments) in Java 7
- Java 8+: CAS + synchronized blocks, no segments
Key Idea:
- Multiple threads can read/write safely
- No
synchronizedkeyword needed
// Example
Map<String, Integer> map = new ConcurrentHashMap<>();
map.put("A", 1);
Best For: Highly concurrent applications
Internal Comparison
| Feature | HashMap | LinkedHashMap | TreeMap | ConcurrentHashMap |
|---|---|---|---|---|
| Order | No | Insertion | Sorted | No |
| Thread-safe | No | No | No | Yes |
| Null Keys | 1 allowed | 1 allowed | ❌ No | ❌ No |
| Performance | Fastest | Slight overhead | O(log n) | High in concurrency |
When to Use What?
| Scenario | Recommended Map |
|---|---|
| Fast lookup | HashMap |
| Maintain order | LinkedHashMap |
| Sorted data | TreeMap |
| Multithreading | ConcurrentHashMap |
| LRU Cache | LinkedHashMap |
| Range queries | TreeMap |
This content originally appeared on DEV Community and was authored by shantanu mahakale
shantanu mahakale | Sciencx (2025-11-21T16:09:32+00:00) Quick Recap: Maps in Java. Retrieved from https://www.scien.cx/2025/11/21/quick-recap-maps-in-java/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.