Overview
The Java Collections Framework is a frequent interview topic because the implementations hide non-obvious complexity. Understanding the internals — why HashMap resizes, how ConcurrentHashMap avoids global locks, why random UUID keys hurt B-tree performance — separates senior engineers from the rest.
Architecture
HASHMAP INTERNALS (Java 8+)
════════════════════════════════════════════════════════
put("apple", 1):
hash("apple") = 3029837 → index = hash & (capacity-1) = 3029837 & 15 = 5
Bucket Array (capacity=16, default)
┌──┬──┬──┬──┬──┬──────────────────────┬──┬──┐
│ │ │ │ │ │ bucket[5] │ │ │
└──┴──┴──┴──┴──┴──────────────────────┴──┴──┘
│
▼ Linked list (< 8 entries)
Node{hash,key="apple",value=1,next}
│
▼
Node{hash,key="X",value=Y,next=null}
TREEIFY at 8 entries (Java 8):
TreeNode (Red-Black tree, O(log n))
RESIZE at load factor 0.75 (12 entries in size-16 map):
New capacity = 32, all entries rehashed and redistributed
CONCURRENTHASHMAP (Java 8)
════════════════════════════════════════════════════════
Java 7: 16 Segments, each with its own ReentrantLock
(16 concurrent writers max)
Java 8: CAS for empty buckets, synchronized per bucket head
for collision chains. No global lock at all.
putIfAbsent: CAS on empty bucket → O(1) lock-free
put collision: synchronized(bucketHead) → only blocks same-bucket writers
read: always lock-free (volatile reads)
Max concurrency: number of buckets (default 16, grows with table)
TREEMAP: RED-BLACK TREE
════════════════════════════════════════════════════════
Sorted by natural order or Comparator.
O(log n) all operations.
NavigableMap API:
floorKey(k) → largest key ≤ k
ceilingKey(k) → smallest key ≥ k
headMap(k) → view of keys < k
tailMap(k) → view of keys ≥ k
subMap(k1, k2) → view of keys in [k1, k2)
GENERICS: PECS RULE
════════════════════════════════════════════════════════
PECS = Producer Extends, Consumer Super
List<? extends Animal> ← can READ animals (producer)
cannot ADD (compiler can't know exact type)
List<? super Dog> ← can ADD dogs (consumer)
can only READ as Object (might be Animal or Object)
Copy example:
static <T> void copy(List<? extends T> src, List<? super T> dst)
src produces T elements, dst consumes T elements.
Technical Implementation
LRU Cache Using LinkedHashMap
// LinkedHashMap maintains insertion OR access order.
// Override removeEldestEntry to cap size → O(1) LRU cache.
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxSize;
public LRUCache(int maxSize) {
// accessOrder=true: get() moves entry to tail (most recently used)
super(maxSize, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize; // evict LRU entry when over capacity
}
// Thread-safe wrapper
public static <K, V> Map<K, V> threadSafe(int maxSize) {
return Collections.synchronizedMap(new LRUCache<>(maxSize));
}
}
// Usage
LRUCache<String, User> userCache = new LRUCache<>(1000);
userCache.put("user:1", user);
User u = userCache.get("user:1"); // moves to tail (recently used)
ConcurrentHashMap for Thread-Safe Aggregation
// computeIfAbsent is atomic in ConcurrentHashMap — safe for memoization
public class MetricsAggregator {
private final ConcurrentHashMap<String, LongAdder> counters = new ConcurrentHashMap<>();
public void increment(String metric) {
// computeIfAbsent is atomic: creates LongAdder only if absent
counters.computeIfAbsent(metric, k -> new LongAdder()).increment();
}
public long get(String metric) {
LongAdder adder = counters.get(metric);
return adder == null ? 0 : adder.sum();
}
// merge: atomic read-modify-write
public void addToTotal(String key, long value) {
counters.merge(key,
new LongAdder(){{ add(value); }},
(existing, newVal) -> { existing.add(value); return existing; }
);
}
}
Generic Bounded Wildcards (PECS)
public class CollectionUtils {
// Copy from producer (extends) to consumer (super)
public static <T> void copy(List<? extends T> src, List<? super T> dst) {
for (T item : src) {
dst.add(item);
}
}
// Sum a list of any Number subtype (Integer, Double, Long...)
public static double sum(List<? extends Number> numbers) {
return numbers.stream().mapToDouble(Number::doubleValue).sum();
}
// Add multiple dogs to any list that can hold dogs (Dog, Animal, Object)
public static void addSomeDogs(List<? super Dog> list) {
list.add(new Labrador());
list.add(new Poodle());
}
// TreeMap range query: all users in age range
public static <K extends Comparable<K>, V> List<V> rangeQuery(
TreeMap<K, V> map, K from, K to) {
return new ArrayList<>(map.subMap(from, true, to, true).values());
}
}
// Type-safe heterogeneous container (Effective Java pattern)
public class TypeSafeMap {
private Map<Class<?>, Object> map = new HashMap<>();
public <T> void put(Class<T> type, T value) { map.put(type, value); }
@SuppressWarnings("unchecked")
public <T> T get(Class<T> type) { return type.cast(map.get(type)); }
}
Interview Preparation
Q: What happens in a HashMap when the load factor threshold is exceeded?
When the number of entries exceeds capacity × loadFactor (default: 16 × 0.75 = 12 entries), HashMap creates a new array with double the capacity (32) and rehashes every existing entry into the new array. This is O(n) and causes a brief pause — important for real-time applications. Mitigation: pre-size the map with new HashMap<>(expectedSize / 0.75 + 1) to avoid resizes. Java 8 also treeifies individual buckets when a bucket chain exceeds 8 nodes (and untreeifies below 6), converting linked lists to Red-Black trees for O(log n) worst-case bucket access.
Q: Why is ConcurrentHashMap faster than Hashtable?
Hashtable synchronizes on this — every read and write acquires the same global lock, so all threads serialize. ConcurrentHashMap (Java 8) uses CAS for puts on empty buckets (no lock at all) and synchronized on the individual bucket head node for collisions — only threads accessing the same bucket contend. Reads are always lock-free (volatile head node). This means with 16 buckets, 16 threads can write to different buckets simultaneously. At the cost of weaker iteration consistency (no snapshot), you get near-linear throughput scaling.
Q: What is the PECS principle for generics wildcards?
PECS = Producer Extends, Consumer Super. If you're reading (producing) values FROM a collection, use ? extends T — this lets you pass List<Dog> where List<? extends Animal> is expected. If you're writing (consuming) values INTO a collection, use ? super T — this lets you pass List<Animal> where List<? super Dog> is expected. Collections.copy(dst, src) is the canonical example: src is List<? extends T> (we read from it), dst is List<? super T> (we write into it).
Q: When would you use TreeMap over HashMap?
TreeMap when you need sorted order or range queries: find all keys between X and Y (subMap), find the nearest key below a value (floorKey), iterate in sorted order. Real use cases: a scheduler where keys are timestamps (find all jobs due within the next 60 seconds with headMap), an order book (price levels sorted ascending/descending), autocomplete (find all strings with a given prefix with subMap). HashMap for O(1) exact lookups where order doesn't matter.
Learning Resources
- OpenJDK HashMap source
- Java ConcurrentHashMap internals
- Effective Java — Bloch, Item 29–33 (Generics)
- Java Generics FAQ — Angelika Langer