7. The Collections Framework

Almost every program has to hold a group of things, and an array is rarely the right shape for the job: it cannot grow, it cannot answer "do you already contain this?", and it has no notion of keys. The Collections Framework is the standard library's answer, a small set of interfaces that describe what a group of objects can do and a larger set of classes that implement them with different performance trade-offs. This chapter covers the interfaces you should declare against, the implementations you should instantiate, and the operations that tie them together, all of it resting on the generics rules from chapter 6.

<a id="71-collection-interfaces"></a>

7.1 Collection Interfaces

This subchapter covers the contracts at the top of the framework: what each interface promises, how they relate to one another, and how iteration works.

The Collection Hierarchy Overview

Suppose you write a method that prints every element of a group. If you declare its parameter as ArrayList<String>, it will not accept a HashSet<String>, a LinkedList<String>, or anything else, even though printing works identically for all of them. The method has been welded to one particular storage strategy for no reason.

The framework solves this by separating two questions that beginners tend to merge:

• What can this group do? Answered by an interface: List, Set, Queue, Map.
• How does it do it, and how fast? Answered by an implementation class: ArrayList, HashSet, ArrayDeque, HashMap.

The practical rule that follows is program to the interface: declare variables, parameters, and return types with the interface, and name a concrete class only at the single point where you create the object.

// Declare the CAPABILITY, instantiate the STRATEGY
List<String> names = new ArrayList<>();

// This method now accepts ArrayList, LinkedList, List.of(...), anything
public static void printAll(Collection<String> items) {
    for (String item : items) {
        System.out.println(item);
    }
}

Swapping new ArrayList<>() for new LinkedList<>() later becomes a one-line change instead of a refactor, because nothing downstream ever named the class.

The hierarchy itself has two roots that are often mistaken for one:

                   Iterable<E>                        Map<K, V>
                        |                           (NOT a Collection)
                   Collection<E>                          |
         ___________|________|____________         _______|________
        |           |                     |       |       |        |
     List<E>      Set<E>               Queue<E>  HashMap LinkedHashMap
        |           |                     |              TreeMap
   ArrayList    HashSet              ArrayDeque          (SortedMap
   LinkedList   LinkedHashSet        PriorityQueue        -> NavigableMap)
   (Vector)     TreeSet                  |
                (SortedSet            Deque<E>
                 -> NavigableSet)      ArrayDeque
                                       LinkedList

Map is deliberately outside Collection. A Collection holds single elements and Map holds pairs, so add(E) would be meaningless on it. Maps are still part of the framework and expose their contents as collections through keySet(), values(), and entrySet().

Iterable<E> sits above everything and declares exactly one abstract method, iterator(). That single method is what makes the enhanced for loop work, and implementing it is all a custom class needs to be loopable.

Collection<E> adds the operations shared by every group of elements:

Method	Meaning
add(E e)	Insert; returns whether the collection changed
remove(Object o)	Remove one matching element, if present
contains(Object o)	Membership test, using equals
size(), isEmpty()	How many elements
clear()	Remove everything
iterator()	Inherited from Iterable
stream()	Bridge to the Stream API of chapter 8

Note that remove and contains take Object, not E. That is a historical wart kept for backwards compatibility, and it means list.remove("typo") on a List<Integer> compiles silently and does nothing. It is worth remembering when a removal mysteriously has no effect.

Key Takeaways

• Interfaces describe capability, implementation classes describe strategy and performance.
• Declare with the interface and instantiate the class only at the creation site.
• Iterable provides iterator(), which is what powers the enhanced for loop.
• Collection is the common parent of List, Set, and Queue.
• Map is not a Collection, because it stores pairs rather than single elements.
• contains and remove accept Object, so a wrong-typed argument compiles but never matches.

🧪 Practice

1. Write a method int countNonNull(Collection<?> items) and call it with an ArrayList, a HashSet, and a TreeSet.
2. Declare a variable as ArrayList<String>, pass it to a method expecting List<String>, then try the reverse and read the compiler error.
3. Interview: Why is Map not a subinterface of Collection? (Hint: what would the single-argument add(E) method mean for a map?)

List, Set, and Queue Contracts

The three Collection subinterfaces differ in one thing each: what they promise about order and duplicates. Choosing between them is a modelling decision, not a performance one, and getting it right removes whole classes of bug.

A List is an ordered sequence with integer positions. Duplicates are allowed, insertion order is preserved, and every element has an index. Think of a numbered shopping list: item 3 stays item 3, and "milk" may appear twice.

List<String> tasks = new ArrayList<>();
tasks.add("write");
tasks.add("review");
tasks.add("write");              // duplicates are fine

System.out.println(tasks.get(1));      // "review": positional access
tasks.add(1, "plan");                  // insert AT an index, shifting the rest
System.out.println(tasks.indexOf("write"));  // 0: first occurrence only
System.out.println(tasks);             // [write, plan, review, write]

Methods unique to List are the index-based ones: get(int), set(int, E), add(int, E), remove(int), indexOf, subList, and sort.

A Set is a collection with no duplicates. Adding an element that is already present does nothing and returns false. There is no index, because most sets have no meaningful position. Think of the set of tags on an article: asking for "the third tag" is not a question the model supports.

Set<String> tags = new HashSet<>();
System.out.println(tags.add("java"));   // true:  actually added
System.out.println(tags.add("java"));   // false: already present, no change
tags.add("collections");
System.out.println(tags.size());        // 2
// tags.get(0);                         // ERROR: no such method on Set

"Duplicate" here means equals returned true, which is why the hashing rules later in this chapter matter so much for custom element types.

A Queue holds elements for processing in a defined order, normally first-in-first-out. Its distinctive feature is that each operation comes in two flavours: one that throws on failure and one that returns a special value. In code that must not crash on an empty queue, the second family is the one you want.

Operation	Throws on failure	Returns special value
Insert	add(e)	offer(e) -> false
Remove	remove()	poll() -> null
Examine	element()	peek() -> null

Queue<String> jobs = new ArrayDeque<>();
jobs.offer("first");
jobs.offer("second");

System.out.println(jobs.peek());   // "first": look without removing
System.out.println(jobs.poll());   // "first": look AND remove
System.out.println(jobs.poll());   // "second"
System.out.println(jobs.poll());   // null: empty, but no exception

A Deque ("double-ended queue", pronounced "deck") extends Queue and allows insertion and removal at both ends, which makes it usable as a queue and as a stack at once:

  addFirst / offerFirst            addLast / offerLast
          |                                |
          v                                v
        [ A ][ B ][ C ][ D ]
          ^                                ^
          |                                |
  removeFirst / pollFirst          removeLast / pollLast

Summarising the three contracts:

Interface	Duplicates	Ordered	Positional access
List	Yes	By insertion index	Yes, get(int)
Set	No	Implementation-dependent	No
Queue	Yes	By processing order	No, ends only

Key Takeaways

• Pick the interface that matches the meaning of your data, then worry about speed.
• List keeps insertion order, permits duplicates, and supports indices.
• Set rejects duplicates as defined by equals, and has no indices.
• Queue offers a throwing family (add/remove/element) and a returning family (offer/poll/peek).
• Deque extends Queue with operations at both ends, serving as both queue and stack.

🧪 Practice

1. Add the same three strings to an ArrayList and a HashSet, print both sizes, and explain the difference.
2. Use an ArrayDeque to reverse a sentence by pushing each word with addFirst and then draining it.
3. Interview: When would offer return false rather than throwing? (Hint: think about a queue created with a fixed capacity.)

The Map Interface Family

A Map<K, V> associates unique keys with values. It is the right model whenever your data answers a lookup question: username to account, product code to price, word to count. Scanning a list to find a matching element is a linear search; a hash-based map answers the same question in effectively constant time.

Keys form a set, so each key appears at most once. Values are unconstrained and may repeat.

   KEYS (unique)          VALUES (may repeat)
   +-----------+          +--------+
   | "alice"   | -------> | 30     |
   | "bob"     | -------> | 25     |
   | "carol"   | -------> | 30     |   <- same value, different key: fine
   +-----------+          +--------+

The core operations:

Map<String, Integer> ages = new HashMap<>();

ages.put("alice", 30);
Integer previous = ages.put("alice", 31);  // REPLACES; returns the old value 30

System.out.println(ages.get("alice"));     // 31
System.out.println(ages.get("nobody"));    // null: absent, not an exception
System.out.println(ages.containsKey("bob"));   // false
System.out.println(ages.remove("alice"));  // 31: returns what was removed

Because get returns null for a missing key, a map holding null values is ambiguous: you cannot tell "absent" from "present but null" without calling containsKey. Avoid storing null values, and prefer the defaulting methods below.

Those defaulting methods, added in Java 8, remove most of the boilerplate around "check, then act":

Map<String, Integer> counts = new HashMap<>();

// Read with a fallback, without writing anything
int n = counts.getOrDefault("java", 0);

// Insert only if the key is currently absent
counts.putIfAbsent("java", 1);

// Compute a new value from the old one; the classic counter idiom
counts.merge("java", 1, Integer::sum);     // absent -> 1, present -> old + 1

// Build a value lazily, only when the key is missing
Map<String, List<String>> index = new HashMap<>();
index.computeIfAbsent("j", k -> new ArrayList<>()).add("java");

merge and computeIfAbsent are worth memorising: the first is the standard way to count occurrences, the second the standard way to build a multi-valued map without a null check on every insert.

A map exposes its contents as three collection views. A view is not a copy; it is a window onto the same data, so changes flow both ways.

View	Type	Contains
keySet()	Set<K>	Every key
values()	Collection<V>	Every value, duplicates ok
entrySet()	Set<Map.Entry<K, V>>	Key-value pairs

Iterating a map should almost always go through entrySet(), because it yields both halves in one pass rather than calling get for every key:

for (Map.Entry<String, Integer> entry : ages.entrySet()) {
    System.out.println(entry.getKey() + " is " + entry.getValue());
}

// Equivalent and more compact when you need no control flow
ages.forEach((name, age) -> System.out.println(name + " is " + age));

SortedMap and its subinterface NavigableMap extend the contract with ordering guarantees: firstKey(), lastKey(), headMap, tailMap, and the neighbour lookups floorKey, ceilingKey, higherKey, lowerKey. TreeMap implements them, and section 7.2 covers when that is worth the extra cost.

Key Takeaways

• A Map stores unique keys mapped to values, and is the right model for any lookup.
• put on an existing key replaces the value and returns the old one.
• get returning null is ambiguous when null values are stored, so do not store them.
• getOrDefault, putIfAbsent, merge, and computeIfAbsent replace most check-then-act code.
• keySet, values, and entrySet are live views, not copies.
• Iterate with entrySet() or forEach rather than looking up every key.

🧪 Practice

1. Count word frequencies in a sentence using merge with Integer::sum.
2. Build a Map<Character, List<String>> grouping words by first letter, using computeIfAbsent.
3. Interview: What is the difference between map.get(k) == null and !map.containsKey(k)? (Hint: consider a map that explicitly stores a null value.)

Iteration and the Enhanced for Loop

Every collection needs to be walked, and Java offers several ways to do it. They are not interchangeable, and the differences show up as soon as you try to modify the collection mid-walk.

The enhanced for loop (also called the for-each loop) is the default choice. It reads cleanly and works on any Iterable and on arrays:

List<String> names = List.of("Ada", "Grace", "Alan");

for (String name : names) {      // read as: "for each name in names"
    System.out.println(name);
}

It is pure syntactic sugar. The compiler rewrites it into the underlying iterator protocol, which is what Iterable and Iterator exist to provide:

// What the compiler actually generates
for (Iterator<String> it = names.iterator(); it.hasNext(); ) {
    String name = it.next();
    System.out.println(name);
}

  iterator()  ->  a cursor positioned BEFORE the first element

        [ Ada ][ Grace ][ Alan ]
       ^
    cursor        hasNext() -> true, next() -> "Ada", cursor advances

Iterator<E> has three methods:

Method	Purpose
hasNext()	Is there another element?
next()	Return the next element and advance
remove()	Remove the element last returned by next()

remove() is the reason to reach for an explicit iterator: it is the only safe way to delete elements while iterating.

List<String> words = new ArrayList<>(List.of("a", "bb", "c", "dd"));

Iterator<String> it = words.iterator();
while (it.hasNext()) {
    if (it.next().length() > 1) {
        it.remove();          // safe: the iterator knows about this change
    }
}
System.out.println(words);    // [a, c]

Since Java 8 there is a shorter way to express exactly that, and it is preferable when no other logic is involved:

words.removeIf(w -> w.length() > 1);   // same result, one line

For read-only traversal, forEach takes a lambda and reads well when the body is a single action:

names.forEach(System.out::println);

Choosing between the options:

Style	Use when
Enhanced for	Reading every element; the default
Explicit iterator	Removing elements during the walk
removeIf	Removing by a condition, with no other logic
Indexed for	You need the index, or are walking backwards
forEach	One simple action per element

One caution about the indexed loop: removing inside a forward indexed loop skips elements, because the remaining elements shift left while the index keeps moving right.

// BUG: removes "b" but skips "c", which slid into index 1
for (int i = 0; i < list.size(); i++) {
    if (shouldRemove(list.get(i))) {
        list.remove(i);       // no i-- compensation
    }
}

List additionally offers a ListIterator, which can move backwards with hasPrevious()/previous() and can insert with add(E) during the walk.

Key Takeaways

• The enhanced for loop compiles down to iterator(), hasNext(), and next().
• Any class implementing Iterable can be used with it, including your own.
• Iterator.remove() is the only safe removal during an explicit iteration.
• removeIf expresses conditional removal in one line and should be preferred.
• A forward indexed loop that removes elements silently skips the next one.
• ListIterator adds backwards traversal and insertion, for lists only.

🧪 Practice

1. Rewrite an enhanced for loop over a List<Integer> as an explicit iterator loop, producing identical output.
2. Remove every negative number from an ArrayList<Integer> twice, once with Iterator.remove() and once with removeIf.
3. Make a class Deck implement Iterable<Card> so it works with the enhanced for loop.
4. Interview: Why does the enhanced for loop not expose an index? (Hint: what would an index mean for a HashSet?)

Fail-Fast Iterators and ConcurrentModificationException

Sooner or later you will write a loop that modifies the collection it is walking and be met with ConcurrentModificationException. It is one of the most common runtime surprises in Java, and it is a feature rather than a bug.

The problem it guards against: an iterator holds a position inside a structure. If the structure changes underneath it, that position may now point at the wrong element, past the end, or at a node that no longer exists. Rather than quietly producing wrong results, the collections detect the change and throw immediately. That behaviour is called fail-fast.

List<String> names = new ArrayList<>(List.of("Ada", "Grace", "Alan"));

for (String name : names) {
    if (name.startsWith("G")) {
        names.remove(name);          // structural change behind the iterator
    }
}
// Exception in thread "main" java.util.ConcurrentModificationException

The mechanism is a counter. Each collection keeps a modCount field that is incremented on every structural modification, meaning any change to the number of elements. When an iterator is created it copies that value; on every next() it compares the copy with the current value.

  names.iterator()     modCount = 0      expectedModCount = 0   -> ok
  it.next()            modCount = 0  ==  expectedModCount = 0   -> ok
  names.remove(...)    modCount = 1                             (iterator unaware)
  it.next()            modCount = 1  !=  expectedModCount = 0   -> THROW

Iterator.remove() avoids the exception precisely because it updates both counters, keeping them in step.

Two details catch people out. First, the name is misleading: no second thread is needed. The example above is single-threaded. Second, the check happens on the next call to next(), so removing the second-to-last element can slip through undetected, because hasNext() returns false and the loop exits before the comparison ever runs. Do not rely on that; it is an accident of the implementation.

Only structural changes count. Replacing a value in place is fine:

List<String> names = new ArrayList<>(List.of("ada", "grace"));
for (int i = 0; i < names.size(); i++) {
    names.set(i, names.get(i).toUpperCase());   // set() is NOT structural
}

The four safe ways to modify while traversing:

Approach	Suitable for
Iterator.remove()	Removing with extra logic in the loop
removeIf(predicate)	Removing by a condition
Collect first, modify after	Adding, or complex multi-step edits
A concurrent collection	Genuine multi-threaded access

// Adding during iteration is impossible: collect, then apply
List<String> toAdd = new ArrayList<>();
for (String name : names) {
    if (name.length() < 4) {
        toAdd.add(name + "-short");
    }
}
names.addAll(toAdd);          // safe: iteration has finished

For real concurrency, java.util.concurrent offers weakly consistent iterators instead. CopyOnWriteArrayList iterates over a snapshot taken when the iterator was created, and ConcurrentHashMap reflects some but not necessarily all concurrent updates. Neither throws.

List<String> shared = new CopyOnWriteArrayList<>(List.of("a", "b"));
for (String s : shared) {
    shared.add(s + "!");      // no exception; the loop sees the old snapshot
}

Note the trade-off: CopyOnWriteArrayList copies the whole backing array on every write, so it suits read-heavy data that changes rarely, such as listener lists, and is a poor choice for anything write-heavy.

Key Takeaways

• Fail-fast iterators throw ConcurrentModificationException on detecting a structural change.
• The check uses a modCount counter compared on each next() call.
• No second thread is required; the usual cause is removing inside a for-each loop.
• Structural means the size changed; set(i, v) is not structural.
• Iterator.remove() and removeIf are the safe in-loop removals.
• Concurrent collections use weakly consistent iterators that never throw, at a cost in memory or freshness.

🧪 Practice

1. Reproduce a ConcurrentModificationException by removing inside a for-each loop, then fix it two different ways.
2. Show that removing the second-to-last element sometimes does not throw, and explain why using hasNext().
3. Replace an ArrayList with a CopyOnWriteArrayList in a loop that adds elements, and print the size before and after.
4. Interview: Why is ConcurrentModificationException a RuntimeException rather than a checked exception? (Hint: is it a condition a caller can recover from, or a programming mistake?)

<a id="72-collection-implementations"></a>

7.2 Collection Implementations

This subchapter covers the concrete classes behind the interfaces, what data structure each one uses, and how to choose between them.

ArrayList and LinkedList Trade-offs

Both implement List, so they are interchangeable from the outside. Inside they are entirely different, and the difference decides which one is fast for your access pattern.

An ArrayList stores elements in a contiguous array and remembers how many slots are in use. Reaching element i is one address computation.

  ArrayList: one block of memory, indexed directly

  index:     0      1      2      3      4      5      6
           +------+------+------+------+------+------+------+
           | Ada  |Grace | Alan |      |      |      |      |
           +------+------+------+------+------+------+------+
             size = 3                  capacity = 7

When the array fills, the list allocates a larger one (roughly 1.5x) and copies everything across. That copy is occasional, so the amortised cost of add at the end stays constant even though a single call can be expensive.

A LinkedList stores each element in its own node carrying references to the previous and next node. There is no array, so there is no index arithmetic: reaching element i means walking i links.

  LinkedList: scattered nodes joined by references

   head                                              tail
    |                                                  |
    v                                                  v
  +------+     +------+     +------+
  | Ada  |<--->|Grace |<--->| Alan |
  +------+     +------+     +------+
   each node: prev | value | next

The costs that follow from those two shapes:

Operation	ArrayList	LinkedList
get(i) / set(i, v)	O(1)	O(n), walks the links
add(e) at the end	O(1) amortised	O(1)
add(0, e) at the front	O(n), shifts all	O(1)
remove(i) in the middle	O(n), shifts	O(n) to find, O(1) to unlink
contains(o)	O(n)	O(n)
Memory per element	One slot	Node with two references

Reading that table naively suggests LinkedList wins on front insertion, and it does. In practice ArrayList still wins nearly every real benchmark, because the table ignores hardware. An array is contiguous, so the CPU prefetches the next elements into cache; linked nodes are scattered across the heap, and each hop is a potential cache miss. Copying a few thousand array slots is often faster than following a few hundred pointers.

There is also a memory cost. Each LinkedList node is a separate object with its own header plus two references, commonly around 24 extra bytes per element on a 64-bit JVM.

The classic trap is an indexed loop over a LinkedList:

List<String> list = new LinkedList<>(/* 100_000 elements */);

// O(n^2): every get(i) restarts the walk from the nearest end
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

// O(n): the iterator keeps its position between steps
for (String s : list) {
    process(s);
}

Practical guidance:

• Default to ArrayList. It is the right answer for the large majority of lists.
• If you know the final size, presize it: new ArrayList<>(10_000) avoids every intermediate copy.
• Use ArrayDeque, not LinkedList, when you need fast insertion and removal at both ends. It is faster and uses less memory.
• LinkedList earns its place mainly when you hold a ListIterator and splice elements in and out at the current position.

Vector is a legacy synchronised ArrayList kept only for compatibility. Its locking costs on every call even in single-threaded code. Use ArrayList, or Collections.synchronizedList or CopyOnWriteArrayList when you genuinely need thread safety.

Key Takeaways

• ArrayList is a growable array; LinkedList is a doubly linked list.
• ArrayList gives O(1) indexed access, LinkedList gives O(n).
• Big-O favours LinkedList for front insertion, but cache locality usually favours ArrayList anyway.
• LinkedList carries roughly 24 extra bytes of node overhead per element.
• Never use an indexed loop over a LinkedList; it degrades to O(n^2).
• Default to ArrayList, presize it when the size is known, and avoid Vector.

🧪 Practice

1. Time 100,000 add(0, x) calls on an ArrayList and a LinkedList and compare.
2. Time an indexed loop against an enhanced for loop over a 100,000-element LinkedList.
3. Presize an ArrayList to 1,000,000 and compare the fill time against the default constructor.
4. Interview: LinkedList.add(0, x) is O(1) and ArrayList.add(0, x) is O(n), yet ArrayList often wins. Why? (Hint: what does the CPU cache do with contiguous memory?)

HashSet, LinkedHashSet, and TreeSet

All three implement Set, so all three reject duplicates. They differ in the iteration order they promise and in what they demand of the elements you store.

A HashSet is backed by a HashMap whose keys are your elements. Adding computes hashCode() to pick a bucket, then compares with equals() inside that bucket. Both operations are effectively O(1), and iteration order is unspecified: it depends on hash values and table size, and can change when the set resizes.

Set<String> set = new HashSet<>();
set.add("banana");
set.add("apple");
set.add("cherry");
System.out.println(set);      // [banana, cherry, apple] -- arbitrary order

A LinkedHashSet extends HashSet with a doubly linked list threaded through the entries, recording insertion order. Lookups stay O(1); iteration returns elements in the order they were first added. The cost is two extra references per element.

Set<String> set = new LinkedHashSet<>();
set.add("banana");
set.add("apple");
set.add("cherry");
set.add("banana");            // ignored; does NOT move it to the end
System.out.println(set);      // [banana, apple, cherry] -- insertion order

A TreeSet is a red-black tree, a self-balancing binary search tree. It keeps elements in sorted order rather than insertion order, which costs O(log n) per operation but enables range queries that a hash set cannot answer at all.

Set<String> set = new TreeSet<>();
set.add("banana");
set.add("apple");
set.add("cherry");
System.out.println(set);      // [apple, banana, cherry] -- sorted

  HashSet             LinkedHashSet           TreeSet
  buckets             buckets + a chain       balanced BST

  [0] -> apple        apple -> banana         .     banana
  [1] ->                 ^        |          .      /    \
  [2] -> cherry          |        v         .    apple  cherry
  [3] -> banana       cherry <----+
        (arbitrary)   (insertion order)     (sorted order)

Side by side:

Feature	HashSet	LinkedHashSet	TreeSet
Backing structure	Hash table	Hash table + list	Red-black tree
add/contains	O(1)	O(1)	O(log n)
Iteration order	Unspecified	Insertion order	Sorted
Requires	hashCode/equals	hashCode/equals	Comparable or Comparator
Allows null	One	One	No
Memory	Lowest	Medium	Highest

Two practical consequences of the last two rows. TreeSet rejects null with a NullPointerException, because it must compare every element against existing ones. And a TreeSet decides duplicates by compareTo returning zero, not by equals, which means a comparator that ignores case will treat "Java" and "java" as the same element:

Set<String> ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
ci.add("Java");
ci.add("java");
System.out.println(ci.size());   // 1: compareTo returned 0

TreeSet also implements NavigableSet, which is the reason to choose it when order matters:

TreeSet<Integer> scores = new TreeSet<>(List.of(10, 20, 30, 40));

System.out.println(scores.first());          // 10
System.out.println(scores.last());           // 40
System.out.println(scores.floor(25));        // 20: greatest element <= 25
System.out.println(scores.ceiling(25));      // 30: least element >= 25
System.out.println(scores.headSet(30));      // [10, 20]: strictly below
System.out.println(scores.subSet(15, 35));   // [20, 30]
System.out.println(scores.descendingSet());  // [40, 30, 20, 10]

Choose HashSet by default, LinkedHashSet when reproducible iteration order matters (tests, output stability), and TreeSet when you need sorting or range queries.

Key Takeaways

• All three forbid duplicates; they differ in ordering and in element requirements.
• HashSet is O(1) with unspecified, unstable iteration order.
• LinkedHashSet keeps insertion order at the cost of two references per element; re-adding does not reorder.
• TreeSet keeps sorted order at O(log n) and supports range and neighbour queries.
• TreeSet rejects null and defines duplicates by compareTo, not equals.
• Default to HashSet; upgrade only when you need the extra guarantee.

🧪 Practice

1. Add the same five strings to each of the three sets and print each one, noting the orders.
2. Use a TreeSet<Integer> to find the nearest value above and below a target with ceiling and floor.
3. Build a TreeSet with String.CASE_INSENSITIVE_ORDER, add "ABC" and "abc", and explain the resulting size.
4. Interview: Why does TreeSet reject null when HashSet allows one? (Hint: what happens when you call compareTo on a null reference?)

HashMap, LinkedHashMap, and TreeMap

The three map implementations mirror the three set implementations exactly, which is not a coincidence: HashSet is a HashMap with dummy values, LinkedHashSet wraps a LinkedHashMap, and TreeSet wraps a TreeMap. Learning the maps gives you the sets for free.

A HashMap is an array of buckets. put hashes the key, spreads the bits, masks the result to a bucket index, and stores the entry there. Collisions, two keys landing in the same bucket, are resolved by chaining the entries together.

  key "alice" -> hashCode() -> spread -> index 3

  bucket:  0     1     2     3        4     5     6     7
         +---+ +---+ +---+ +-------+ +---+ +---+ +---+ +---+
         |   | |   | |   | | alice | |   | |   | |   | |   |
         +---+ +---+ +---+ +---|---+ +---+ +---+ +---+ +---+
                                v
                            +-------+
                            | bob   |   <- collision: same bucket, chained
                            +-------+

Since Java 8, a bucket whose chain exceeds eight entries converts to a balanced tree, so pathological hashing degrades to O(log n) rather than O(n). That matters for security as much as speed, because it defends against deliberately crafted colliding keys.

Two parameters control the table. Capacity is the number of buckets, always a power of two, defaulting to 16. Load factor defaults to 0.75; when size > capacity * loadFactor the table doubles and every entry is rehashed. Presizing avoids those rehashes:

// Expecting ~1000 entries: 1000 / 0.75 = 1334, rounded up to 2048 buckets
Map<String, Integer> counts = new HashMap<>(2048);

A LinkedHashMap adds insertion-order iteration, and one feature the linked set does not expose: access order. Constructed with the three- argument constructor and accessOrder = true, every get moves the entry to the end, which makes an LRU cache about ten lines of code.

// A least-recently-used cache holding at most 3 entries
Map<String, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > 3;        // evict the front entry once we exceed 3
    }
};

lru.put("a", "1");
lru.put("b", "2");
lru.put("c", "3");
lru.get("a");                     // "a" is now the most recently used
lru.put("d", "4");                // evicts "b", the least recently used
System.out.println(lru.keySet()); // [c, a, d]

A TreeMap is a red-black tree keyed by sort order, implementing NavigableMap. Every operation is O(log n), and it answers questions no hash map can:

TreeMap<Integer, String> grades = new TreeMap<>();
grades.put(60, "D");
grades.put(70, "C");
grades.put(80, "B");
grades.put(90, "A");

System.out.println(grades.firstKey());        // 60
System.out.println(grades.floorEntry(85));    // 80=B: the grade for a score 85
System.out.println(grades.headMap(80));       // {60=D, 70=C}
System.out.println(grades.descendingMap());   // {90=A, 80=B, 70=C, 60=D}

That floorEntry call is the idiomatic way to implement range lookups such as tax brackets, shipping tiers, or grade boundaries.

Feature	HashMap	LinkedHashMap	TreeMap
Structure	Hash table	Hash table + list	Red-black tree
get/put	O(1)	O(1)	O(log n)
Key order	Unspecified	Insertion or access	Sorted
Null keys	One allowed	One allowed	Not allowed
Null values	Allowed	Allowed	Allowed
Extra feature	-	LRU eviction	Range queries

Hashtable is the legacy synchronised equivalent of HashMap and should not be used. For concurrent access use ConcurrentHashMap, which locks only individual bins rather than the whole table and scales far better.

Key Takeaways

• The three maps mirror the three sets, because the sets are implemented on top of them.
• HashMap uses buckets with chaining, converting long chains to trees after eight entries.
• Capacity 16 and load factor 0.75 are the defaults; presize to avoid rehashing.
• LinkedHashMap supports access order, giving an LRU cache via removeEldestEntry.
• TreeMap is sorted, O(log n), forbids null keys, and supports floorEntry style range lookups.
• Prefer ConcurrentHashMap over the legacy Hashtable for thread safety.

🧪 Practice

1. Insert ten entries into each map type and print keySet() for each, noting the ordering.
2. Implement a fixed-size LRU cache with LinkedHashMap and verify the eviction order.
3. Model tax brackets in a TreeMap<Integer, Double> and look up the rate for an arbitrary income with floorEntry.
4. Interview: Why is HashMap capacity always a power of two? (Hint: how can a modulo by a power of two be computed with a bitmask?)

ArrayDeque, Stack, and PriorityQueue

Three implementations for processing order rather than storage order. Each answers a different question about which element comes next.

An ArrayDeque is a resizable circular array supporting insertion and removal at both ends in O(1). It is the recommended implementation of both Queue and Deque, and therefore also the recommended stack.

  Circular array: head and tail move, elements never shift

   indices:   0     1     2     3     4     5
            +-----+-----+-----+-----+-----+-----+
            |  D  |     |     |  A  |  B  |  C  |
            +-----+-----+-----+-----+-----+-----+
                              ^                 wraps around to index 0
                            head        tail ---+
   logical order: A, B, C, D

Used as a FIFO queue:

Deque<String> queue = new ArrayDeque<>();
queue.offer("first");           // adds at the tail
queue.offer("second");
System.out.println(queue.poll());   // "first": removes from the head

Used as a LIFO stack:

Deque<String> stack = new ArrayDeque<>();
stack.push("first");            // push == addFirst
stack.push("second");
System.out.println(stack.pop());    // "second": pop == removeFirst
System.out.println(stack.peek());   // "first": top without removing

ArrayDeque rejects null, and that is intentional: poll and peek return null to signal emptiness, so a stored null would be indistinguishable from an empty deque.

Stack is a legacy class extending Vector. Avoid it in new code for two reasons. It is synchronised, paying for locks you almost never need. More confusingly, it inherits Vector's list behaviour, so it exposes get(int) and iterates bottom to top, the opposite of pop order.

Stack<String> legacy = new Stack<>();
legacy.push("a");
legacy.push("b");
System.out.println(legacy);      // [a, b]: prints bottom-first, not pop order
System.out.println(legacy.get(0));  // "a": a stack should not have indices

A PriorityQueue returns the smallest element next rather than the oldest. It is a binary heap stored in an array: the root is the minimum, and each node is smaller than its children.

  Binary min-heap, and its array layout

              1
            /   \
           3     2         array: [1, 3, 2, 7, 4]
          / \   /          parent of i = (i-1)/2
         7   4             children of i = 2i+1, 2i+2

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);

System.out.println(pq.poll());   // 1: always the smallest
System.out.println(pq.poll());   // 3
System.out.println(pq);          // [5]

A comparator flips or customises the ordering, which is how you build a max-heap or prioritise by a field:

// Max-heap
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());

// Highest-priority task first, breaking ties by name
PriorityQueue<Task> tasks =
    new PriorityQueue<>(Comparator.comparingInt(Task::priority).reversed()
                                  .thenComparing(Task::name));

The single most common mistake is expecting the whole queue to be sorted. It is not. A heap only guarantees the head; printing it or iterating it yields heap array order, which is partially sorted at best. Sorted output requires draining it with repeated poll() calls.

Implementation	offer	poll	peek	Next element is
ArrayDeque	O(1)	O(1)	O(1)	Oldest, or newest
PriorityQueue	O(log n)	O(log n)	O(1)	Smallest by order
LinkedList	O(1)	O(1)	O(1)	Oldest

Key Takeaways

• ArrayDeque is the default choice for both queues and stacks, at O(1) on both ends.
• It forbids null so that a null from poll unambiguously means empty.
• The legacy Stack extends Vector, is synchronised, and iterates in the wrong direction.
• PriorityQueue is a binary heap returning the smallest element, O(log n) per insert and remove.
• A PriorityQueue is not sorted; only its head is guaranteed.
• Pass a Comparator to build a max-heap or to order by a field.

🧪 Practice

1. Check whether a string of brackets is balanced using an ArrayDeque as a stack.
2. Find the three largest numbers in a list using a size-bounded PriorityQueue.
3. Print a PriorityQueue directly and then drain it with poll, and explain why the two orders differ.
4. Interview: Why does ArrayDeque forbid null elements? (Hint: what would poll() returning null then mean?)

Choosing an Implementation by Complexity

With roughly a dozen implementations available, the choice can feel arbitrary. It is not. Two questions settle it almost every time, and only the second involves performance.

Question one: what shape is the data?

  Do you look things up by a key?
      |
      +-- YES --> Map
      |
      +-- NO --> Must duplicates be rejected?
                     |
                     +-- YES --> Set
                     |
                     +-- NO --> Do you take elements in a processing order?
                                    |
                                    +-- YES --> Queue / Deque
                                    |
                                    +-- NO --> List

Question two: what guarantee do you need on order? Within each family, "no guarantee" is fastest, "insertion order" costs a little memory, and "sorted" costs a logarithmic factor.

Need	List	Set	Map
Fastest, order irrelevant	ArrayList	HashSet	HashMap
Insertion order kept	ArrayList	LinkedHashSet	LinkedHashMap
Sorted order	sort a list	TreeSet	TreeMap
Both ends fast	ArrayDeque	-	-
Thread-safe	CopyOnWriteArrayList	ConcurrentHashMap.newKeySet()	ConcurrentHashMap

The consolidated complexity table, worth committing to memory for interviews:

Implementation	Access by index	Search	Insert	Delete
ArrayList	O(1)	O(n)	O(1) amortised at end	O(n)
LinkedList	O(n)	O(n)	O(1) at ends	O(1) at a known node
ArrayDeque	-	O(n)	O(1) at ends	O(1) at ends
HashSet	-	O(1)	O(1)	O(1)
LinkedHashSet	-	O(1)	O(1)	O(1)
TreeSet	-	O(log n)	O(log n)	O(log n)
HashMap	-	O(1)	O(1)	O(1)
LinkedHashMap	-	O(1)	O(1)	O(1)
TreeMap	-	O(log n)	O(log n)	O(log n)
PriorityQueue	-	O(n)	O(log n)	O(log n) at head

Three cautions about reading that table:

• The O(1) hash figures assume a decent hashCode. A type whose hashCode returns a constant is still correct but pushes every entry into one bucket, degrading lookups to O(log n) after treeification.
• Constant factors are real. For fewer than about a hundred elements, a linear scan of an ArrayList frequently beats a HashSet, because there is no hashing and the data sits in cache.
• "Search" for a List means contains. If membership testing is a hot path in your code, that is a signal you wanted a Set.

The one classic swap worth knowing: replacing List.contains inside a loop with a HashSet turns an O(n*m) algorithm into O(n+m).

// SLOW: contains is O(n), called m times
List<String> blocked = loadBlockedUsers();
for (String user : allUsers) {
    if (blocked.contains(user)) { ... }
}

// FAST: build the set once, then every lookup is O(1)
Set<String> blocked = new HashSet<>(loadBlockedUsers());
for (String user : allUsers) {
    if (blocked.contains(user)) { ... }
}

Key Takeaways

• Choose the interface from the data's shape, then the implementation from the ordering guarantee you need.
• Hash implementations are O(1), tree implementations O(log n), and trees buy you sorting and range queries.
• ArrayList, HashSet, and HashMap are the correct defaults.
• O(1) hashing assumes a well-distributed hashCode.
• For small collections, constant factors often beat asymptotic complexity.
• Repeated List.contains is the signal to switch to a Set.

🧪 Practice

1. Given "track unique visitor IDs and report them alphabetically", name the implementation and justify it.
2. Rewrite a nested loop that uses List.contains to use a HashSet, and measure both on 100,000 elements.
3. Choose implementations for: an undo history, a browser's open tabs, a phone book, and a print spooler.
4. Interview: When might an ArrayList outperform a HashSet for membership tests? (Hint: how large does n have to be before hashing pays for itself?)

Immutable and Unmodifiable Collections

A collection that can be modified by anyone holding a reference is a shared mutable variable. Handing one out from a getter lets callers rewrite your object's internals behind its back. Unmodifiable collections close that hole.

The problem in three lines:

public class Team {
    private final List<String> members = new ArrayList<>();

    public List<String> getMembers() { return members; }   // LEAK
}

team.getMembers().clear();     // any caller can wipe the team's state

final does not help. It stops the field being reassigned; it says nothing about the object the field points at.

Since Java 9 the factory methods produce genuinely immutable collections:

List<String> list = List.of("a", "b", "c");
Set<String> set = Set.of("x", "y");
Map<String, Integer> map = Map.of("a", 1, "b", 2);

// More than ten map entries, or clearer formatting:
Map<String, Integer> big = Map.ofEntries(
    Map.entry("a", 1),
    Map.entry("b", 2)
);

list.add("d");    // UnsupportedOperationException at runtime

These factories have three behaviours that surprise people:

• They reject null elements, keys, and values with a NullPointerException.
• Set.of and Map.of throw IllegalArgumentException on duplicate elements or keys, rather than silently collapsing them.
• Their iteration order is unspecified and deliberately randomised between JVM runs, so code must not depend on it.

The older Collections.unmodifiableList family behaves differently in an important way. It returns a read-only view of a collection, not a copy. The view forbids modification, but the underlying collection can still change, and those changes are visible through the view.

List<String> backing = new ArrayList<>(List.of("a", "b"));
List<String> view = Collections.unmodifiableList(backing);

view.add("c");             // UnsupportedOperationException, as expected
backing.add("c");          // but this succeeds...
System.out.println(view);  // [a, b, c] -- the view changed underneath

Java 10 added List.copyOf, Set.copyOf, and Map.copyOf, which take a snapshot and are the correct tool for a defensive getter:

public class Team {
    private final List<String> members = new ArrayList<>();

    public List<String> getMembers() {
        return List.copyOf(members);   // immutable snapshot, safe to hand out
    }
}

Approach	Modifiable	Reflects source changes	Rejects null
new ArrayList<>(source)	Yes	No, it is a copy	No
Collections.unmodifiableList	No	Yes, it is a view	No
List.of(...)	No	Not applicable	Yes
List.copyOf(source)	No	No, it is a snapshot	Yes

One last limit to be honest about. Immutability here is shallow: the collection cannot be restructured, but the objects inside it can still be mutated if they are mutable themselves.

List<StringBuilder> l = List.of(new StringBuilder("a"));
// l.add(...)         -> throws
l.get(0).append("b");  // allowed: the ELEMENT is still mutable

Deep immutability requires immutable element types, which is one of the arguments for records and for String.

Key Takeaways

• A final field still exposes a mutable object; defensive copying is what protects state.
• List.of, Set.of, and Map.of create truly immutable collections.
• Those factories reject nulls, reject duplicate keys, and randomise iteration order between runs.
• Collections.unmodifiableList returns a view, so the backing collection can still change beneath it.
• List.copyOf takes an immutable snapshot and is the right tool for a getter.
• Collection immutability is shallow; mutable elements remain mutable.

🧪 Practice

1. Write a class with a List field and demonstrate an external caller mutating it through the getter, then fix it with List.copyOf.
2. Show that an unmodifiable view reflects later changes to its backing list.
3. Call Set.of("a", "a") and List.of("a", null) and record which exceptions each throws.
4. Interview: Is List.of(new ArrayList<>()) immutable? (Hint: distinguish the structure of the outer list from the state of its elements.)

<a id="73-working-with-collections"></a>

7.3 Working with Collections

This subchapter covers the operations you perform on collections: ordering them, searching them, converting them, and meeting the contracts they rely on.

Sorting with Comparable and Comparator

Sorting requires a definition of "smaller". Java offers two places to put that definition, and the choice between them is about ownership: does the type have one obvious order, or does the caller need a different order each time?

Comparable<T> defines a type's single natural ordering. The type implements it, and the rule travels with every instance. String orders lexicographically, Integer numerically, LocalDate chronologically.

public class Employee implements Comparable<Employee> {
    private final String name;
    private final int salary;

    @Override
    public int compareTo(Employee other) {
        // Contract: negative if this < other, zero if equal, positive if >
        return Integer.compare(this.salary, other.salary);
        // NOT this.salary - other.salary: that overflows for extreme values
    }
}

List<Employee> staff = new ArrayList<>(...);
Collections.sort(staff);      // uses compareTo
staff.sort(null);             // same thing: null means natural ordering

The subtraction warning is worth taking seriously. Integer.MIN_VALUE - 1 wraps around to a positive number, and the resulting comparator is inconsistent in a way that can make TreeMap lose entries. Always use Integer.compare, Double.compare, and friends.

Comparator<T> defines an ordering outside the type. It is the tool when you do not own the class, when there is no single sensible order, or when you need several orderings.

// Pre-Java 8, as an anonymous class
Comparator<Employee> byName = new Comparator<Employee>() {
    @Override
    public int compare(Employee a, Employee b) {
        return a.getName().compareTo(b.getName());
    }
};

// Java 8 onwards, with a key extractor
Comparator<Employee> byName2 = Comparator.comparing(Employee::getName);

The factory methods compose, which is where comparators become genuinely pleasant to use:

Comparator<Employee> ordering =
        Comparator.comparing(Employee::getDepartment)        // primary key
                  .thenComparing(Employee::getSalary,
                                 Comparator.reverseOrder())  // tie-break, desc
                  .thenComparing(Employee::getName);         // final tie-break

staff.sort(ordering);

Factory / method	Purpose
Comparator.comparing(fn)	Order by an extracted key
comparingInt / Long / Double	Same, avoiding boxing
thenComparing(fn)	Tie-breaker
reversed()	Invert the whole comparator
Comparator.reverseOrder()	Reverse natural ordering
nullsFirst(cmp) / nullsLast(cmp)	Position nulls instead of throwing

Note the difference between .reversed() at the end of a chain, which inverts everything before it, and passing Comparator.reverseOrder() to a single thenComparing, which inverts only that one key. Mixing them up is a common source of "the secondary sort is backwards" bugs.

  comparing(dept).thenComparing(salary).reversed()
      -> reverses BOTH keys

  comparing(dept).thenComparing(salary, reverseOrder())
      -> dept ascending, salary descending

Side by side:

Aspect	Comparable	Comparator
Package	java.lang	java.util
Method	compareTo(T other)	compare(T a, T b)
Where it lives	Inside the class	Outside, as a separate object
How many	One per type	As many as you like
Modifies class	Yes	No

Both must obey the same contract, and violating it causes real failures:

• compare(a, b) and compare(b, a) must have opposite signs.
• The ordering must be transitive.
• It should be consistent with equals: compare(a, b) == 0 should coincide with a.equals(b). If it does not, TreeSet and TreeMap behave in ways that contradict the Set and Map contracts, because they decide equality by comparison.

Java's sort is stable for object arrays and lists, using TimSort: elements that compare equal keep their relative order. That is what makes successive sorts compose, so sorting by name and then by department yields departments in order with names still sorted inside each one.

Key Takeaways

• Comparable gives a type one natural ordering via compareTo.
• Comparator supplies external orderings, and you can define many.
• Use Integer.compare rather than subtraction to avoid overflow.
• Comparator.comparing(...).thenComparing(...) composes multi-key orderings.
• .reversed() inverts the whole chain; a per-key reversal goes inside thenComparing.
• Orderings should be consistent with equals, or TreeSet and TreeMap misbehave.
• sort is stable, so equal elements keep their prior relative order.

🧪 Practice

1. Make a Book class Comparable by title, then sort a list of books.
2. Sort the same list by year descending, then by title ascending, with a composed comparator.
3. Sort a list containing nulls using Comparator.nullsFirst.
4. Interview: What breaks if compareTo is inconsistent with equals? (Hint: add two such objects to a TreeSet and count the elements.)

Searching and Bulk Operations

Beyond adding and removing one element at a time, collections support searching and whole-collection operations. Knowing them avoids writing loops that the library already provides.

Linear search is what contains, indexOf, and lastIndexOf do. They compare with equals, walk from one end, and cost O(n):

List<String> names = List.of("Ada", "Grace", "Alan", "Grace");

names.contains("Alan");        // true
names.indexOf("Grace");        // 1: first occurrence
names.lastIndexOf("Grace");    // 3: last occurrence
names.indexOf("Nobody");       // -1: absent, never an exception

Binary search is O(log n) but carries a precondition that the library cannot check for you: the list must already be sorted by the same ordering you search with. Searching an unsorted list compiles, runs, and returns nonsense.

List<Integer> sorted = new ArrayList<>(List.of(10, 20, 30, 40, 50));

int found = Collections.binarySearch(sorted, 30);    // 2: the index
int missing = Collections.binarySearch(sorted, 35);  // negative

// A negative result encodes where the value WOULD go: -(insertionPoint) - 1
int insertionPoint = -missing - 1;      // 3
sorted.add(insertionPoint, 35);         // keeps the list sorted

That negative-return convention is a frequent interview question. The result is never a plain -1, because index 0 needs its own distinct "not found" value.

Bulk operations apply set-style logic to whole collections. Each returns a boolean saying whether the receiver changed:

List<String> a = new ArrayList<>(List.of("x", "y", "z"));
List<String> b = List.of("y", "z", "w");

a.addAll(b);       // union-ish: [x, y, z, y, z, w] -- duplicates kept in a List
a.retainAll(b);    // intersection: keep only elements also in b
a.removeAll(b);    // difference: remove every element found in b
a.containsAll(b);  // subset test

With sets these correspond exactly to the mathematical operations:

  A = {1, 2, 3}      B = {3, 4, 5}

  A.addAll(B)     -> {1, 2, 3, 4, 5}    union
  A.retainAll(B)  -> {3}                intersection
  A.removeAll(B)  -> {1, 2}             difference

Set<Integer> a = new HashSet<>(Set.of(1, 2, 3));
Set<Integer> b = Set.of(3, 4, 5);

Set<Integer> union = new HashSet<>(a);
union.addAll(b);                        // {1, 2, 3, 4, 5}

Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b);              // {3}

Note that each of these mutates the receiver, which is why the examples copy first. There is a genuine performance trap here too: removeAll and retainAll call contains on the argument for each element, so passing a List makes the whole operation O(n*m). Pass a Set and it is O(n).

// SLOW when blocked is a List: O(n*m)
users.removeAll(blocked);

// FAST: O(n)
users.removeAll(new HashSet<>(blocked));

Two more bulk methods worth knowing, both added in Java 8:

list.removeIf(s -> s.isBlank());        // conditional removal, in place
list.replaceAll(String::toUpperCase);   // transform every element, in place
map.replaceAll((k, v) -> v * 2);        // the map equivalent

Key Takeaways

• contains and indexOf are linear searches using equals, returning -1 when absent.
• binarySearch is O(log n) but requires a list already sorted by the same ordering.
• A negative binarySearch result encodes the insertion point as -(point) - 1.
• addAll, retainAll, removeAll, and containsAll give union, intersection, difference, and subset.
• These methods mutate the receiver, so copy first if you need the original.
• Pass a Set to removeAll and retainAll to avoid O(n*m) behaviour.

🧪 Practice

1. Compute the union, intersection, and difference of two Set<Integer> values without mutating either input.
2. Use Collections.binarySearch on a missing value and insert it at the decoded insertion point.
3. Demonstrate binarySearch returning a wrong answer on an unsorted list.
4. Interview: Why does binarySearch return -(insertionPoint) - 1 rather than just -insertionPoint? (Hint: what would a value that belongs at index 0 return?)

The Collections Utility Class

java.util.Collections is a class of static helpers that operate on collections. It cannot be instantiated; it exists purely because Java had no interface default methods when the framework was designed. Knowing what is in it saves writing algorithms that already exist.

The most used members, grouped by purpose:

List<Integer> nums = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6));

// --- Ordering ---
Collections.sort(nums);                      // natural ordering, in place
Collections.sort(nums, Comparator.reverseOrder());
Collections.reverse(nums);                   // flip the current order
Collections.shuffle(nums);                   // random permutation
Collections.shuffle(nums, new Random(42));   // reproducible shuffle
Collections.swap(nums, 0, 3);                // exchange two positions
Collections.rotate(nums, 2);                 // shift right, wrapping around

// --- Extremes and counting ---
int min = Collections.min(nums);
int max = Collections.max(nums, Comparator.naturalOrder());
int ones = Collections.frequency(nums, 1);   // how many times 1 appears

// --- Whole-collection edits ---
Collections.fill(nums, 0);                   // replace every element
List<String> blanks = Collections.nCopies(3, "-");   // immutable [-, -, -]

// --- Tests ---
boolean apart = Collections.disjoint(listA, listB);  // no elements in common

A second group produces wrapper collections. All of them return views backed by the original, not copies:

Factory	Returns
unmodifiableList/Set/Map	Read-only view
synchronizedList/Set/Map	View with every method synchronised
checkedList(list, Class)	View that rejects wrong-typed inserts at runtime
emptyList(), emptySet()	Shared immutable empty instances
singletonList(e), singleton(e)	Immutable one-element collection

synchronizedList has a sharp edge worth stating explicitly. Each individual method is synchronised, but iteration is not, so you must lock manually around any loop:

List<String> sync = Collections.synchronizedList(new ArrayList<>());

synchronized (sync) {               // required: iteration is not atomic
    for (String s : sync) {
        process(s);
    }
}

This is one reason the java.util.concurrent collections are preferred for new concurrent code: ConcurrentHashMap and CopyOnWriteArrayList need no such external locking.

checkedList is a debugging aid. When legacy code passes a raw List around, an Integer can end up inside a List<String> and the ClassCastException surfaces far from the culprit. A checked view fails at the insertion instead:

List<String> safe = Collections.checkedList(new ArrayList<>(), String.class);
List raw = safe;
raw.add(42);      // ClassCastException HERE, at the bad insert

Since Java 9, List.of and friends have replaced most uses of emptyList and singletonList, and sort/removeIf/replaceAll exist directly on List. Prefer the instance methods where they exist:

Collections.sort(list);   // older style
list.sort(null);          // modern equivalent

Key Takeaways

• Collections is a static utility class of algorithms over collections.
• It provides sort, reverse, shuffle, swap, rotate, min, max, frequency, and disjoint.
• Its wrapper factories return views over the original, never copies.
• synchronizedList synchronises individual methods but not iteration, which you must lock yourself.
• checkedList catches raw-type pollution at the point of the bad insert.
• Prefer modern instance methods such as list.sort over the older static equivalents.

🧪 Practice

1. Shuffle a list with a seeded Random twice and confirm both orders match.
2. Use Collections.frequency to find the most common element in a list.
3. Wrap a list with checkedList, assign it to a raw variable, and trigger the ClassCastException.
4. Interview: Why is iterating a synchronizedList not thread-safe even though every method is synchronised? (Hint: how many method calls does one loop make, and what can happen between them?)

Hashing Requirements for Keys and Set Elements

Hash-based collections are fast because they compute where an element belongs instead of searching for it. That only works if your objects answer two questions consistently, and getting it wrong produces bugs that look like the collection is broken.

The two questions are hashCode(), "which bucket?", and equals(), "is this the same element?". A lookup does both: hash to find the bucket, then compare with equals inside it.

  set.contains(x)
        |
        1. h = x.hashCode()  -> bucket index
        |
        2. for each entry in that bucket: entry.equals(x) ?
        |
        +-- found -> true        +-- bucket empty or no match -> false

The failure follows directly. If two equal objects produce different hash codes, they land in different buckets and step 2 never runs:

public class Point {
    private final int x, y;

    @Override
    public boolean equals(Object o) {          // equals overridden...
        if (this == o) return true;
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }
    // ...but hashCode is NOT: inherited identity hash
}

Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
System.out.println(set.contains(new Point(1, 2)));   // false!
set.add(new Point(1, 2));
System.out.println(set.size());                      // 2: "duplicates"

Hence the contract, which the compiler cannot enforce:

1. If a.equals(b), then a.hashCode() == b.hashCode(). Mandatory.
2. Unequal objects may share a hash code. That is a collision, handled correctly, just slower.
3. hashCode must be stable for as long as the object is in a hash collection.

A correct implementation, using the JDK helpers rather than hand-rolled arithmetic:

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

@Override
public int hashCode() {
    return Objects.hash(x, y);   // same fields as equals, in the same spirit
}

The golden rule: use exactly the same fields in both methods. If equals compares x and y, hashCode must be computed from x and y.

Rule 3 is the subtler trap. Mutating a field used by hashCode after insertion strands the object in the wrong bucket, where it cannot be found even by its own reference:

Set<MutablePoint> set = new HashSet<>();
MutablePoint p = new MutablePoint(1, 2);
set.add(p);                           // filed under hash of (1, 2)

p.setX(99);                           // hash is now that of (99, 2)
System.out.println(set.contains(p));  // false: looks in the wrong bucket
System.out.println(set.size());       // 1: still there, but unreachable

The lesson is to use immutable types as keys and set elements. String, Integer, LocalDate, enums, and records are all safe. Records are especially convenient, because the compiler generates equals and hashCode from all components automatically:

public record Point(int x, int y) { }   // equals and hashCode: done correctly

A final note on distribution. Returning a constant is legal, since it satisfies the contract, but it puts every element in one bucket:

@Override
public int hashCode() { return 42; }   // correct, but every lookup degrades

The collection still works. It just stops being a hash table.

Key Takeaways

• Hash lookups use hashCode to pick a bucket and equals to match inside it.
• Equal objects must have equal hash codes; overriding one without the other breaks lookups.
• Unequal objects sharing a hash code is a legal collision, only a performance cost.
• Use the same fields in equals and hashCode, and build the latter with Objects.hash.
• Mutating a hash-relevant field after insertion makes the element unreachable.
• Prefer immutable keys; records generate both methods correctly for free.

🧪 Practice

1. Write a class overriding equals but not hashCode, add two equal instances to a HashSet, and print the size.
2. Add the correct hashCode and confirm the size becomes 1.
3. Insert a mutable object into a HashSet, change a key field, and show contains returning false for that very object.
4. Interview: Is a hashCode that always returns 42 correct? (Hint: separate the contract's correctness requirement from the performance consequence.)

Converting Between Arrays and Collections

Arrays and collections solve the same problem in different eras of the language, and real code crosses between them constantly: a varargs parameter arrives as an array, a library returns one, a List must be handed to an older API. The conversions are short but contain two genuine traps.

Array to List. Arrays.asList is the obvious call and the more dangerous one. It returns a fixed-size view backed by the array, not an independent list:

String[] array = {"a", "b", "c"};
List<String> view = Arrays.asList(array);

view.set(0, "z");                  // allowed: writes THROUGH to the array
System.out.println(array[0]);      // "z": the array changed

view.add("d");                     // UnsupportedOperationException: fixed size
view.remove(0);                    // UnsupportedOperationException

For a real, growable list, wrap it:

List<String> real = new ArrayList<>(Arrays.asList(array));  // an independent copy
List<String> immutable = List.of(array);                    // immutable copy

The second trap involves primitives. Generics cannot hold int, so an int[] is treated as a single object, giving a one-element list:

int[] nums = {1, 2, 3};
List<int[]> wrong = Arrays.asList(nums);      // size 1: the array itself
System.out.println(wrong.size());             // 1

Integer[] boxed = {1, 2, 3};
List<Integer> right = Arrays.asList(boxed);   // size 3
System.out.println(right.size());             // 3

// The clean way for primitives, using streams from chapter 8
List<Integer> fromPrimitives = Arrays.stream(nums).boxed().toList();

List to array. The modern form passes a zero-length array, which tells the list the element type while letting it allocate the right size:

List<String> list = List.of("a", "b", "c");

String[] arr = list.toArray(new String[0]);   // preferred
Object[] objects = list.toArray();            // loses the element type
String[] arr2 = list.toArray(String[]::new);  // Java 11 generator form

Passing new String[0] rather than new String[list.size()] is the recommended idiom: on modern JVMs the empty array is faster, because the allocation is intrinsified and the sized version gets zero-filled before being overwritten.

The whole set of conversions in one table:

From	To	Call
T[]	fixed List	Arrays.asList(arr)
T[]	mutable List	new ArrayList<>(Arrays.asList(arr))
T[]	immutable List	List.of(arr)
T[]	Set	new HashSet<>(Arrays.asList(arr)) or Set.of(arr)
int[]	List<Integer>	Arrays.stream(arr).boxed().toList()
List<T>	T[]	list.toArray(new T[0])
List<Integer>	int[]	list.stream().mapToInt(Integer::intValue).toArray()
Collection	List	new ArrayList<>(collection)

A few related array utilities that come up alongside these conversions:

int[] a = {3, 1, 2};

Arrays.sort(a);                      // in-place sort
System.out.println(Arrays.toString(a));          // [1, 2, 3]: readable output
System.out.println(Arrays.equals(a, new int[]{1, 2, 3}));   // true, by content

int[][] grid = {{1, 2}, {3, 4}};
System.out.println(Arrays.deepToString(grid));   // [[1, 2], [3, 4]]

int[] copy = Arrays.copyOf(a, 5);    // [1, 2, 3, 0, 0]: padded with zeros
int[] slice = Arrays.copyOfRange(a, 1, 3);       // [2, 3]

Arrays.toString is worth remembering on its own: printing an array directly gives you something like [I@1b6d3586, because arrays do not override toString.

Key Takeaways

• Arrays.asList returns a fixed-size view that writes through to the original array.
• Wrap it in new ArrayList<>(...) for an independent, growable list.
• Arrays.asList(int[]) yields a one-element List<int[]>; box with Arrays.stream(...).boxed() instead.
• Convert to an array with toArray(new String[0]), which is both typed and fast.
• list.toArray() without an argument returns Object[] and loses the element type.
• Use Arrays.toString and Arrays.deepToString to print arrays readably.

🧪 Practice

1. Create an array, wrap it with Arrays.asList, modify element 0 through the list, and print the array.
2. Call Arrays.asList on an int[] and on an Integer[], and print both sizes.
3. Round-trip a List<String> to a String[] and back, confirming equality.
4. Interview: Why does Arrays.asList support set but not add? (Hint: what resource is the returned list actually backed by, and can it grow?)

<a id="8-functional-programming-in-an-object-oriented-language"></a>