The Collections framework

The main interfaces

• List: ordered, allows duplicates. ArrayList, LinkedList.
• Set: no duplicates. HashSet (no order), LinkedHashSet (insertion order), TreeSet (sorted).
• Map: key → value. HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap.
• Queue/Deque: ArrayDeque (stack and queue), PriorityQueue (heap).

ArrayList vs LinkedList

In practice ArrayList wins almost always thanks to cache-friendly memory.

How HashMap works (asked in nearly every Java interview)

1. hashCode() of the key is computed and spread; the bucket index = hash & (capacity - 1).
2. Each bucket holds a linked list of entries; since Java 8, a bucket with more than 8 entries becomes a red-black tree (O(log n) worst case instead of O(n)).
3. get finds the bucket, then compares keys with equals.
4. When size exceeds capacity × load factor (0.75), the table doubles and entries are rehashed.
5. One null key is allowed (bucket 0). HashMap isn't thread-safe.

HashMap vs Hashtable vs ConcurrentHashMap: Hashtable is legacy and locks the whole table; ConcurrentHashMap allows concurrent reads and fine-grained locking for writes; neither allows null keys.

Comparable vs Comparator

record Job(String title, int salary) implements Comparable<Job> {
    public int compareTo(Job o) { return Integer.compare(salary, o.salary); }  // natural order
}
jobs.sort(Comparator.comparing(Job::title).thenComparing(Job::salary, Comparator.reverseOrder()));

Comparable defines one natural order inside the class; Comparator defines any number of orders outside it.

Fail-fast vs fail-safe iterators

Modifying an ArrayList while iterating it with a for-each loop throws ConcurrentModificationException (fail-fast). Use iterator.remove() or removeIf. Concurrent collections like CopyOnWriteArrayList iterate over a snapshot (fail-safe).

Check yourself

• Walk through what happens on map.put(key, value) in a HashMap.
• When would you use a TreeMap?
• Why does removing inside a for-each loop throw an exception?