Java Collection Framework Deep Dive: 8 Core Interview Topics from ArrayList to ConcurrentHashMap
This comprehensive guide covers eight essential Java collection topics for interviews: ArrayList vs LinkedList internals, HashMap structure and resizing, JDK 1.7 vs 1.8 evolution, ConcurrentHashMap locking mechanisms, HashSet/TreeMap/LinkedHashMap implementations, collection hierarchy architecture, and thread-safe collection comparisons with performance analysis.
ArrayList vs LinkedList: Implementation and Use Cases
ArrayList uses a dynamic Object[] array with default initial capacity 10, expanding by 1.5x ( oldCapacity + (oldCapacity >> 1)). It provides O(1) random access but O(n) insertion/deletion due to element shifting. LinkedList uses a doubly-linked list with Node objects containing prev, item, next fields, enabling O(1) insertion/deletion at known positions but O(n) access.
Performance Comparison
get(int) : ArrayList O(1), LinkedList O(n)
add(E) tail : ArrayList O(1) amortized, LinkedList O(1)
add(int,E) head/middle : ArrayList O(n), LinkedList O(1) after locating node
remove(int) : ArrayList O(n), LinkedList O(n) locate + O(1) delete
remove(Object) : Both O(n)
Iteration : ArrayList very fast (contiguous memory), LinkedList slower (pointer jumps, cache misses)
Memory : ArrayList compact (no extra pointers), LinkedList two pointers per element
Selection Guidelines
Frequent random access/iteration → ArrayList (cache-friendly contiguous memory)
Heavy tail appends → ArrayList (amortized O(1), less pointer overhead)
Frequent head/middle insert/delete → LinkedList (pointer manipulation only)
Queue/Deque implementation → LinkedList (implements Deque interface)
Memory-sensitive, many small objects → ArrayList (LinkedList stores two extra pointers per node)
Batch removal/filtering → ArrayList ( removeAll uses bulk copy)
Concurrent iteration/modification → Neither; use CopyOnWriteArrayList or ConcurrentLinkedDeque In practice, ArrayList suffices for 90% of cases due to CPU cache line optimization. For frequent head insertion, consider ArrayDeque instead of LinkedList.
HashMap Internals: Array + LinkedList + Red-Black Tree
Structure (JDK 1.8+)
Array (hash buckets): default capacity 16 (power of 2), index = hash & (length-1) LinkedList: resolves collisions via chaining
Red-Black Tree: converts when list length ≥ 8 AND array length ≥ 64 ; reverts when tree nodes ≤ 6
Put Flow (5 Steps)
Compute hash: h ^ (h >>> 16) mixes high/low 16 bits
Determine index: (table.length - 1) & hash If bucket empty → new node; else handle collision: equals() check → overwrite or tail-insert into list/tree
Check treeify: treeifyBin() if length ≥ 8 and array ≥ 64
Check resize: if size ≥ capacity × 0.75 →
resize()Resize Mechanism
Trigger: size ≥ capacity × loadFactor (0.75) New capacity = old × 2 (always power of 2)
Migration: rehash by checking new high bit; 0 → same index, 1 → index + oldCapacity
Red-black trees may split back to lists if nodes ≤ 6
Why power of 2? Enables hash & (n-1) instead of modulo, ~10x faster, and ensures uniform distribution. Non-power-of-2 wastes buckets (e.g., length=10 uses only 4 of 10 buckets).
HashMap JDK 1.7 vs 1.8: Three Core Changes
Insertion : JDK 1.7 head-insert (new node at head); JDK 1.8 tail-insert (preserves order, avoids cyclic list during concurrent resize)
Structure : JDK 1.7 array + singly-linked list only; JDK 1.8 array + linked list + red-black tree (treeify at length≥8, array≥64)
Hash perturbation : JDK 1.7 9 operations (4 shifts + 5 XORs); JDK 1.8 1 operation: h ^ (h >>> 16) Resize rehash : JDK 1.7 recalculates hash for each node; JDK 1.8 high-bit split: check new high bit, no full rehash
Initialization : JDK 1.7 eager (constructor); JDK 1.8 lazy (first put())
Treeify threshold 8 based on Poisson distribution: at load factor 0.75, probability of 8 nodes in a bucket is 0.00000006. Threshold 6 for untreeify provides hysteresis buffer.
Hash perturbation simplified because resize splitting already disperses nodes; high-bit mixing suffices.
HashMap Design: Capacity Power of 2 & Load Factor 0.75
Capacity = 2^n
Index calculation: hash & (length-1) equals hash % length only when length is power of 2
Bitwise AND is single-cycle CPU instruction vs expensive modulo
Non-power-of-2 leaves trailing zeros in length-1, making odd indices unreachable (50% waste)
Resize optimization: only check new high bit (0→stay, 1→move to index+oldCapacity)
Load Factor = 0.75
Trade-off: 0.5 wastes space (frequent resize), 1.0 causes excessive collisions
Poisson distribution at 0.75: P(k=0)=0.6065, P(k=1)=0.3033, P(k=8)=0.00000006
0.75 × 2^n always integer (16→12, 32→24, 64→48), avoiding floating-point thresholds
ConcurrentHashMap: Segment Lock → CAS + synchronized
JDK 1.7: Segment Array
Segment[](default 16), each extends ReentrantLock, contains HashEntry[] Write locks one segment; max 16 concurrent writers
Drawbacks: coarse granularity (segment covers many buckets), fixed concurrency, O(n) list traversal
JDK 1.8: Fine-Grained Locking
Single Node[] table (like HashMap) + linked list + red-black tree
Locking: CAS for empty bucket; synchronized on bucket head node only
Read: lock-free, volatile on val and next Concurrency = array length (grows with resize)
Concurrent resize: multiple threads assist via ForwardingNode Size calculation: baseCount + CounterCell[] (striped counter)
Comparison
Lock granularity : 1.7 Segment (multiple buckets); 1.8 single bucket head node
Concurrency : 1.7 fixed 16; 1.8 array length (dynamic)
Empty bucket insert : 1.7 requires lock; 1.8 CAS lock-free
Treeify : 1.7 no; 1.8 yes (length≥8, array≥64)
Resize : 1.7 per-segment; 1.8 concurrent whole-table
Why synchronized over ReentrantLock? JVM optimizations (biased locking, lock coarsening) make it comparable or better, with simpler code.
HashSet, TreeMap, LinkedHashMap
HashSet
Wrapper around HashMap<E, Object> with dummy value PRESENT = new Object() Same structure: array + list + tree (JDK 1.8+)
Deduplication via hashCode() + equals() Use cases: fast deduplication, O(1)
contains()TreeMap
Red-black tree (self-balancing BST), implements NavigableMap Keys sorted by natural order ( Comparable) or custom Comparator No null keys; O(log n) for all operations
Range queries: subMap(), headMap(),
tailMap()LinkedHashMap
Extends HashMap + doubly-linked list
Two modes: insertion-order (default) or access-order ( accessOrder=true)
LRU cache implementation: extend and override
removeEldestEntry()public class LRUCache<K,V> extends LinkedHashMap<K,V> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true); // accessOrder=true
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > capacity;
}
}Collection Framework Architecture
Hierarchy
Collection
├─ List: ordered, duplicates, indexed
│ ├─ ArrayList (dynamic array)
│ ├─ LinkedList (doubly-linked list)
│ ├─ Vector (synchronized, legacy)
│ └─ CopyOnWriteArrayList (read-heavy)
├─ Set: no duplicates, mostly unordered
│ ├─ HashSet (HashMap-backed)
│ ├─ LinkedHashSet (insertion-order)
│ └─ TreeSet (TreeMap-backed, sorted)
└─ Queue
Map
├─ HashMap (array+list+tree)
├─ LinkedHashMap (HashMap + doubly-linked list)
├─ TreeMap (red-black tree)
├─ Hashtable (synchronized, legacy)
└─ ConcurrentHashMap (CAS+synchronized)Selection Cheatsheet
Indexed, duplicates → ArrayList (default)
Deduplication, unordered → HashSet Deduplication + insertion order → LinkedHashSet Deduplication + sorted/range → TreeSet Key-value, no order → HashMap Key-value + insertion/access order → LinkedHashMap (LRU)
Key-value + sorted keys → TreeMap Thread-safe Map → ConcurrentHashMap (not Vector/Hashtable)
Thread-Safe Collections: Four Approaches
Comparison
Vector : method-level synchronized, whole object lock, concurrency 1, read ★, write ★, iterator safe (locked), null yes, ❌ legacy
Hashtable : method-level synchronized, whole object lock, concurrency 1, read ★, write ★, iterator safe (locked), null no, ❌ legacy
Collections.synchronizedList : decorator + synchronized, whole object ( mutex), concurrency 1, read ★, write ★, iterator unsafe (manual sync needed), null yes, ★ low concurrency only
CopyOnWriteArrayList : copy-on-write + ReentrantLock, write global lock, reads unlimited, read ★★★★★, write ★, iterator safe (snapshot), null yes, ★★★ read-heavy
ConcurrentHashMap (1.7) : segment locks, segment granularity, concurrency 16, read ★★★, write ★★★, iterator weakly consistent, null no, ★★★ legacy compat
ConcurrentHashMap (1.8) : CAS + synchronized on bucket head, single bucket granularity, concurrency array length, read ★★★★, write ★★★★, iterator weakly consistent, null no, ★★★★★ primary choice
Key Insights
ConcurrentHashMaprejects null to avoid ambiguity: get(key)==null could mean absent or null value; concurrent containsKey() check not atomic synchronizedList vs Vector: different lock objects ( mutex vs this), synchronizedList wraps any List, iterator not auto-synchronized
JDK 8 dropped segments because: fixed concurrency (16), higher memory overhead, synchronized now optimized
CopyOnWriteArrayList copies array on write to allow lock-free reads; unsuitable for write-heavy or real-time consistency needs
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
