Skip to content
Java Collection Framework Deep Dive: 8 Core Interview Topics from ArrayList to ConcurrentHashMap

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.

Rain's Path to Java Mastery
Rain's Path to Java Mastery
Rain's Path to Java Mastery

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

ConcurrentHashMap

rejects 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

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

Thread SafetyHashMapConcurrentHashMapinterview preparationArrayListLinkedListTreeMapJava Collections
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.