Collections Framework

Both drive sorting/ordering, but from different places:

• Comparable<T>: implemented by the class being sorted, defining its single "natural" ordering via int compareTo(T other). Used by Collections.sort(list) / Arrays.sort(arr) with no extra argument, and by sorted collections (TreeSet, TreeMap) by default.

class Employee implements Comparable<Employee> {
    int salary;
    public int compareTo(Employee other) { return Integer.compare(salary, other.salary); }
}
Collections.sort(employees); // uses compareTo

• Comparator<T>: a separate object (often a lambda or method reference) representing one specific ordering strategy, passed explicitly where needed. A class can have unlimited comparators, including ones defined outside the class entirely — useful for sorting classes you don't own, or supporting multiple orderings.

Comparator<Employee> byName = Comparator.comparing(e -> e.name);
Comparator<Employee> bySalaryDesc = Comparator.comparingInt((Employee e) -> e.salary).reversed();
employees.sort(byName.thenComparing(bySalaryDesc));

Rule of thumb: implement Comparable for the one obvious, canonical ordering of a type (e.g., Integer's natural numeric order); use Comparator for anything situational, alternative, or external to the class.

Both let you traverse a collection safely (i.e., without triggering a ConcurrentModificationException from structural changes made outside the iterator), but ListIterator is strictly more capable — and only available on Lists:

List<String> names = new ArrayList<>(List.of("a", "b", "c"));
ListIterator<String> it = names.listIterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("b")) it.set("B"); // safe in-place modification
}

Both are the safe way to remove/modify elements while iterating — calling list.remove(x) directly inside a for-each loop throws ConcurrentModificationException; calling iterator.remove() (or listIterator.set/add) is explicitly supported because the iterator updates its own internal state to match.

Fail-fast iterators (the default for ArrayList, HashMap, HashSet, LinkedList, etc.) track a modCount field that's incremented on every structural modification (add/remove, not just changing an existing element's value). Each iterator call (next(), etc.) checks the current modCount against the value captured when the iterator was created; a mismatch throws ConcurrentModificationException immediately:

List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
    if (s.equals("b")) list.remove(s); // throws ConcurrentModificationException
}

This is a best-effort detection mechanism meant to catch bugs early, not a hard guarantee — the JavaDoc explicitly warns it shouldn't be relied on for correctness (a modification could, in rare cases, go undetected).

Fail-safe (better termed "weakly consistent") iterators don't throw at all. CopyOnWriteArrayList iterates over an immutable snapshot of the array taken when the iterator was created — concurrent writes go to a new copy, so the iterator never sees them and never throws, but also never reflects the update. ConcurrentHashMap's iterator similarly tolerates concurrent modification, reflecting some but not necessarily all concurrent changes, again without throwing.

Practical takeaway: use iterator.remove()/listIterator methods to modify safely during iteration on fail-fast collections, or reach for a concurrent collection when multiple threads genuinely need to read and write at the same time.

• Queue<E>: models FIFO (first-in-first-out) processing with offer(e)/poll()/peek() (non-throwing) and add(e)/remove()/element() (throwing variants for full/empty cases).
• Deque<E> ("double-ended queue"): extends the queue concept to both ends — addFirst/addLast, removeFirst/removeLast, peekFirst/peekLast. Because of this, a Deque can act as either a FIFO queue (add at one end, remove from the other) or a LIFO stack (add/remove from the same end via push/pop), which is why ArrayDeque is the JDK-recommended replacement for the legacy, synchronized Stack class.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);
stack.pop(); // 2 — LIFO

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
queue.poll(); // 1 — FIFO

• PriorityQueue<E>: a Queue implementation backed by a binary heap, where poll()/peek() always return the smallest element per natural ordering (Comparable) or a supplied Comparator — not insertion order. Insertion is O(log n); it's the standard structure behind algorithms like Dijkstra's shortest path or "top-K" problems.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.addAll(List.of(5, 1, 3));
minHeap.poll(); // 1 — smallest first, regardless of insertion order

Note PriorityQueue is not a Deque — it only supports removal from the "front" (highest priority), and its iterator makes no ordering guarantee at all.

There are two distinct approaches, and they behave differently:

1. List.of(...), Set.of(...), Map.of(...) (Java 9+): create genuinely immutable collections. Any mutation attempt (add, remove, set) throws UnsupportedOperationException, and they reject null elements/keys/values outright (throwing NullPointerException at creation time).

List<String> l = List.of("a", "b", "c");
l.add("d"); // UnsupportedOperationException
List.of("a", null); // NullPointerException immediately

2. Collections.unmodifiableList(list) (and unmodifiableSet, unmodifiableMap, ...): wraps an existing mutable collection in a read-only view. The view itself rejects direct mutation, but it is not truly immutable — if code still holds a reference to the original mutable list and modifies it, those changes are visible through the wrapper, since it's just a thin delegating façade, not a copy.

List<String> mutable = new ArrayList<>(List.of("a", "b"));
List<String> view = Collections.unmodifiableList(mutable);
mutable.add("c");
view.get(2); // "c" — the wrapper sees the underlying change

Rule of thumb: prefer List.of()/Set.of()/Map.of() for genuinely fixed data (constants, defensive copies to hand out to callers); use Collections.unmodifiableX mainly when you need to expose a read-only view over a collection you still intend to mutate internally.

Both are static-method-only utility classes in java.util, mirroring similar operations for two different data structures:

• Arrays: operates on plain Java arrays (int[], String[], etc.) — Arrays.sort(arr), Arrays.binarySearch(arr, key), Arrays.fill(arr, val), Arrays.equals(a, b) (element-wise, unlike ==), Arrays.copyOf(arr, newLength), and Arrays.asList(arr) (returns a fixed-size List view backed by the array — its size can't change, though existing elements can be set).
• Collections: operates on Collection/List/Set/Map objects — Collections.sort(list), Collections.binarySearch(list, key), Collections.max(coll)/min(coll), Collections.shuffle(list), Collections.unmodifiableList(list), Collections.synchronizedList(list), and factory helpers like Collections.emptyList()/singletonList(x).

int[] nums = {3, 1, 2};
Arrays.sort(nums);                     // arrays

List<Integer> list = new ArrayList<>(List.of(3, 1, 2));
Collections.sort(list);                // collections

A common gotcha: Arrays.asList(arr) returns a fixed-size list backed directly by the array — calling .add()/.remove() on it throws UnsupportedOperationException, and mutating an element through the list writes back into the original array. To get a fully independent, resizable list, wrap it: new ArrayList<>(Arrays.asList(arr)).

A hash collision happens when two different keys map to the same bucket index. HashMap has always handled this by chaining multiple entries in the same bucket:

Pre-Java 8: each bucket was a simple singly-linked list of entries. Looking up a key meant walking the list and calling equals() on each entry — worst case O(n) if many keys collided into one bucket. This could be forced adversarially, for example with crafted String keys sharing the same hashCode(), as a denial-of-service vector.

Java 8+ (treeification): if a single bucket's chain grows beyond TREEIFY_THRESHOLD (8 entries) and the table itself has at least MIN_TREEIFY_CAPACITY (64) buckets, that bucket's linked list converts into a red-black tree, keyed by hash code (and, if comparable, natural ordering as a tiebreaker). This bounds worst-case lookup within that bucket to O(log n) instead of O(n).

If the table is too small (fewer than 64 buckets), a busy bucket triggers a resize (doubling capacity) instead of treeification — a small table just needs its collisions spread across more buckets, not a smarter per-bucket structure.

If entries are later removed and a treeified bucket shrinks below UNTREEIFY_THRESHOLD (6), it converts back to a plain linked list, since the tree's extra memory overhead isn't worth it for a small bucket.

This change specifically hardens HashMap against algorithmic-complexity attacks, where an attacker supplies many keys engineered to collide, without changing the map's average-case O(1) behavior for well-distributed keys.