Part 3: Collections & Generics

1. The Collection Framework at a Glance

Collection
├── List (ordered, allows duplicates)
│     ├── ArrayList   (resizable array — fast get, O(1) append)
│     └── LinkedList  (doubly linked — fast insert/remove at ends)
├── Set (no duplicates)
│     ├── HashSet     (hash-based, O(1), unordered)
│     ├── LinkedHashSet (insertion order)
│     └── TreeSet    (sorted, O(log n))
└── Queue / Deque
      └── ArrayDeque, PriorityQueue (heap)
Map
    ├── HashMap        (hash buckets, O(1) typical)
    ├── LinkedHashMap (insertion-order iteration)
    ├── TreeMap       (sorted by keys)
    └── Hashtable / ConcurrentHashMap (thread-safe)

Interview favourite — ArrayList vs LinkedList:

• ArrayList.get(i) — O(1); add at end amortized O(1).
• LinkedList.add/remove at head/tail — O(1) but O(n) if you need index lookup; each node allocates memory.
• Almost always, ArrayList wins for real workloads; “LinkedList is faster for insertions” is a half-truth — only at the ends.

2. HashSet vs TreeSet vs LinkedHashSet

• HashSet: unordered by hash. add, remove, contains — O(1) average. Requires equals/hashCode.
• TreeSet: Sorted — comparator/natural order, O(log n). Elements must be Comparable/provided a Comparator.
• LinkedHashSet: HashSet + doubly-linked chain to preserve insertion order.
• Iteration order: HashSet unspecified → LinkedHashSet insertion → TreeSet sorted.

3. HashMap Internals (most-asked collection question)

• Structure: array of buckets; each bucket is a linked list (treeified when a bucket reaches 8+ elements, JDK 8+ → red-black tree, untreeify below 6).
• Put: compute (h = key.hashCode()) ^ (h >>> 16) → index = (n - 1) & hash → insert or replace.
• Load factor (default 0.75): when size > capacity × 0.75 → resize doubles capacity (rehash).
• A bad hashCode (constant) collapses all entries into one bucket → O(n) degrades to worst case.
• key in HashMap and element in HashSet must implement equals/hashCode properly.

Gotcha: HashMap is not thread-safe. Concurrent writes → infinite loop in structural modification (legacy). Use ConcurrentHashMap (lock-striped, no global lock, weakly consistent iterators).

4. Iterators & fail-fast

• Fail-fast iterators: ArrayList/HashMap throw ConcurrentModificationException if the underlying collection is structurally modified during iteration (add/remove), detected via the modCount.
• Exceptions: size()/set() are not structural → allowed.
• Safe removal while iterating: iterator.remove(), or collect keys then remove after, or list.removeIf(predicate).
• ListIterator — bidirectional, can add/set during iteration.
• Weakly consistent iterators (ConcurrentHashMap/CopyOnWriteArrayList) — don’t throw, iterate a snapshot.

5. Comparable vs Comparator

• Comparable = natural ordering, implemented inside the class (compareTo).
• Comparator = external lambda/class passed to sort, no change to the domain class.

list.sort((a, b) -> a.age() - b.age());            // ascending
list.sort(Comparator.comparing(Person::age));      // key extractor
list.sort(Comparator.comparing(Person::age)
        .thenComparing(Person::name));             // chained

Must: return negative / zero / positive, and must be transitive for correct sorting.

6. Generics — Erasure is the key

• Type erasure: generics are compile-time only; List<String> and List<Integer> erase to the raw List at runtime. You cannot check generic type with instanceof.
• Wildcards:
  • ? extends T — producer; read ok, write impossible.
  • ? super T — consumer; write ok, read as Object.
• PECS mnemonic: Producer Extends, Consumer Super.
• T extends Comparable etc. bound the type parameter.
• Raw types bypass safety — avoid; they exist only for legacy compat.
• Cannot do: instantiate new T() (no runtime type), new T[], static field T (not type-erased), primitive type args (List<int> illegal → use List<Integer>).

Gotcha: Arrays.asList("a","b").add("c") throws UnsupportedOperationException — the returned list has fixed size backed by the array.