Choosing a collection
The collections part of the course ends with the question a program asks before it holds any data: which of the four shapes is this. A List is an order with positions, a Set is membership, a Map is a lookup by key and a Deque is both ends. The question is answered by what the code does with the data, and the cost of the operations follows from the shape.
The four shapes
Each shape answers one question well, and the wrong choice is visible in the code before it is visible in a profile. A list that is searched with a loop is a set that was not named. A map that is iterated to find one value is a lookup that was not used. A list that has elements added at the front is a deque that was not named, and the same operation on the list is quadratic.
The four interfaces are the part of a signature that matters: List<Name>, Set<Word>, Map<Id, Order> and Deque<Task> each say what the code promises. An ArrayList in a field is a decision about cost, and it can be changed without touching a caller when the field is named by its interface.
Measured here
The membership test is the operation that separates a list from a set, so it is the one to measure. The program builds 20,000 integers in four collections, asks each one 20,000 times whether it contains a value, and prints the best of three rounds in milliseconds:
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.TreeSet;
public class Measured {
static final int SIZE = 20_000;
static final int PROBES = 20_000;
public static void main(String[] args) {
List<Integer> values = new ArrayList<>();
for (int i = 0; i < SIZE; i++) {
values.add(i);
}
System.out.printf("arraylist %.1f ms%n", best(values));
System.out.printf("hashset %.1f ms%n", best(new HashSet<>(values)));
System.out.printf("treeset %.1f ms%n", best(new TreeSet<>(values)));
System.out.printf("linkedset %.1f ms%n", best(new LinkedHashSet<>(values)));
}
static double best(Collection<Integer> values) {
double best = Double.MAX_VALUE;
for (int round = 0; round < 3; round++) {
best = Math.min(best, contains(values));
}
return best;
}
static double contains(Collection<Integer> values) {
long start = System.nanoTime();
int found = 0;
for (int i = 0; i < PROBES; i++) {
if (values.contains(i * 7 % SIZE)) {
found++;
}
}
double ms = (System.nanoTime() - start) / 1_000_000.0;
if (found < 0) {
System.out.println(found);
}
return ms;
}
}
javac -Xlint:all Measured.java
java Measured
arraylist 244.3 ms
hashset 3.3 ms
treeset 5.7 ms
linkedset 5.0 ms
The list is about seventy times slower than the hash set, because every contains on a list walks until it finds the value, so the work grows with the size. The numbers depend on the machine and the run; the order does not, and the order is the lesson: membership belongs to a set.
The cost table
The operations, by structure. A n is the number of elements.
ArrayList: get(i) and add at the end are constant time (amortised), add(0, x) and remove(i) are linear, contains is linear. LinkedList: add and remove at either end are constant, get(i) is linear, and it costs a node per element. HashSet: add, remove and contains are constant on average, with no order. LinkedHashSet: the same, plus the insertion order at the cost of the links. TreeSet: those three are logarithmic and the elements are sorted. HashMap and LinkedHashMap: put, get and remove are constant on average. TreeMap: logarithmic, sorted, with range queries. ArrayDeque: both ends are constant, and it is the queue and the stack.
The constant-time claim of a hash collection assumes a hash function that spreads the keys. A class whose hashCode answers the same number for everything turns a HashSet into a list, which is lesson 080 from another side.
A structure per task
Four small tasks, each with the structure its question needs. The words of a line, the counts of those words, the two most recent items and an ordered copy for the report:
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Pick {
public static void main(String[] args) {
Set<String> unique = new LinkedHashSet<>();
for (String word : "a b a c b".split(" ")) {
unique.add(word);
}
System.out.println("set: " + unique);
Map<String, Integer> counts = new LinkedHashMap<>();
for (String word : "a b a c b".split(" ")) {
counts.merge(word, 1, Integer::sum);
}
System.out.println("map: " + counts);
Deque<String> recent = new ArrayDeque<>();
for (String word : "a b c".split(" ")) {
recent.push(word);
if (recent.size() > 2) {
recent.removeLast();
}
}
System.out.println("deque: " + recent);
List<String> ordered = new ArrayList<>(unique);
ordered.sort(null);
System.out.println("list: " + ordered);
}
}
javac -Xlint:all Pick.java
java Pick
set: [a, b, c]
map: {a=2, b=2, c=1}
deque: [c, b]
list: [a, b, c]
The set answers which words appeared and in which order they were first seen, because it is a LinkedHashSet; the map answers how many times; the deque keeps the two most recent, newest first; and the list is the sorted copy a report prints. ordered.sort(null) sorts by the natural order, which is the same as passing Comparator.naturalOrder().
What only a sorted map can do
A TreeMap implements NavigableMap, and that interface is the reason to choose it: it can answer a question about a range of keys without walking them. The program below picks a grade for a score by finding the best key at or below it:
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;
public class Range {
public static void main(String[] args) {
NavigableMap<Integer, String> scores = new TreeMap<>();
scores.put(90, "A");
scores.put(80, "B");
scores.put(70, "C");
scores.put(60, "D");
System.out.println(scores.firstKey() + " is the lowest");
System.out.println(scores.floorKey(85) + " is the best key at or below 85");
System.out.println(scores.headMap(80, true));
System.out.println(scores.descendingMap());
System.out.println(grade(scores, 73) + " for 73");
}
static String grade(NavigableMap<Integer, String> scores, int score) {
Map.Entry<Integer, String> entry = scores.floorEntry(score);
return entry == null ? "none" : entry.getValue();
}
}
javac -Xlint:all Range.java
java Range
60 is the lowest
80 is the best key at or below 85
{60=D, 70=C, 80=B}
{90=A, 80=B, 70=C, 60=D}
C for 73
floorKey and floorEntry are binary searches in the tree, so the answer is found in logarithmic time and no loop over the grades appears in the program. A HashMap would need a scan of every key for the same question, and a TreeMap that is not asked such a question is a cost paid for nothing.
Exercises
- Change the list of Measured to a LinkedList and run the program again.
- Keep a set of the words of a paragraph and print its size, then the same with a list and a loop that checks for duplicates.
- Add a score of 95 to Range and print the grade for 95 and for 50.
- Choose a structure for a queue of print jobs and explain the choice in one sentence.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Which structure answers "is this value in the collection" in constant time on average?
Answer
HashSet
The hash code chooses a bucket, so the search does not grow with the size.
-
What is the cost of
get(i)on a LinkedList?Answer
Linear, because it walks the chain
A linked list has no positions to index into, so it walks from an end.
-
When is a TreeMap the right choice?
Answer
When the keys must be ordered or a range query is needed
The sorted tree pays a logarithmic cost for an order a hash map does not have.
-
What does this program print?
import java.util.ArrayList; import java.util.List; public class Q1 { public static void main(String[] args) { List<String> list = new ArrayList<>(List.of("a", "b", "a")); System.out.println(list.size()); System.out.println(list.contains("c")); System.out.println(list.indexOf("a")); } }Answer
3 / false / 0
A list keeps both a values, does not contain c, and indexOf finds the first a.
-
What does this program print?
import java.util.LinkedHashSet; import java.util.Set; public class Q2 { public static void main(String[] args) { Set<String> set = new LinkedHashSet<>(); for (String word : "b a b".split(" ")) { set.add(word); } System.out.println(set); } }Answer
[b, a]
The set drops the duplicate and keeps the order of first appearance.
-
What does this program print?
import java.util.ArrayDeque; import java.util.Deque; public class Q3 { public static void main(String[] args) { Deque<String> deque = new ArrayDeque<>(); for (String word : "a b c".split(" ")) { deque.push(word); if (deque.size() > 2) { deque.removeLast(); } } System.out.println(deque); } }Answer
[c, b]
The newest element is pushed at the head and the oldest drops off the tail.
-
What does this program print?
import java.util.Map; import java.util.TreeMap; public class Q4 { public static void main(String[] args) { Map<Integer, String> map = new TreeMap<>(); map.put(2, "b"); map.put(1, "a"); map.put(3, "c"); System.out.println(map); System.out.println(((java.util.NavigableMap<Integer, String>) map).firstKey()); } }Answer
{1=a, 2=b, 3=c} / 1
The tree orders the keys, and firstKey answers the smallest.
-
Why is a list searched with a loop a set in disguise?
Answer
The code only asks whether an element is present, which is membership
The question is membership, and a set answers it without the loop.
-
What does a field declared as
List<String>allow thatArrayList<String>does not?Answer
The implementation can be replaced without changing the callers
The interface is the promise, and the concrete class is a decision behind it.
-
Which collection would you use for a stack of undo steps?
Answer
ArrayDeque, with push and pop
A stack needs the last element back first, which is one end of a deque.
The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.
Article author: Arthur Isaev