So far each Book has stood alone — you built one, inspected it, and moved on. A library does not have one book; it has thousands, and the questions it asks are about the collection: which books did Herbert write, what is in stock, which title comes first on the shelf. A single object cannot answer those. You need a container that holds many objects and the operations to search and arrange them.
Java's collections are those containers. This milestone keeps everything in memory — no database, no files — and focuses on the two decisions that shape every collection-backed feature: which container to choose, and how to find and order the things inside it.
flowchart TD
subgraph L["ArrayList"]
L1["Dune"] --> L2["Beloved"] --> L3["The Halo"]
end
subgraph M["HashMap"]
K["key Dune"] --> V["Book value"]
end
style L3 fill:#b45309,color:#fff
style V fill:#3776ab,color:#fff
Choose the container by how you ask the question
The container you reach for is decided by the question you ask most often. An ArrayList keeps things in the order you added them and lets you walk through every element — perfect for list all books by Herbert or show the whole shelf. A HashMap stores each value under a unique key, so find the book with this ISBN jumps straight to it without scanning.
The rule of thumb: if you look things up by position or by scanning, use a List; if you look them up by a unique key, use a Map. Picking wrong is expensive — searching a large List for a key that a Map would resolve instantly is the difference between a snappy interface and a frozen one.
import java.util.ArrayList;
import java.util.List;
public class Main {
static class Book {
private final String title;
private final String author;
private final int year;
Book(String title, String author, int year) {
this.title = title;
this.author = author;
this.year = year;
}
String getTitle() { return title; }
String getAuthor() { return author; }
int getYear() { return year; }
}
public static void main(String[] args) {
List<Book> books = new ArrayList<>();
books.add(new Book("Dune", "Herbert", 1965));
books.add(new Book("Beloved", "Morrison", 1987));
books.add(new Book("The Halo", "Herbert", 1977));
// Search: every book by Herbert, in insertion order.
for (Book b : books) {
if (b.getAuthor().equals("Herbert")) {
System.out.println(b.getTitle());
}
}
}
}
Search is a filtered scan
Searching a List means walking it and keeping the elements that pass a test. The loop reads one book at a time, checks a condition — is the author Herbert? — and either prints it or skips it. This is a linear search: every element is examined in turn, so the cost grows with the length of the list.
For a few hundred books that is instant. For a few million, or for a lookup that fires on every keystroke, a linear scan becomes the bottleneck — and that is exactly when a Map, which finds a key without scanning, earns its place. Learn the scan first, though, because every more clever search is built on the same idea of test, then keep or skip.
flowchart LR
A["for each book<br/>in the list"] --> C{"author<br/>matches?"}
C -->|"yes"| P["collect the book"]
C -->|"no"| X["skip it"]
style P fill:#3776ab,color:#fff
style X fill:#b45309,color:#fff
The library needs to look up a book instantly by its unique ISBN. Which collection fits the job best?
A HashMap stores each value under a key, so get(isbn) jumps straight to the right book. An ArrayList would force a walk through the elements until the match is found — fine for a handful of books, slow for thousands.
import java.util.HashMap;
import java.util.Map;
public class Main {
static class Book {
private final String title;
private final int year;
Book(String title, int year) { this.title = title; this.year = year; }
String getTitle() { return title; }
int getYear() { return year; }
}
public static void main(String[] args) {
Map<String, Book> byTitle = new HashMap<>();
byTitle.put("Dune", new Book("Dune", 1965));
byTitle.put("Beloved", new Book("Beloved", 1987));
Book found = byTitle.get("Dune");
System.out.println(found.getYear());
System.out.println(byTitle.containsKey("1984"));
}
}
How a Map finds a key without scanning
A HashMap does not store its entries in a single line. It feeds the key through a hash function, which turns it into a number, and uses that number to choose a bucket where the entry lives. To find a key later, it hashes the same key again, goes straight to that bucket, and compares only the handful of entries there.
That is why get is close to constant time no matter how many thousands of books you stored — the hash skips the scan altogether. The trade-off is that a HashMap remembers no order: iterate one and the entries come out in whatever bucket order they happen to occupy, which is why you should never depend on a HashMap's iteration order.
Map lookups do not scan. Predict the exact output (three lines) of these operations on the stock map.
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void main(String[] args) {
Map<String, Integer> stock = new HashMap<>();
stock.put("Dune", 3);
stock.put("Beloved", 0);
stock.put("The Halo", 2);
System.out.println(stock.get("Dune"));
System.out.println(stock.getOrDefault("1984", 0));
System.out.println(stock.size());
}
}
get("Dune") returns the value stored under that key, which is 3.
"1984" was never put in, so getOrDefault returns the fallback 0.
size() counts the keys, and there are three of them.
Ordering: sort with a Comparator
A List remembers the order you added things, which is rarely the order you want to display them. Sorting rearranges the list by a rule you supply. That rule is a Comparator — a small object whose compare(a, b) returns a negative number if a should come first, zero if they tie, and a positive number if a should come second.
You rarely write that logic by hand. Comparator.comparingInt(Book::getYear) builds a comparator that orders books by their year, and books.sort(...) uses it to reorder the list in place. After the call the same List object holds the same books, merely arranged differently — which is why printing it afterwards shows the sorted order.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Main {
static class Book {
private final String title;
private final int year;
Book(String title, int year) { this.title = title; this.year = year; }
String getTitle() { return title; }
int getYear() { return year; }
}
public static void main(String[] args) {
List<Book> books = new ArrayList<>();
books.add(new Book("Beloved", 1987));
books.add(new Book("Dune", 1965));
books.add(new Book("The Halo", 1977));
books.sort(Comparator.comparingInt(Book::getYear));
for (Book b : books) {
System.out.println(b.getTitle() + " " + b.getYear());
}
}
}
flowchart TD
B["two books, a and b"] --> CMP["Comparator.compare(a, b)"]
CMP --> R{"result"}
R -->|"negative"| O1["a before b"]
R -->|"zero"| O2["equal - order unchanged"]
R -->|"positive"| O3["a after b"]
style CMP fill:#3776ab,color:#fff
Sorted oldest first. The books are added out of year order, then sorted by year ascending. Predict the exact output (three lines).
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class Main {
static class Book {
private final String title;
private final int year;
Book(String title, int year) { this.title = title; this.year = year; }
String getTitle() { return title; }
int getYear() { return year; }
}
public static void main(String[] args) {
List<Book> books = new ArrayList<>();
books.add(new Book("Beloved", 1987));
books.add(new Book("Dune", 1965));
books.add(new Book("The Halo", 1977));
books.sort(Comparator.comparingInt(Book::getYear));
for (Book b : books) {
System.out.println(b.getTitle() + " " + b.getYear());
}
}
}
The sort key is the year, so the smallest year comes first.
1965 (Dune) is smallest, then 1977 (The Halo), then 1987 (Beloved).
Each line prints the title, a space, then the year.
You sort a list with a Comparator and two books tie on the sort key (compare returns 0). What decides their relative order in the result?
Java's List.sort is stable: when two elements compare as equal, they stay in the order they had before the sort. That is why distinct sort keys give a fully predictable result, and why a tie never turns into random noise.
The trap: String order is case-sensitive
Sort a list of titles and you might expect plain alphabetical order. You will not get it. Java's natural ordering for String compares character codes, and every uppercase letter has a lower code than every lowercase one — B is 66, a is 97. So a list of apple, Banana, Cherry sorts to Banana, Cherry, apple, because both capitalised words outrank the lowercase one.
This is not a bug; it is the documented behaviour of String.compareTo. When you want true alphabetical order, say so explicitly: pass String.CASE_INSENSITIVE_ORDER, or build a comparator with a case-insensitive key. Never assume that sorted text will look the way a human would shelve it.
The case-sensitivity trap. These three titles are sorted with Collections.sort. Predict the exact output (three lines) — it is not the order a librarian would expect.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> titles = new ArrayList<>();
titles.add("apple");
titles.add("Banana");
titles.add("Cherry");
Collections.sort(titles);
for (String t : titles) {
System.out.println(t);
}
}
}
String order compares character codes, and uppercase letters come before lowercase.
B (66) and C (67) are both smaller than a (97).
So both capitalised words sort before 'apple', leaving it last.
Recap
- Choose by the question you ask: an
ArrayListfor ordered, scannable collections; aHashMapfor direct lookup by a unique key. - Searching a
Listis a linear scan — test each element, keep or skip — fine for small collections, slow for large lookups. - Sorting uses a
Comparatorwhose result (negative, zero, positive) decides the order;List.sortis stable, so ties keep their prior positions. Stringnatural order is case-sensitive: uppercase letters sort before lowercase, so sorted titles can look wrong unless you ask explicitly for case-insensitive order.
Next you will open these classes up to extension with interfaces, so new kinds of books and new ways to search slot in without rewriting what already works.