# Collections Framework

## 1. The Core Hierarchy

Almost every collection type implements one of three root interfaces: `Collection` (lists, sets, queues), `Map` (key-value pairs — notably NOT a `Collection`), and their shared iteration contract.

```
Iterable<E>
  └── Collection<E>
        ├── List<E>     — ordered, indexable, duplicates allowed   (ArrayList, LinkedList)
        ├── Set<E>       — no duplicates                            (HashSet, LinkedHashSet, TreeSet)
        └── Queue<E>      — FIFO/priority access                    (ArrayDeque, PriorityQueue)

Map<K, V>                — key-value pairs, NOT a Collection        (HashMap, LinkedHashMap, TreeMap)
```

```java
List<String> names = new ArrayList<>();
Set<Integer> uniqueIds = new HashSet<>();
Map<String, Integer> ages = new HashMap<>();
```

## 2. `List`: `ArrayList` vs `LinkedList`

| Operation | `ArrayList` | `LinkedList` |
|---|---|---|
| `get(index)` | O(1) — direct array index | O(n) — walks the list from the nearer end |
| `add(end)` | amortized O(1) | O(1) |
| `add(index)` / `remove(index)` | O(n) — shifts elements | O(1) once positioned, O(n) to get there |
| Memory | one contiguous backing array | one node object (with 2 references) per element |
| Cache locality | good — contiguous memory | poor — nodes scattered on the heap |

In practice, `ArrayList` is the default choice almost always; `LinkedList` only wins for workloads dominated by insert/remove at both ends combined with never doing random-access `get`, and even then `ArrayDeque` usually beats it as a double-ended queue.

```java
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(0, 5);      // insert at index 0 — shifts everything right
list.remove(Integer.valueOf(20)); // removes the VALUE 20, not index 20 — overload ambiguity trap
```

## 3. `Set`: `HashSet` vs `LinkedHashSet` vs `TreeSet`

```java
Set<String> hash = new HashSet<>();        // no order guarantee at all
Set<String> linked = new LinkedHashSet<>(); // preserves INSERTION order
Set<String> sorted = new TreeSet<>();        // always kept in SORTED order (needs Comparable or a Comparator)

hash.add("banana"); hash.add("apple"); hash.add("cherry");
// iteration order of `hash` is unspecified and can differ across runs/JVMs

sorted.addAll(hash);
System.out.println(sorted); // [apple, banana, cherry] — always sorted
```

## 4. `Map`: `HashMap` vs `LinkedHashMap` vs `TreeMap`

Same ordering trade-off as `Set` (unsurprising — `HashSet` is literally backed by a `HashMap` internally with dummy values).

```java
Map<String, Integer> scores = new HashMap<>();
scores.put("Ada", 100);
scores.merge("Ada", 5, Integer::sum);        // Ada -> 105, functional update-or-insert
scores.computeIfAbsent("Grace", k -> 0);       // insert 0 only if key absent
scores.getOrDefault("Missing", -1);              // -1, no NullPointerException
```

## 5. `Comparable` vs `Comparator`

`Comparable<T>` is implemented **by the element type itself** to define one natural ordering; `Comparator<T>` is an external, swappable strategy — you can have as many as you like without touching the element class.

```java
class Person implements Comparable<Person> {
    String name; int age;
    Person(String name, int age) { this.name = name; this.age = age; }

    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age); // natural order: by age
    }
}

List<Person> people = new ArrayList<>(List.of(new Person("Bob", 30), new Person("Ana", 25)));
Collections.sort(people); // uses compareTo — natural order (by age)

people.sort(Comparator.comparing((Person p) -> p.name));         // external, by name
people.sort(Comparator.comparingInt((Person p) -> p.age).reversed()); // chainable, reversed
```

## 6. Iteration and Fail-Fast Behavior

Modifying most collections while iterating over them with a `for-each` loop (which uses an `Iterator` under the hood) throws `ConcurrentModificationException` — even in single-threaded code.

```java
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer n : nums) {
    if (n == 2) nums.remove(n); // ConcurrentModificationException on the NEXT iteration
}

// Correct: use the Iterator's own removal method
Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    if (it.next() == 2) it.remove(); // safe — the iterator tracks the removal itself
}
```

## 7. Immutable and Unmodifiable Collections

```java
List<String> immutable = List.of("a", "b", "c");         // truly immutable, fixed size
immutable.add("d"); // UnsupportedOperationException

List<String> mutable = new ArrayList<>(List.of("a", "b"));
List<String> view = Collections.unmodifiableList(mutable); // a VIEW — blocks writes THROUGH view...
mutable.add("c");                                            // ...but the underlying list can still change
System.out.println(view); // [a, b, c] — the view reflects the mutation
```

![A HashMap's table array holds buckets; each bucket is a linked list of entries until it grows past the treeify threshold, at which point that one bucket becomes a red-black tree](diagrams/01-hashmap-buckets.svg)

## Under the Hood

**`ArrayList` grows by 1.5x, not doubling, and copies the whole backing array on resize.** Internally it wraps a plain `Object[]`. On overflow, `ArrayList.grow()` computes `newCapacity = oldCapacity + (oldCapacity >> 1)` (old capacity plus half of itself — a 1.5x growth factor, not the 2x some other languages use) and copies every element into the new array via `System.arraycopy` (a JVM intrinsic, typically compiled to a highly optimized bulk memory copy rather than a per-element Java loop). This is why appending to an `ArrayList` is *amortized* O(1) — most appends are a cheap array write, but occasionally one append triggers an O(n) full copy, averaging out over many operations.

**`HashMap` is an array of buckets, and Java 8 added a real fallback data structure per bucket.** The backing store is `Node<K,V>[] table`, sized to a power of two. `hashCode()` on the key isn't used directly as the bucket index — HashMap runs it through a **spreading function**, `h ^ (h >>> 16)` (XOR the hash with itself shifted right 16 bits), to fold the high bits into the low bits before masking with `(table.length - 1)`, which meaningfully reduces collisions for hash codes that vary mostly in their high bits. Each bucket starts as a simple **linked list** of entries with the same post-spread hash bucket index. Since **Java 8**, if a single bucket's chain grows to `TREEIFY_THRESHOLD` (8) entries *and* the table itself has at least `MIN_TREEIFY_CAPACITY` (64) buckets, that one bucket is converted into a **red-black tree**, changing worst-case lookup in that bucket from O(n) to O(log n) — a defense specifically against hash-flooding (many keys colliding into the same bucket, whether by bad luck or a hostile `hashCode()`). If entries are later removed and the bucket shrinks back to `UNTREEIFY_THRESHOLD` (6), it's converted back to a plain list during a resize. The **default load factor is 0.75** — the table resizes (doubling capacity) once the number of entries exceeds `capacity * loadFactor`, trading some extra empty bucket space for keeping average chain length short.

**`HashSet` is a thin wrapper around `HashMap`.** Every element you add becomes a key in a private, backing `HashMap<E, Object>`, mapped to a single shared dummy sentinel value (`PRESENT`) — there is no independent `HashSet` storage implementation; `add`, `contains`, and `remove` all delegate straight to the map's key operations.

**Fail-fast iteration is implemented with a `modCount` counter, not real concurrency detection.** Every structural modification (add/remove, not element replacement via `set`) increments an internal `modCount` field on the collection. Each `Iterator` snapshots `modCount` when created and re-checks it on every `next()`/`remove()` call; a mismatch throws `ConcurrentModificationException`. This is a best-effort heuristic, not a guarantee — it exists to catch bugs early, not to provide thread safety, and it can still miss some modification patterns or produce false negatives under genuine concurrent access.

## Common Pitfalls

1. **Modifying a collection while iterating it with `for-each`** — throws `ConcurrentModificationException`; use `Iterator.remove()`, a `removeIf(predicate)`, or collect indices/elements to remove into a separate list first.
2. **Using a mutable object as a `HashMap`/`HashSet` key and then mutating it after insertion** — changes the key's `hashCode()`, so the entry becomes unreachable at its original bucket; the entry effectively "disappears" from lookups even though it's still physically in the table.
3. **Not overriding `equals`/`hashCode` on a custom key/element class** — falls back to `Object`'s reference-identity versions, so two logically-equal objects are treated as different keys/elements (see the Inheritance and Polymorphism topic's contract discussion).
4. **`list.remove(int)` vs `list.remove(Object)` overload ambiguity** — `list.remove(5)` on a `List<Integer>` removes the element **at index 5**, not the value `5`; use `list.remove(Integer.valueOf(5))` to remove by value.
5. **Assuming `HashMap`/`HashSet` iteration order is meaningful or stable** — it depends on hash spreading and current bucket layout, and can change across JVM versions or even after a resize on the same run; use `LinkedHashMap`/`LinkedHashSet` (insertion order) or `TreeMap`/`TreeSet` (sorted order) when order matters.

## Quick Reference

```java
List<T>  new ArrayList<>()     // fast random access, default choice
         new LinkedList<>()     // rarely the right call — ArrayDeque usually better

Set<T>   new HashSet<>()        // no order
         new LinkedHashSet<>()  // insertion order
         new TreeSet<>()         // sorted order (Comparable/Comparator)

Map<K,V> new HashMap<>()        // no order, O(1) average get/put
         new LinkedHashMap<>()  // insertion order
         new TreeMap<>()         // sorted by key

map.getOrDefault(k, def)
map.computeIfAbsent(k, fn)
map.merge(k, v, BiFunction)

list.sort(Comparator.comparing(x -> x.field).reversed().thenComparing(...));

Iterator<T> it = list.iterator();
while (it.hasNext()) { T v = it.next(); if (cond) it.remove(); } // safe removal during iteration

List.of(...); Set.of(...); Map.of(k, v, ...); // truly immutable factories
```