Quick Recap: Maps in Java

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 synchronized keyword 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