Collection
├── List          (ordered, duplicates allowed)
│   ├── ArrayList
│   ├── LinkedList
│   ├── Vector (legacy)
│   └── CopyOnWriteArrayList
├── Set           (no duplicates)
│   ├── HashSet
│   ├── LinkedHashSet
│   ├── TreeSet
│   └── CopyOnWriteArraySet
└── Queue / Deque
    ├── ArrayDeque
    ├── LinkedList
    ├── PriorityQueue
    └── BlockingQueue implementations

Map               (key-value, separate hierarchy)
├── HashMap
├── LinkedHashMap
├── TreeMap
├── Hashtable (legacy)
├── ConcurrentHashMap
└── EnumMap

// ArrayList growth: capacity → 10 → 15 → 22 → 33 → ...
ArrayList<String> list = new ArrayList<>(); // capacity: 10
ArrayList<String> presized = new ArrayList<>(1000); // avoids 7 reallocations

Memory layout:
┌───┬───┬───┬───┬───┬─────────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ (empty) │
└───┴───┴───┴───┴───┴─────────┘
  ↑ contiguous, cache-friendly

Memory layout:
┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│ prev │ item  │ ──► │ prev │ item  │ ──► │ prev │ item  │
│ next │       │ ◄── │ next │       │ ◄── │ next │       │
└──────────────┘     └──────────────┘     └──────────────┘
  ↑ scattered in heap, cache-unfriendly

// Almost always correct
List<String> items = new ArrayList<>();

// Only for queue/deque operations
Deque<String> queue = new ArrayDeque<>();

// Rarely correct
List<String> items = new LinkedList<>(); // ← usually a mistake

index = (n - 1) & hash(key)
// where n = number of buckets (always power of 2)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Bucket array:
[0] → null
[1] → Entry(k1) → Entry(k2) → null       (chain)
[2] → TreeNode(k3) ← TreeNode(k4) → ...  (treeified at ≥8 entries)
[3] → Entry(k5)

// Default: resizes at 12 entries, then 24, 48, 96...
HashMap<String, Integer> map = new HashMap<>();

// Pre-size to avoid rehashing: initialCapacity = expectedSize / 0.75 + 1
HashMap<String, Integer> optimized = new HashMap<>((int)(expectedSize / 0.75) + 1);

// Example: expecting 1000 entries
HashMap<String, Integer> presized = new HashMap<>(1334);

// HashMap: O(1) get/put, no ordering guarantee
Map<String, User> byId = new HashMap<>();

// LinkedHashMap: O(1) get/put, insertion-order iteration
// Use for: LRU cache, preserving insertion order in JSON output
Map<String, User> ordered = new LinkedHashMap<>();

// LRU cache using LinkedHashMap
Map<String, User> lruCache = new LinkedHashMap<>(100, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, User> eldest) {
        return size() > 100;
    }
};

// TreeMap: O(log n) get/put, sorted by key natural order or Comparator
// Use for: sorted iteration, range queries, ceiling/floor/subMap
TreeMap<String, User> sorted = new TreeMap<>();
String firstKey = sorted.firstKey();
Map<String, User> range = sorted.subMap("a", "m"); // keys between "a" and "m"

// HashSet: O(1) add/contains/remove, no order
Set<String> ids = new HashSet<>();

// LinkedHashSet: O(1), insertion order preserved
Set<String> ordered = new LinkedHashSet<>();

// TreeSet: O(log n), sorted order, supports floor/ceiling/subSet
TreeSet<String> sorted = new TreeSet<>();
String justBelow = sorted.floor("target"); // greatest element ≤ "target"
Set<String> tail = sorted.tailSet("m");    // all elements ≥ "m"

// ArrayDeque: resizable array, faster than LinkedList for queue operations
// Use as: Stack (push/pop), Queue (offer/poll), Deque
Deque<String> stack = new ArrayDeque<>();
stack.push("first");
String top = stack.pop();

Queue<String> queue = new ArrayDeque<>();
queue.offer("task");
String next = queue.poll(); // null if empty, unlike remove()

// PriorityQueue: min-heap, O(log n) add/poll, O(1) peek
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Custom priority
PriorityQueue<Task> byDeadline = new PriorityQueue<>(
    Comparator.comparing(Task::getDeadline)
);

// Wrong: synchronized wrapper still requires external sync for compound ops
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
// This check-then-act is still a race condition:
if (!syncList.contains(item)) {
    syncList.add(item); // ❌ not atomic
}

// CopyOnWriteArrayList: write creates a new array copy
// Read (including iteration) is lock-free — reads never block
// Use when: reads >> writes (observer lists, routing tables)
List<String> listeners = new CopyOnWriteArrayList<>();

// ConcurrentHashMap: segment-level locking (Java 8+: CAS on buckets)
// putIfAbsent, compute, merge are atomic
ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
counts.merge(word, 1, Integer::sum); // atomic increment
counts.computeIfAbsent(key, k -> new ArrayList<>()).add(value);

// ConcurrentSkipListMap: sorted, concurrent, O(log n)
// Use when you need TreeMap + thread safety
ConcurrentNavigableMap<String, User> concurrent = new ConcurrentSkipListMap<>();

// BlockingQueue: producer-consumer with blocking semantics
BlockingQueue<Task> workQueue = new LinkedBlockingQueue<>(1000);
workQueue.put(task);    // blocks if full
Task t = workQueue.take(); // blocks if empty

// ArrayBlockingQueue: bounded, uses single lock
BlockingQueue<String> bounded = new ArrayBlockingQueue<>(100);

// Manual (pre-Java 7)
public class Point {
    private final int x, y;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y); // combines fields correctly
    }
}

// Java 16+ record: equals, hashCode, toString generated automatically
record Point(int x, int y) {}

// Common mistake: mutable field in hashCode
// Once put in a HashMap, mutating the key makes it "lost"
public class MutableKey {
    public String value; // ← mutable
    
    @Override
    public int hashCode() { return value.hashCode(); } // ← danger
}

// Sorting
List<Integer> nums = new ArrayList<>(List.of(3, 1, 4, 1, 5));
Collections.sort(nums);                          // natural order
nums.sort(Comparator.reverseOrder());            // reverse
nums.sort(Comparator.comparingInt(Math::abs));   // custom

// Searching (requires sorted list)
int idx = Collections.binarySearch(nums, 4);    // O(log n)

// Immutable views (modifications throw UnsupportedOperationException)
List<String> fixed = List.of("a", "b", "c");          // Java 9+
Map<String, Integer> fixedMap = Map.of("k1", 1, "k2", 2);
Set<String> fixedSet = Set.copyOf(existingSet);

// Frequency, disjoint, min, max
int count = Collections.frequency(list, "target");
boolean noOverlap = Collections.disjoint(listA, listB);
String max = Collections.max(list, Comparator.naturalOrder());

// Shuffle, fill, copy, reverse
Collections.shuffle(list);
Collections.fill(list, "default");
Collections.reverse(list);
Collections.rotate(list, 3); // rotate right by 3 positions

Need a list?
  → Default: ArrayList
  → Need O(1) add/remove at both ends: ArrayDeque
  → Thread-safe, reads dominate: CopyOnWriteArrayList
  → LinkedList: almost never

Need a set?
  → Default: HashSet
  → Need insertion order: LinkedHashSet
  → Need sorting/range queries: TreeSet

Need a map?
  → Default: HashMap (pre-size if you know count)
  → Need insertion order: LinkedHashMap
  → Need sorted keys/range queries: TreeMap
  → Enum keys: EnumMap
  → Thread-safe: ConcurrentHashMap

Need a queue?
  → Stack: ArrayDeque
  → FIFO queue: ArrayDeque
  → Priority: PriorityQueue
  → Thread-safe producer-consumer: LinkedBlockingQueue or ArrayBlockingQueue