Collections Framework II

Course 2 · Ch 2

Map, Set, Queue — and the equals()/hashCode() contract that quietly governs all of them

java1-8 covered List. This chapter covers the rest of the framework used just as constantly — Map, Set, Queue — and the one contract every hash-based collection silently depends on.

Map — Key-Value Pairs

Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
ages.put("Bob", 25);

if (ages.containsKey("Alice")) {
    System.out.println(ages.get("Alice"));
}

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

HashMap stores key-value pairs with average constant-time put/get. Iterating a Map directly isn't possible — it's not a Collection itself — so entrySet(), keySet(), or values() supplies something iterable.

Set — Uniqueness Guaranteed

Set<String> names = new HashSet<>();
names.add("Alice");
names.add("Alice"); // silently ignored — a HashSet never holds duplicates
names.size(); // 1

HashSet guarantees no duplicate elements. "Duplicate" here is decided by equals(), not by reference identity — which is exactly why the next section matters.

The equals()/hashCode() Contract

public class Point {
    private int x, y;

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

    @Override
    public int hashCode() {  // MUST be overridden alongside equals()
        return Objects.hash(x, y);
    }
}

HashMap and HashSet use hashCode() first to find the right bucket, then equals() to confirm a real match within that bucket. Overriding equals() without also overriding hashCode() breaks this silently: two objects that equals() now says are equal can still land in different buckets, because their inherited hashCode() (identity-based by default) disagrees — a HashSet can end up holding two "equal" elements, and HashMap.get() can fail to find an entry that's genuinely there. This is a real extension of java1-2's own ==-vs-.equals() material: this contract is exactly why Java requires both methods to agree.

Queue & Deque

Queue<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
queue.poll(); // "first" — FIFO order

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
stack.pop(); // "second" — LIFO order, same ArrayDeque, used as a stack instead

ArrayDeque serves as either a FIFO Queue (offer/poll) or a LIFO stack (push/pop) — the same underlying structure, used through a different pair of methods.

Ordering Variants

HashMap/HashSet make no ordering guarantee at all. LinkedHashMap/LinkedHashSet preserve insertion order. TreeMap/TreeSet keep elements sorted, using either natural ordering (Comparable) or a supplied Comparator.

Comparators

List<String> names = new ArrayList<>(List.of("Charlie", "alice", "Bob"));
names.sort(Comparator.comparing(String::toLowerCase));
// [alice, Bob, Charlie] — case-insensitive order, without touching String's own natural ordering

Where java2-1's bounded generics relied on a type implementing Comparable itself, Comparator supplies ordering logic externally — useful precisely when the natural ordering isn't the one needed, or when the type has no natural ordering at all.

Implementation	Ordering	Typical use
HashMap / HashSet	none guaranteed	fastest general-purpose default
LinkedHashMap / LinkedHashSet	insertion order	predictable iteration order needed
TreeMap / TreeSet	sorted (natural or Comparator)	ordered traversal / range queries needed

Always override hashCode() alongside equals()

Most IDEs generate both together for exactly this reason — treat them as one unit, never override one without the other, or hash-based collections will misbehave in ways that are easy to miss in testing and hard to trace later.

Don't mutate a HashMap key's hashCode-affecting fields after insertion

If a key object's fields (the ones hashCode() depends on) change after it's already been placed in a HashMap, the entry effectively becomes unreachable via get() — it's still sitting in its original bucket, but a fresh lookup now computes a different bucket entirely.

Coding Challenges

Challenge 1

Write a HashMap<String, Integer> storing three names and ages, then iterate it with entrySet() printing each pair, and separately print the result of ages.get() on a key that doesn't exist.

📄 View solution

Challenge 2

Write a class that overrides equals() but NOT hashCode(), add two "equal" instances to a HashSet, and show the set ends up with size 2 instead of 1. Then fix it by adding a correct hashCode() override and show the size becomes 1.

📄 View solution

Challenge 3

Write a List of Strings representing names of varying length, and sort it using Comparator.comparing() by string length rather than alphabetically, printing the result.

📄 View solution

Chapter 2 Quick Reference

Map stores key-value pairs; entrySet()/keySet()/values() make it iterable
Set guarantees no duplicates, decided by equals(), not reference identity
equals() and hashCode() must always be overridden together — hash-based collections rely on both agreeing
ArrayDeque serves as either a FIFO Queue or a LIFO stack via different method pairs
HashMap/HashSet: no order; LinkedHashMap/LinkedHashSet: insertion order; TreeMap/TreeSet: sorted order
Comparator supplies external ordering logic, complementing java2-1's Comparable-based bounded generics
Next chapter: lambda expressions and functional interfaces