Ordered collections

Open a dictionary. The words are not in the order someone thought of them. They are in alphabetical order, and that is the whole reason you can flip to "mango" without reading from "apple". The order is the feature.

Last lesson's HashMap and HashSet are the opposite. They make no promise about order at all. That is fine when you only look things up. It is not fine when you need to print a leaderboard, show names from A to Z, or answer "which is the nearest price below my budget?"

Java gives you two families for this.

• Insertion order. LinkedHashMap and LinkedHashSet remember the order you added things in, like a diary.
• Sorted order. TreeMap and TreeSet keep their keys sorted, like a dictionary.

This lesson covers both, and the two helpers that tell Java what "sorted" means: Comparable and Comparator.

Remember: HashMap has no order. LinkedHashMap keeps the order you added. TreeMap keeps its keys sorted.

A TreeMap keeps its keys in a tree, which is a set of boxes joined from a top box downwards. Each box has at most two children. The rule is simple: everything on the left is smaller than the box, and everything on the right is bigger.

Search for "Meera" in the picture. Start at the top, "Kiran". Meera comes after Kiran, so go right. You reach "Ravi". Meera comes before Ravi, so go left, and there she is. You never looked at "Asha", and with a tree of a million names, each step ignores about half of what is left. That is why a sorted tree finds things in a handful of steps.

Reading the tree from left to right gives the keys in sorted order for free. That is how TreeMap can print itself alphabetically.

A LinkedHashMap works differently. It is an ordinary hash map, so lookups stay quick, with a chain of links running through its entries in the order they were added. The chain gives it a memory of the order.

Every block below can be pasted into jshell. First, the diary: a LinkedHashMap.

Map<String, Integer> visits = new LinkedHashMap<>();
visits.put("Ravi", 2);
visits.put("Asha", 5);
visits.put("Meera", 1);
visits.put("Ravi", 3); // a second put on an existing key keeps its place
System.out.println(visits);

{Ravi=3, Asha=5, Meera=1}

The entries come out in the order they were first added. The second put for "Ravi" changed his value, but he kept his place. This map is the one to pick when you want hash-map speed and a predictable order, for example to print things the way the user entered them.

Now the dictionary: a TreeMap.

TreeMap<String, Integer> marks = new TreeMap<>();
marks.put("Ravi", 72);
marks.put("Asha", 91);
marks.put("Meera", 65);
marks.put("Kiran", 80);
System.out.println(marks);
System.out.println(marks.firstKey());
System.out.println(marks.lastKey());

{Asha=91, Kiran=80, Meera=65, Ravi=72}
Asha
Ravi

Whatever order you add keys in, they come out sorted, here from A to Z. firstKey and lastKey give you the two ends at once. Keys of type String sort alphabetically and keys of type Integer sort from smallest to biggest, because those classes already know how to sort themselves.

A sorted map can do more than a hash map, because "next to" means something. These calls look for the neighbours of a key, even one that isn't stored:

TreeMap<String, Integer> marks = new TreeMap<>();
marks.put("Asha", 91);
marks.put("Kiran", 80);
marks.put("Meera", 65);
marks.put("Ravi", 72);
System.out.println(marks.floorKey("L"));   // the nearest key at or before "L"
System.out.println(marks.ceilingKey("L")); // the nearest key at or after "L"
System.out.println(marks.headMap("Meera")); // every key before "Meera"
System.out.println(marks.floorKey("A"));   // nothing comes before "Asha"

Kiran
Meera
{Asha=91, Kiran=80}
null

floorKey("L") is the biggest key that is not past "L", so Kiran. ceilingKey("L") is the smallest key from "L" onwards, so Meera. headMap("Meera") is everything before Meera. When nothing qualifies, you get null, as with floorKey("A"). TreeSet has the same ideas under the names floor, ceiling, lower and higher.

Teaching Java how to sort your own class

How does Java know that "Asha" comes before "Kiran"? String has a method that compares itself with another string. For your own classes you have to supply that rule, in one of two ways.

The first is Comparable. You make the class say how its objects sort by default, by adding a compareTo method. It returns a negative number if this object comes first, zero if they tie, and a positive number if this one comes later.

// Comparable: "this is how objects of this class sort by default".
record Result(String name, int marks) implements Comparable<Result> {
    @Override
    public int compareTo(Result other) {
        return Integer.compare(marks, other.marks);
    }
}

Integer.compare(a, b) does the subtraction safely. (Writing marks - other.marks can overflow with big numbers, so use compare.) A record, the short class form from lesson 7, can implement an interface just like any class.

List<Result> results = new ArrayList<>();
results.add(new Result("Ravi", 72));
results.add(new Result("Asha", 91));
results.add(new Result("Meera", 65));
results.sort(null); // null means "use the natural order", the compareTo above
for (Result r : results) {
    System.out.println(r.name() + " " + r.marks());
}

Meera 65
Ravi 72
Asha 91

results.sort(null) means "sort with the natural order", which is our compareTo: lowest marks first.

But a class can have only one natural order. What if you want highest marks first, or sort by name this time? The second tool is a Comparator, a separate little object that holds a sorting rule. You can make as many as you like, and pass one in when you need it.

List<Result> results = new ArrayList<>();
results.add(new Result("Ravi", 72));
results.add(new Result("Asha", 72));
results.add(new Result("Meera", 91));

// Highest marks first, and for a tie, by name from A to Z.
Comparator<Result> ranking = Comparator.comparingInt(Result::marks).reversed()
        .thenComparing(Result::name);
results.sort(ranking);
for (Result r : results) {
    System.out.println(r.name() + " " + r.marks());
}

Meera 91
Asha 72
Ravi 72

Read the comparator like a sentence: compare by marks, reversed() so the biggest comes first, and thenComparing the name to break ties. Asha and Ravi both have 72, so the name decides, and Asha comes first. Comparator.comparingInt(...) takes a method reference (the Result::marks shorthand from lesson 6) which says what to compare.

There is one trap with sorted sets and maps. They decide that two things are the same by asking the comparator, not equals:

// This comparator says two names are "the same" when they are equally long.
TreeSet<String> names = new TreeSet<>(Comparator.comparingInt(String::length));
names.add("Asha");
names.add("Ravi");  // same length as Asha, so the set thinks it is already there
names.add("Meera");
System.out.println(names);
System.out.println(names.size());

[Asha, Meera]
2

"Asha" and "Ravi" are both four letters long, so this comparator says they tie, and the TreeSet treats "Ravi" as a duplicate and quietly refuses it. Your comparator must tell apart everything you want to keep as separate. For safety, make a comparator end with a tie-breaker, such as thenComparing(Result::name).

Remember: Comparable is the one natural order a class carries. A Comparator is a sorting rule you hand in. In a TreeSet, "compares as equal" means "is a duplicate".

The real TreeMap uses a red-black tree, a tree that rebalances itself so it never leans too far to one side. Rebalancing is fiddly, so here is the plain version without it. It shows the idea, which is the same.

static class TinySortedSet<T extends Comparable<T>> {
    private static class Node<T> {
        final T value;
        Node<T> left;  // everything smaller than value
        Node<T> right; // everything bigger than value

        Node(T value) {
            this.value = value;
        }
    }

    private Node<T> root;
    private int size = 0;

    int size() {
        return size;
    }

    boolean add(T value) {
        if (root == null) {
            root = new Node<>(value);
            size++;
            return true;
        }
        Node<T> current = root;
        while (true) {
            int order = value.compareTo(current.value);
            if (order == 0) {
                return false; // compareTo says it is already here
            }
            if (order < 0) {
                if (current.left == null) {
                    current.left = new Node<>(value);
                    size++;
                    return true;
                }
                current = current.left;
            } else {
                if (current.right == null) {
                    current.right = new Node<>(value);
                    size++;
                    return true;
                }
                current = current.right;
            }
        }
    }

    boolean contains(T value) {
        Node<T> current = root;
        while (current != null) {
            int order = value.compareTo(current.value);
            if (order == 0) {
                return true;
            }
            // Each step throws away one whole side of the tree.
            current = order < 0 ? current.left : current.right;
        }
        return false;
    }

    List<T> toList() {
        List<T> out = new ArrayList<>();
        walk(root, out);
        return out;
    }

    // left side, then this node, then right side: that is sorted order
    private void walk(Node<T> node, List<T> out) {
        if (node == null) {
            return;
        }
        walk(node.left, out);
        out.add(node.value);
        walk(node.right, out);
    }
}

Go through it in order.

• Each Node holds a value and two links, left for smaller things and right for bigger things.
• add starts at the top, compares the new value with the node it is standing on, and goes left or right. When it finds an empty spot, it hangs the new node there. If compareTo returns 0, the value is already present and nothing is added.
• contains follows the same walk. Every step drops one whole side of the tree.
• toList visits the left side, then the node itself, then the right side. That is called an in-order walk, and it comes out sorted. The method calls itself, which is called recursion: each call handles one smaller piece of the tree.
• The T extends Comparable<T> in the class line is a promise that anything stored knows how to compare itself.

TinySortedSet<String> names = new TinySortedSet<>();
for (String name : new String[] {"Kiran", "Asha", "Ravi", "Meera", "Asha"}) {
    names.add(name);
}
System.out.println(names.toList());
System.out.println(names.contains("Meera"));
System.out.println(names.contains("Zoya"));
System.out.println(names.size());

[Asha, Kiran, Meera, Ravi]
true
false
4

"Asha" was added twice and counted once. The names come out sorted, though they were added in a different order. The catch of this plain version: if you add names that are already sorted, every one goes right, and the tree becomes a long line, as slow as a list. Self-balancing trees such as the red-black tree exist to prevent that.

LinkedHashMap, meanwhile, is a HashMap plus a doubly linked list of its entries, the same pair of links you saw in lesson 4. Looking up uses the hash part and walking uses the list part.

O(log n) means the number of steps grows very slowly: about doubling the data adds one step. It is a little slower than a hash map's O(1) and gives you sorted order and neighbour searches in return. Pick TreeMap only when you need the order.

static List<Result> rank(List<Result> results) {
    throw new UnsupportedOperationException("highest marks first; ties by name, A to Z");
}

static List<Result> rank(List<Result> results) {
    List<Result> ranked = new ArrayList<>(results); // sort a copy, leave the caller's list alone
    ranked.sort(Comparator.comparingInt(Result::marks).reversed().thenComparing(Result::name));
    return ranked;
}

static Integer bestFit(TreeSet<Integer> prices, int budget) {
    throw new UnsupportedOperationException("the dearest price you can still afford, or null");
}

static Integer bestFit(TreeSet<Integer> prices, int budget) {
    return prices.floor(budget); // the biggest price that is <= budget, or null
}

static class LruCache<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;

    LruCache(int capacity) {
        throw new UnsupportedOperationException("keep at most capacity entries, dropping the least recently used");
    }
}

static class LruCache<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;
    private final int capacity;

    LruCache(int capacity) {
        // true = order the entries by when they were last used, not when they were added
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity; // called after every put; true drops the oldest
    }
}

• "HashMap, LinkedHashMap or TreeMap?" HashMap when order doesn't matter. LinkedHashMap when you need insertion order, or to build a cache. TreeMap when you need sorted keys, or ranges and neighbours. Give one reason for each.
• "What data structure is a TreeMap?" A red-black tree, which is a self-balancing binary search tree. Say "balanced", which is why it stays O(log n).
• "Comparable or Comparator?" Comparable is the one natural order that sits inside the class. A Comparator is outside the class, so you can have many and choose per sort. Sorting by something that isn't the natural order needs a Comparator.
• "What should compareTo be consistent with?" equals. If compareTo returns 0 for two objects that equals calls different, a TreeSet will treat them as one. The earlier gotcha is exactly that.
• "Can a TreeMap take a null key?" Not with natural ordering, since null can't be compared. It throws a NullPointerException. A HashMap allows one null key.
• "How would you build an LRU cache?" A LinkedHashMap with access order on, overriding removeEldestEntry. Problem 3 is that answer. A good follow-up mention is that it is not thread-safe.
• Say the cost. "Hash map: O(1) on average. Tree map: O(log n), and sorted. Linked hash map: O(1) on average, in insertion order."

Made by VeraStack Labs