12.1 The Hierarchy at a Glance

Iterable -> Collection -> List  : ArrayList, LinkedList, Vector, Stack
                       -> Set   : HashSet, LinkedHashSet, TreeSet (SortedSet)
                       -> Queue : PriorityQueue, ArrayDeque
Map (separate root!)            : HashMap, LinkedHashMap, TreeMap, Hashtable

Trap: Map does not extend Collection — it is a parallel hierarchy of key→value pairs. Rules of thumb: List = ordered + duplicates; Set = no duplicates; Map = unique keys.

12.2 ArrayList vs LinkedList

Default choice: ArrayList. Vector/Hashtable are legacy synchronized versions — mention them only as "thread-safe but obsolete; use Collections.synchronizedList or concurrent collections instead."

12.3 HashMap Internals — The 10-Mark Advanced Question

A HashMap is an array of buckets (default capacity 16). For put(k, v):

1. Compute h = k.hashCode(), then spread it: h ^ (h >>> 16) (mixes high bits into low).
2. Bucket index = h & (capacity − 1) — works because capacity is always a power of two.
3. Empty bucket → place a new node. Collision → walk the chain comparing with equals(); replace value if a matching key exists, else append.
4. When one bucket's chain exceeds 8 nodes (and capacity ≥ 64), it converts to a red-black tree — worst-case lookup improves O(n) → O(log n). (Java 8 change.)
5. When size > capacity × loadFactor (default 0.75), the table doubles and all entries rehash.

This is why the equals/hashCode contract matters: equal keys must land in the same bucket. One null key is allowed (bucket 0); HashMap is unordered, LinkedHashMap keeps insertion order, TreeMap keeps keys sorted (O(log n), no null key).

12.4 Iterator & Fail-Fast Behaviour

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));
Iterator<Integer> it = nums.iterator();
while (it.hasNext())
    if (it.next() % 2 == 0) it.remove();       // SAFE removal during iteration
// nums.remove(...) inside the loop => ConcurrentModificationException

Collection iterators are fail-fast: structural modification outside the iterator trips a modCount check and throws ConcurrentModificationException. ListIterator additionally walks backwards and supports add/set.

12.5 Comparable vs Comparator

Modern Comparator building: Comparator.comparing(Student::getMarks).reversed().thenComparing(Student::getName) — write this fluently and examiners are impressed.

12.6 Generics — Compile-Time Type Safety

Generics move type errors from runtime to compile time: List<String> refuses an Integer, and no cast is needed on get. Key facts:

• Type erasure: generic types are erased at compile time — at runtime a List<String> and List<Integer> are the same class, so new T(), T[] and instanceof List<String> are illegal.
• Bounded types: <T extends Number>; wildcards: <?> unknown, <? extends T> read-only producer, <? super T> consumer (PECS — Producer Extends, Consumer Super).
• List<Object> is not a supertype of List<String> (generics are invariant).
• Autoboxing bridges primitives ↔ wrappers when storing int into List<Integer>; beware the Integer cache: Integer a = 127, b = 127; a == b is true, but with 128 it is false.

🎯 Exam Focus

1. Draw the Collections Framework hierarchy. Why is Map not a Collection?
2. Compare ArrayList and LinkedList (structure, complexity of get/insert, memory). When is each preferred?
3. Explain the internal working of HashMap: hashing, index calculation, collision handling, treeification threshold and load factor.
4. What is a fail-fast iterator? Show code that causes ConcurrentModificationException and its correct fix.
5. Differentiate Comparable and Comparator. Write a program sorting Students by marks descending, then by name.
6. What is type erasure in generics? Explain PECS with one example each.