3. Java Collections Framework — Architect-Level Deep Dive

3. Java Collections Framework — Architect-Level Deep Dive

3.1 List, Set, Map Hierarchies and Implementations

Core Interface Hierarchy

Iterable
└── Collection
    ├── List (ordered, duplicates allowed, index-based)
    │   ├── ArrayList
    │   ├── LinkedList
    │   ├── Vector (legacy, synchronized)
    │   └── CopyOnWriteArrayList
    ├── Set (no duplicates)
    │   ├── HashSet (backed by HashMap)
    │   ├── LinkedHashSet (backed by LinkedHashMap)
    │   ├── TreeSet (backed by TreeMap, NavigableSet)
    │   └── EnumSet
    └── Queue / Deque
        ├── PriorityQueue
        ├── ArrayDeque
        └── LinkedList (also implements Deque)

Map (not a Collection — separate hierarchy)
├── HashMap
├── LinkedHashMap
├── TreeMap (NavigableMap, SortedMap)
├── Hashtable (legacy, synchronized)
├── ConcurrentHashMap
└── WeakHashMap / IdentityHashMap / EnumMap

Key architectural distinctions:

Aspect List Set Map
Duplicates Allowed Not allowed Keys unique, values can duplicate
Ordering Insertion order (index) Implementation-dependent Implementation-dependent
Null elements Multiple nulls allowed One null allowed (except TreeSet) One null key (except TreeMap, Hashtable)
Access pattern Index-based O(1)/O(n) Hash/tree-based lookup Hash/tree-based lookup

Why Map isn’t a Collection: A Map<K,V> doesn’t fit the Collection<E> contract of single-element operations (add(E), contains(E)). It exposes its collection views instead — keySet(), values(), entrySet() — which are Collection/Set instances backed by the map, so mutations on the view propagate to the map (except via entrySet() for adding new entries, which is unsupported).

Architect-level decision points:

  • Need insertion-order iteration with O(1) lookup → LinkedHashMap/LinkedHashSet
  • Need sorted iteration → TreeMap/TreeSet (O(log n) operations, red-black tree)
  • Need thread-safety without external locking → ConcurrentHashMap, CopyOnWriteArrayList
  • LRU cache implementation → LinkedHashMap with accessOrder=true + overridden removeEldestEntry()

3.2 ArrayList vs LinkedList — Internal Structure

ArrayList — backed by Object[] array

transient Object[] elementData;
private int size;
  • Default capacity 10; grows via grow() → new capacity = oldCapacity + (oldCapacity >> 1) (1.5x growth, not 2x — a common interview trap).
  • Arrays.copyOf() triggers a full array copy on resize — O(n) amortized to O(1) per add().
  • Random access get(index) is O(1) — direct array indexing.
  • Insertion/deletion at arbitrary index is O(n) — requires System.arraycopy() shift of subsequent elements.
  • Cache-friendly: contiguous memory layout means excellent CPU cache locality, which in practice makes ArrayList faster than LinkedList even for some O(n) operations due to cache misses dominating LinkedList traversal cost.

LinkedList — doubly linked list of Node<E>

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}
transient Node<E> first;
transient Node<E> last;
  • No capacity/resizing concerns — pure pointer manipulation.
  • get(index) is O(n) — must traverse from first or last, whichever is closer (it bisects based on index vs size/2).
  • addFirst()/addLast()/removeFirst()/removeLast() are O(1) — this is LinkedList’s actual strength, which is why it implements Deque.
  • Insertion/deletion at a known node (via ListIterator) is O(1) since no shifting is needed — but locating that node is still O(n).
  • Higher memory overhead per element: each Node carries two pointers + object header, vs ArrayList’s flat slot.

Practical guidance for architects:

Use case Choice Reason
Frequent random access, infrequent mutation ArrayList O(1) get, cache locality
Frequent head/tail insertion (queue/stack semantics) LinkedList or ArrayDeque O(1) at ends
General-purpose default ArrayList Better cache behavior, lower memory overhead per element
Implementing Deque/Queue ArrayDeque (preferred over LinkedList) Array-backed circular buffer, better cache locality, no per-node allocation

Note: Modern guidance (post-Java 6) generally avoids LinkedList even for deque use cases — ArrayDeque outperforms it in nearly all benchmarks due to cache locality, despite LinkedList’s “theoretical” O(1) advantage.

3.3 HashMap Internals (Buckets, Hashing, Resize, Java 8 Tree-ification)

Structure:

transient Node<K,V>[] table;  // array of buckets
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Hashing process:

  1. hash(key) — applies a supplemental hash spreading function: 
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

    This XORs the high 16 bits into the low 16 bits — guards against poor hashCode() implementations where lower bits lack entropy, especially important since table.length is always a power of 2.

  2. Bucket index = (n - 1) & hash — equivalent to hash % n but faster since n is power-of-2 (bitmask AND vs modulo division).
  3. Collision handling: Each bucket holds a linked list of Node<K,V> by default. On collision, new nodes append to the list; lookup degrades to O(n) within that bucket.

Resize (rehashing):

  • Triggered when size > capacity * loadFactor (i.e., 12 entries at default 16 capacity/0.75 LF).
  • New capacity = oldCapacity << 1 (doubling).
  • Java 8 optimization: during resize, entries either stay at the same index or move to index + oldCapacity — determined by checking one additional bit (hash & oldCapacity), avoiding full rehash recomputation. This split is done in-place without recalculating hash().

Java 8 Tree-ification:

  • When a single bucket’s linked-list length reaches TREEIFY_THRESHOLD (8), and total table capacity ≥ MIN_TREEIFY_CAPACITY (64), that bucket converts to a red-black tree (TreeNode extends Node), improving worst-case lookup from O(n) to O(log n).
  • If capacity < 64 but a bucket hits 8 collisions, the table resizes instead of tree-ifying (resizing first is preferred since small tables shouldn’t pay tree overhead).
  • Reverse: if a tree bucket shrinks to ≤ UNTREEIFY_THRESHOLD (6) during removal, it converts back to a linked list.
  • This defends against hash-flooding/algorithmic-complexity attacks where adversarial keys are crafted to collide into the same bucket (especially relevant for HashMap<String,V> exposed to untrusted input, e.g., HTTP parameter maps).

Why HashMap requires equals()/hashCode() contract:

  • Equal objects must produce equal hash codes (otherwise lookups fail to find existing keys).
  • Mutable keys (especially mutating fields used in hashCode()) after insertion corrupt the structure — the entry becomes unreachable via get() since it’s still physically in its old bucket but a fresh hash computation points elsewhere.

Load factor trade-off: Lower load factor (e.g., 0.5) → fewer collisions, faster lookups, more memory/more frequent resizing. Higher load factor (e.g., 0.9) → more collisions, less memory, less frequent resizing. 0.75 is empirically the time/space sweet spot.

3.4 ConcurrentHashMap vs Synchronized Map vs Hashtable

Hashtable Collections.synchronizedMap() ConcurrentHashMap
Locking granularity Entire map (every method synchronized) Entire map (single monitor wraps delegate) Per-bucket (Java 8+: CAS + synchronized on bin head node)
Null keys/values Not allowed Depends on backing map Not allowed (deliberate — avoids ambiguity between “absent” and “mapped to null” in concurrent reads)
Iterator Fail-fast Fail-fast (requires manual sync during iteration) Weakly consistent — doesn’t throw ConcurrentModificationException, reflects state at some point during/after iterator creation
Read concurrency Blocking Blocking Non-blocking for reads (volatile reads on Node fields)
Performance under contention Poor Poor Good — lock striping minimizes contended sections
Legacy status Legacy (pre-Collections framework) Wrapper utility Modern, JSR-166 (Doug Lea)

ConcurrentHashMap internals (Java 8+ redesign):

  • Abandoned Java 7’s Segment[] lock-striping array in favor of synchronizing on individual bucket head nodes directly — finer granularity, lower memory overhead.
  • Writes use Unsafe.compareAndSwapObject (CAS) for inserting into an empty bucket — completely lock-free in the common case.
  • Only when a bucket already has a colliding chain does it synchronize on that bucket’s first node — meaning concurrent writes to different buckets never block each other.
  • Size tracking uses a striped counter (LongAdder-style CounterCell[]) rather than a single AtomicLong, reducing CAS contention from concurrent put() calls across threads.
  • size() is therefore an approximation under concurrent modification — by design, since an exact count would require a global lock, defeating the purpose.
  • Bucket tree-ification (red-black trees for long chains) applies here too, same thresholds as HashMap.

Compound atomic operations: ConcurrentHashMap provides computeIfAbsent(), merge(), compute() as atomic, lock-protected-per-bucket operations — critical for things like counters/caches where check-then-act on a plain HashMap + external lock would be both slower and easier to get wrong.

Architect guidance: Never recommend Hashtable or synchronizedMap() for new code unless interfacing with legacy APIs that require them. ConcurrentHashMap is the default for any shared mutable map in multi-threaded service code (caches, counters, session registries).

3.5 TreeMap/TreeSet and Comparable vs Comparator

Backing structure: Both are backed by a red-black tree (self-balancing BST) — guarantees O(log n) for get, put, remove, containsKey, and ordered traversal.

TreeMap implements NavigableMap giving methods beyond SortedMap:

  • floorKey(), ceilingKey(), lowerKey(), higherKey() — nearest-match lookups.
  • firstEntry(), lastEntry(), pollFirstEntry(), pollLastEntry().
  • headMap(), tailMap(), subMap() — range views (live, backed by the original map).

Comparable (intrinsic ordering):

class Employee implements Comparable<Employee> {
    public int compareTo(Employee other) {
        return Integer.compare(this.id, other.id);
    }
}
  • Defines the class’s “natural ordering” — single, fixed sort order baked into the class itself.
  • Used automatically by TreeMap/TreeSet/Collections.sort() when no Comparator is supplied.

Comparator (extrinsic ordering):

Comparator<Employee> bySalaryDesc = Comparator
    .comparing(Employee::getSalary).reversed()
    .thenComparing(Employee::getName);
  • Defines ordering external to the class — lets you sort the same objects multiple ways without modifying the class.
  • Required when the class doesn’t implement Comparable, or when you need an alternate ordering.
  • Java 8 added the fluent comparing()/thenComparing()/reversed() chain, replacing verbose anonymous-class comparators.

Critical contract — consistency with equals():

  • TreeMap/TreeSet use compareTo()/compare() exclusively for both ordering and equality determination — compareTo() == 0 is treated as “duplicate,” not equals(). If your compareTo() isn’t consistent with equals(), TreeSet can silently “lose” elements that equals() would consider distinct, which is a frequent production bug source. Document this deviation explicitly if intentional (e.g., a case-insensitive String comparator in a TreeSet<String>).

When TreeMap/TreeSet vs HashMap/HashSet:

  • Need sorted iteration or range queries (floor/ceiling, subMap) → TreeMap/TreeSet, accept O(log n) over O(1).
  • Need pure fastest lookup with no ordering requirement → HashMap/HashSet.
  • Need insertion-order iteration without sort overhead → LinkedHashMap/LinkedHashSet.

3.6 Fail-Fast vs Fail-Safe Iterators

Fail-Fast (ArrayList, HashMap, HashSet, most java.util collections):

  • Maintains a modCount field, incremented on every structural modification (add/remove, not set).
  • Iterator captures expectedModCount at creation; every next() call checks modCount != expectedModCount and throws ConcurrentModificationException (CME) if they diverge.
  • This is a best-effort detection mechanism, not a guarantee — the Javadoc explicitly states CME should not be relied upon for correctness, only to catch bugs. It’s possible for concurrent modification to go undetected (e.g., removing the second-to-last element of an ArrayList during iteration can sometimes avoid throwing CME due to how the bounds check interacts with size).
  • The correct way to remove during iteration is Iterator.remove() itself — which updates expectedModCount in lockstep, avoiding the exception.

Fail-Safe (ConcurrentHashMap, CopyOnWriteArrayList, ConcurrentSkipListMap):

  • CopyOnWriteArrayList: every mutation (add/remove/set) creates a new copy of the entire underlying array; iterators hold a reference to the array snapshot at iterator-creation time, so they never see subsequent modifications and never throw CME.
    • Trade-off: write operations are O(n) (full array copy) — appropriate only for read-heavy, write-rare scenarios (e.g., listener lists, configuration caches).
  • ConcurrentHashMap: iterators are weakly consistent — they reflect some state of the map as of iterator creation or later, may or may not show concurrent updates, but never throw CME and never return the same element twice.
    • This isn’t a full snapshot like CopyOnWrite — it’s a traversal that tolerates concurrent structural changes without locking, by virtue of how the underlying bucket/node structure is updated (new nodes inserted via CAS at bucket heads, traversal follows volatile next pointers).

Architect-relevant distinction: “Fail-safe” doesn’t mean “sees a consistent snapshot” except for CopyOnWriteArrayList. For ConcurrentHashMap, fail-safe means “won’t crash, but don’t assume the iteration reflects the map as of any single instant” — important when reasoning about correctness in concurrent batch-processing code.

3.7 Java 8+ Collection Enhancements

Immutable Collections (Java 9+ factory methods):

List<String> list = List.of("a", "b", "c");
Set<String> set = Set.of("a", "b");
Map<String, Integer> map = Map.of("a", 1, "b", 2);
Map<String, Integer> map2 = Map.ofEntries(
    Map.entry("a", 1), Map.entry("b", 2)
);
  • Returned instances are genuinely immutable — add()/put()/remove() throw UnsupportedOperationException, unlike Collections.unmodifiableList() which only prevents mutation through that wrapper while the backing list remains mutable elsewhere.
  • List.of()/Set.of() reject null elements (throws NullPointerException) — a deliberate defensive design choice, unlike legacy collections.
  • Set.of() and Map.of() have randomized iteration order per JVM run (salted hashing) — intentionally prevents code from accidentally depending on iteration order, exposing such bugs early.
  • Backed by specialized internal implementations (ImmutableCollections.ListN, etc.) optimized for small fixed sizes rather than general-purpose ArrayList/HashMap overhead.

Stream Collectors (java.util.stream.Collectors):

Key collectors an architect should reach for fluently:

// Grouping
Map<Department, List<Employee>> byDept = 
    employees.stream().collect(Collectors.groupingBy(Employee::getDept));

// Grouping + downstream aggregation
Map<Department, Double> avgSalaryByDept =
    employees.stream().collect(
        Collectors.groupingBy(Employee::getDept, 
            Collectors.averagingDouble(Employee::getSalary)));

// Partitioning (boolean split)
Map<Boolean, List<Employee>> partitioned =
    employees.stream().collect(Collectors.partitioningBy(e -> e.getSalary() > 100000));

// Joining
String csv = names.stream().collect(Collectors.joining(", ", "[", "]"));

// To unmodifiable collection (Java 10+)
List<String> immutable = stream.collect(Collectors.toUnmodifiableList());

// Teeing (Java 12+) — combine two collectors' results
var result = employees.stream().collect(Collectors.teeing(
    Collectors.counting(),
    Collectors.summingDouble(Employee::getSalary),
    (count, total) -> total / count   // manual average, demonstrating composition
));

Other notable enhancements:

  • Map.computeIfAbsent(), computeIfPresent(), merge(), getOrDefault() — reduce common null-check/check-then-act boilerplate to single atomic-on-CHM, concise-on-HashMap calls.
  • removeIf(Predicate) on Collection — in-place filtered removal without manual iterator handling.
  • forEach(Consumer) default method on Iterable.
  • Collection.toArray(IntFunction) (Java 11+) — list.toArray(String[]::new), avoiding the old pre-sized-array idiom.
  • Stream.toList() (Java 16+) — shorthand for collect(Collectors.toList()), returns an unmodifiable list (subtle behavior difference architects should flag in code review — it’s not equivalent to the mutable list Collectors.toList() historically returned, and code relying on mutability after .toList() will break).