Collections in Java — practice with a word counter, custom keys and loan queues (and the HashMap that printed in an order I couldn’t understand)

My first word counter worked on the first try… or so I thought. I fed in the text, went through the words with a HashMap, printed the result and stared at the screen: the words came out jumbled. Not alphabetical, not in order of appearance, not by frequency. I figured I had mixed up the data by accident and spent half an hour checking the loop. The loop was fine. What I expected from a HashMap (an order) is exactly what a HashMap does not promise.

That’s the beauty of collections: each one promises different things, and most mistakes come from asking one for what another one promised. So today we practise with three programs where you’ll compare, break and fix.

If you’ve already read the collections theory, this article is for applying it: counting words with a Map and its three flavors, seeing what happens when your own objects are keys in a HashSet or a HashMap, and building loan queues and stacks with Deque and PriorityQueue. They are medium-difficulty programs. Each one comes with commented code, the output and the doubts that usually arise.

Before you start

It helps to be clear on:

• That List allows duplicates and keeps order; Set doesn’t allow duplicates; Map associates keys with values.
• That HashSet and HashMap guarantee no order at all; LinkedHash... keeps insertion order and Tree... sorts.
• That HashSet and HashMap use hashCode() to choose the bucket and equals() to decide whether it’s already there.
• That merge(key, 1, Integer::sum) is used for counting.

If any of these sounds shaky, review the theory before going on.

Program 1: word counter with Map

Counting how many times each word of a text appears is the “hello world” of Maps. We’ll do it with all three flavors at once to see what changes.

The idea

A word is a key and its number of appearances is the value. For each word in the text: if it was already in the map, we add 1; if not, we add it with 1. This can be written two ways: with merge (short) or with getOrDefault (explicit), and we’ll check that they give the same result. We’ll also store everything at once in a HashMap, a TreeMap and a LinkedHashMap to compare how each one prints.

The text is a line from Hamlet in English (no accents or special letters, and in the public domain). You can swap it for any other, but keep the words separated by spaces and in lowercase.

The code

Words.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Words {
    public static void main(String[] args) {
        String text = "to be or not to be that is the question whether it is nobler in the mind to suffer";
        String[] words = text.split(" ");

        Map<String, Integer> hash = new HashMap<>();
        Map<String, Integer> tree = new TreeMap<>();
        Map<String, Integer> linked = new LinkedHashMap<>();
        Map<String, Integer> manual = new HashMap<>();

        for (String p : words) {
            hash.merge(p, 1, Integer::sum);
            tree.merge(p, 1, Integer::sum);
            linked.merge(p, 1, Integer::sum);
            manual.put(p, manual.getOrDefault(p, 0) + 1);   // the same count, without merge
        }

        System.out.println("Words in total: " + words.length);
        System.out.println("Distinct words: " + hash.size());
        System.out.println("HashMap:       " + hash);
        System.out.println("TreeMap:       " + tree);
        System.out.println("LinkedHashMap: " + linked);
        System.out.println("Does getOrDefault give the same as merge? " + manual.equals(hash));

        String mostRepeated = null;
        int max = 0;
        for (Map.Entry<String, Integer> e : tree.entrySet()) {
            if (e.getValue() > max) {
                max = e.getValue();
                mostRepeated = e.getKey();
            }
        }
        System.out.println("Most repeated: " + mostRepeated + " (" + max + " times)");

        List<String> onlyOnce = new ArrayList<>();
        for (Map.Entry<String, Integer> e : tree.entrySet()) {
            if (e.getValue() == 1) {
                onlyOnce.add(e.getKey());
            }
        }
        System.out.println("Appear only once: " + onlyOnce);
    }
}

Output

Words in total: 19
Distinct words: 14
HashMap:       {mind=1, or=1, be=2, question=1, in=1, nobler=1, is=2, it=1, the=2, that=1, suffer=1, not=1, whether=1, to=3}
TreeMap:       {be=2, in=1, is=2, it=1, mind=1, nobler=1, not=1, or=1, question=1, suffer=1, that=1, the=2, to=3, whether=1}
LinkedHashMap: {to=3, be=2, or=1, not=1, that=1, is=2, the=2, question=1, whether=1, it=1, nobler=1, in=1, mind=1, suffer=1}
Does getOrDefault give the same as merge? true
Most repeated: to (3 times)
Appear only once: [in, it, mind, nobler, not, or, question, suffer, that, whether]

Check it by hand:

• Total and distinct: the text has 19 words, but only 14 distinct ones. The map has 14 entries because each key appears only once.
• **TreeMap:** alphabetical (be, in, is, it, mind…). It compares keys using their natural order.
• **LinkedHashMap: in order of first appearance** (to, be, or, not…). The repetition of to doesn’t change its position.
• **HashMap: yet another order, neither alphabetical nor by appearance. It’s the one that results from the hash codes, and it’s the same every time you run this program with these** words, but Java doesn’t promise it. Don’t rely on it.
• **to appears 3 times**, be, is and the twice, and the rest once.
• **manual.equals(hash):** two maps are equal if they have the same pairs, regardless of order or implementation. That’s why getOrDefault and merge give the same result.

Questions you might ask

**Why if (e.getValue() > max) and not >=?** Because we traverse the TreeMap alphabetically: with > we keep the first word that reaches the maximum and, if there’s a tie, the alphabetically smallest wins. With >= the last one of the tie would win.

**Why do I traverse with entrySet() and not with keySet() and then get?** Because entrySet() gives you the key and the value at once, in a single pass. With keySet() you’d have to look up each value with get, which is repeated work.

Which of the three do I use? HashMap if you only want to count and look up; TreeMap if you’re going to show the words sorted afterwards; LinkedHashMap if you want to respect the order in which they appeared.

And if the text has capital letters or punctuation? Then The and the would be different keys. The usual approach is to convert the text to lowercase with toLowerCase() and split with a regular expression, for example split("\\W+"), which cuts at anything that isn’t a letter.

Try it yourself

1. Swap the text for one of your own and check that the TreeMap still comes out alphabetical and the LinkedHashMap in order of first appearance.
2. Add a final line to the program that prints the words that appear more than once, in alphabetical order.

Program 2: your objects as keys

The program that explains why the set at the start of the theory claimed to have the same book twice. Here we put it through all its nuances.

The idea

We’re going to create five versions of “a book identified by its ISBN”. With the first four we’ll put two books with the same ISBN into a HashSet:

1. BareBook: without equals() or hashCode().
2. EqualsBook: only equals().
3. FullBook: equals() and hashCode().
4. RecordBook: a record, which generates them on its own.
5. MutableBook: it honors the contract, but its title field can be changed after it’s been stored.

For each one, a test method prints whether they’re equals, whether they have the same hashCode and how many elements the set ends up with. Then we use FullBook as a HashMap key to count copies, and finally we see what happens when the key changes after being stored.

The code

Keys.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

public class Keys {

    static class BareBook {
        final String isbn;
        BareBook(String isbn) { this.isbn = isbn; }
    }

    static class EqualsBook {
        final String isbn;
        EqualsBook(String isbn) { this.isbn = isbn; }

        @Override
        public boolean equals(Object o) {
            return o instanceof EqualsBook other && isbn.equals(other.isbn);
        }
    }

    static class FullBook {
        final String isbn;
        FullBook(String isbn) { this.isbn = isbn; }

        @Override
        public boolean equals(Object o) {
            return o instanceof FullBook other && isbn.equals(other.isbn);
        }

        @Override
        public int hashCode() {
            return Objects.hash(isbn);
        }

        @Override
        public String toString() {
            return "Book " + isbn;
        }
    }

    record RecordBook(String isbn) { }

    static class MutableBook {
        private String title;
        MutableBook(String title) { this.title = title; }
        void setTitle(String title) { this.title = title; }

        @Override
        public boolean equals(Object o) {
            return o instanceof MutableBook other && title.equals(other.title);
        }

        @Override
        public int hashCode() {
            return title.hashCode();
        }

        @Override
        public String toString() {
            return title;
        }
    }

    static void test(String name, Object a, Object b) {
        Set<Object> set = new HashSet<>();
        set.add(a);
        set.add(b);
        System.out.println(name + ": equals=" + a.equals(b)
                + ", same hashCode=" + (a.hashCode() == b.hashCode())
                + ", set size=" + set.size());
    }

    public static void main(String[] args) {
        System.out.println("== Two objects with the same ISBN ==");
        test("Nothing       ", new BareBook("L-101"), new BareBook("L-101"));
        test("Only equals   ", new EqualsBook("L-101"), new EqualsBook("L-101"));
        test("equals+hash   ", new FullBook("L-101"), new FullBook("L-101"));
        test("record        ", new RecordBook("L-101"), new RecordBook("L-101"));

        System.out.println("== As a HashMap key ==");
        Map<FullBook, Integer> copies = new HashMap<>();
        copies.merge(new FullBook("L-101"), 1, Integer::sum);
        copies.merge(new FullBook("L-102"), 1, Integer::sum);
        copies.merge(new FullBook("L-101"), 1, Integer::sum);
        System.out.println("Copies: " + copies);

        System.out.println("== A key that changes after being stored ==");
        MutableBook book = new MutableBook("Dune");
        Set<MutableBook> shelf = new HashSet<>();
        shelf.add(book);
        System.out.println("Before changing the title: contains=" + shelf.contains(book));
        book.setTitle("Dune (2nd edition)");
        System.out.println("After changing it:         contains=" + shelf.contains(book)
                + ", size=" + shelf.size());
        System.out.println("But traversing it, it's still there: " + shelf);
    }
}

Output

== Two objects with the same ISBN ==
Nothing       : equals=false, same hashCode=false, set size=2
Only equals   : equals=true, same hashCode=false, set size=2
equals+hash   : equals=true, same hashCode=true, set size=1
record        : equals=true, same hashCode=true, set size=1
== As a HashMap key ==
Copies: {Book L-101=2, Book L-102=1}
== A key that changes after being stored ==
Before changing the title: contains=true
After changing it:         contains=false, size=1
But traversing it, it's still there: [Dune (2nd edition)]

Check it by hand:

• Nothing: no equals and not the same hash. Two different objects as far as Java is concerned: size 2.
• **Only equals:** equals gives true, but the hash is still different. The HashSet looks at the hash first to choose the bucket, so it never even finds out they’re equal: size 2. This is the most treacherous bug, because the code looks correct.
• **equals + hashCode:** the full contract. Size 1.
• **record:** the same as the previous one, without writing anything. It compares all the fields (here there’s only one).
• **HashMap with FullBook keys:** the two L-101s are recognized as the same key and merge adds up: L-101=2, L-102=1.
• Key that changes: the book is still inside the set (size=1, and it shows up when traversing), but contains gives false. It’s a silent loss.

Questions you might ask

**Why isn’t equals() enough?** Because HashSet and HashMap first use hashCode() to decide which bucket to look in and only compare with equals() the objects that are in that bucket. If two equal objects have different hashes, they are never compared.

**And if I always make hashCode() return 1?** It honors the contract, but every element would land in the same bucket and the HashSet would become slow, almost as slow as walking a list. A good hash spreads things out.

**Which fields do I use for equals() and hashCode()? The ones that identify** the object. For a book, the ISBN; for a person, maybe the ID number. And the same ones in both methods. Objects.hash(...) and Objects.equals(...) help you write them without worrying about nulls.

How do I avoid the changing-key problem? Use immutable keys: final fields and no setters. A record, a String or an Integer are good candidates precisely for that reason.

Try it yourself

1. Add to FullBook a second title field that does not go into equals() or hashCode(). Check that two books with the same ISBN and different titles are still the same.
2. Change RecordBook so it has two fields (isbn and title) and check that now two books with the same ISBN and different titles are not equal. Why?

Program 3: loan queues and stacks

The library also has queues: of people waiting, of returned books and of reservations with priority. Three structures, three behaviors.

The idea

• A queue (FIFO, first in, first out): the first to arrive is the first to leave. It’s the line of members waiting to be served.
• A stack (LIFO, last in, first out): the last one in is the first one out. It’s the cart of returned books: the one you left on top is the one you pick up first.
• A priority queue: it doesn’t matter who arrived first, the most urgent one leaves first. To know what “most urgent” means, Reservation implements Comparable (you saw it in the Comparable theory).

We build both the queue and the stack with the same type, ArrayDeque, which is a double-ended queue. It uses one set of methods or another depending on whether you want it as a queue or as a stack.

The code

QueueDemo.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

public class QueueDemo {

    record Reservation(String member, int priority) implements Comparable<Reservation> {
        @Override
        public int compareTo(Reservation other) {
            return Integer.compare(priority, other.priority);   // lower number = more urgent
        }
    }

    public static void main(String[] args) {
        // 1. Queue (FIFO): the first to arrive is the first to leave
        Deque<String> waiting = new ArrayDeque<>();
        waiting.offer("Ana");
        waiting.offer("Luis");
        waiting.offer("Marta");
        System.out.println("Queue: " + waiting);
        System.out.println("Who is first (peek): " + waiting.peek());
        System.out.println("I serve (poll): " + waiting.poll());
        System.out.println("Queue now: " + waiting);

        // 2. Stack (LIFO): the last to arrive is the first to leave
        Deque<String> returned = new ArrayDeque<>();
        returned.push("Dune");
        returned.push("Emma");
        returned.push("Hamlet");
        System.out.println("Stack: " + returned);
        System.out.println("Top (peek): " + returned.peek());
        System.out.println("I reshelve (pop): " + returned.pop());
        System.out.println("Stack now: " + returned);

        // 3. Priority queue: the "smallest" according to compareTo leaves first
        PriorityQueue<Reservation> reservations = new PriorityQueue<>();
        reservations.add(new Reservation("Pablo", 3));
        reservations.add(new Reservation("Lucía", 1));
        reservations.add(new Reservation("Irene", 2));
        reservations.add(new Reservation("Mario", 5));
        System.out.println("Printing it doesn't sort it: " + reservations);
        System.out.println("Service order:");
        while (!reservations.isEmpty()) {
            System.out.println("  " + reservations.poll());
        }

        // 4. Empty queues and stacks
        Deque<String> empty = new ArrayDeque<>();
        System.out.println("poll() on an empty queue: " + empty.poll());
        try {
            empty.pop();
        } catch (NoSuchElementException e) {
            System.out.println("pop() on an empty stack: " + e.getClass().getSimpleName());
        }
    }
}

Output

Queue: [Ana, Luis, Marta]
Who is first (peek): Ana
I serve (poll): Ana
Queue now: [Luis, Marta]
Stack: [Hamlet, Emma, Dune]
Top (peek): Hamlet
I reshelve (pop): Hamlet
Stack now: [Emma, Dune]
Printing it doesn't sort it: [Reservation[member=Lucía, priority=1], Reservation[member=Pablo, priority=3], Reservation[member=Irene, priority=2], Reservation[member=Mario, priority=5]]
Service order:
  Reservation[member=Lucía, priority=1]
  Reservation[member=Irene, priority=2]
  Reservation[member=Pablo, priority=3]
  Reservation[member=Mario, priority=5]
poll() on an empty queue: null
pop() on an empty stack: NoSuchElementException

Check it by hand:

• Queue: Ana, Luis, Marta go in in that order; peek() looks at the front without removing, poll() removes it and the queue is left as [Luis, Marta].
• Stack: Dune, Emma, Hamlet go in in that order, but the stack prints with Hamlet in front (the top). pop() returns Hamlet, the last one in.
• Priority queue: when printed, it does not come out sorted (Pablo with priority 3 appears before Irene with 2). Only the first one is guaranteed to be the smallest. But when taking out with poll() everything comes out in order: 1, 2, 3, 5.
• Empty ones: poll() on an empty queue gives null; pop() on an empty stack throws NoSuchElementException.

Questions you might ask

**Why do peek() and poll() return null instead of an exception?** Because they are designed for the normal case “maybe there’s nobody”. Their versions that throw an exception (element() and remove()) exist for when an empty queue is an error. pop(), on the other hand, does throw an exception.

What happens if two reservations have the same priority? The order between them is not guaranteed. If the tie matters, add a second criterion to compareTo (for example, arrival time).

**Why isn’t a PriorityQueue printed sorted?** Inside, it’s a heap: a structure that only guarantees the smallest is at the front, not that everything is sorted. If you want to go through it in order, you have to take elements out with poll().

**Can I traverse a queue with a for-each?** Yes, but in the structure’s internal order (the one it prints). For ArrayDeque that’s the expected one; for PriorityQueue, it isn’t.

Try it yourself

1. Change Reservation so that, on equal priority, the member whose name comes first alphabetically is served first. Hint: compareTo with two criteria.
2. Make the waiting queue a priority queue using a PriorityQueue<String> and check in what order it serves Ana, Luis and Marta. Why that order?

Typical mistakes in this practice

• **Expecting an order from a HashMap or HashSet**: none is guaranteed. Use LinkedHash... or Tree....
• **Doing map.put(w, map.get(w) + 1)** without checking whether it exists: NullPointerException the first time. Use merge or getOrDefault.
• **Overriding only equals()** (or only hashCode()): HashSet and HashMap misbehave without warning.
• Changing a field that is part of the hash of an object that is already inside a HashSet or a HashMap: it gets lost without an error.
• Mixing queue and stack methods (add with pop): the order comes out reversed.
• **Expecting a PriorityQueue to print sorted**: only poll() hands things over in order.

Watch it step by step in Python Tutor

Python Tutor runs the code line by line and draws variables, arrays and references. Choose Java. Here’s how an ArrayDeque works inside: a circular array with a head index, where taking out the first one doesn’t force anyone to move.

public class Tutor {
    public static void main(String[] args) {
        String[] queue = new String[4];
        int head = 0;
        int count = 0;

        String[] arrive = {"Ana", "Luis", "Marta"};
        for (String s : arrive) {                          // offer() of three people
            queue[(head + count) % queue.length] = s;
            count++;
        }

        String served = queue[head];                    // poll(): the first one leaves
        queue[head] = null;
        head = (head + 1) % queue.length;
        count--;

        queue[(head + count) % queue.length] = "Pablo";  // offer(): takes the last slot
        count++;
        queue[(head + count) % queue.length] = "Irene";  // offer(): wraps back to the start
        count++;

        System.out.println(served + " has been served");
        for (int i = 0; i < count; i++) {
            System.out.println(queue[(head + i) % queue.length]);
        }
    }
}

Expected output:

Ana has been served
Luis
Marta
Pablo
Irene

What to watch, step by step:

1. After the first for, queue holds Ana, Luis, Marta and a gap (null) at the end. head is 0 and count, 3.
2. In the “poll”, served receives "Ana", her slot becomes null and head moves to 1. Nobody moved: Luis and Marta are still in exactly the same positions of the array.
3. Pablo is stored at (1 + 2) % 4 = 3, the last slot of the array.
4. Irene is stored at (1 + 3) % 4 = 0: the index wraps around and reuses the slot Ana left behind. The array ends up as [Irene, Luis, Marta, Pablo], but the real order of the queue, which reads starting from head, is Luis, Marta, Pablo, Irene.

Summary

• **Map** associates keys with values; merge(key, 1, Integer::sum) is the short way to count, and getOrDefault the explicit one.
• **HashMap promises no order; LinkedHashMap respects insertion and TreeMap** sorts by key.
• **HashSet and HashMap require consistent equals() and hashCode()** on the keys: the hash chooses the bucket and equals decides. With only one of the two, duplicates appear.
• Keys should be immutable: if you change what goes into the hash, the element “disappears” from lookups.
• **ArrayDeque** works as a queue (offer/poll) and as a stack (push/pop); **PriorityQueue** always takes out the smallest according to Comparable (or a Comparator).

Checklist: have you practised it?

• [ ] I’ve compiled and run the three programs.
• [ ] I’ve checked at least one output of each program by hand.
• [ ] I’ve seen that HashMap, TreeMap and LinkedHashMap print in different orders.
• [ ] I’ve reproduced the “only equals” case and I understand why the set gives 2.
• [ ] I’ve seen that a key that changes can no longer be found.
• [ ] I’ve checked that a printed PriorityQueue doesn’t come out sorted, but poll() does.
• [ ] I’ve looked at the Python Tutor program and seen how the index wraps around the array.

And now, on to the exercises: collections exercises, with three levels, three fragments to debug and a cheat sheet at the end. See you there!

Next step: exercisesCollections in Java — exercises with authors, catalogs and a merge of two libraries (and the “b” that was in the map but never showed up)

Did this article help you? Here is how you can support SergioLearns →