Maps

The previous lesson measured that a list, a set, and a queue each reach an element by one of three separate paths: position, membership, the end. All three were accesses where the container was self-sufficient — finding the element required no information from outside the container. A map breaks this. In a map, an element is reached by its key, and the key can be a class the caller writes, one the library has never seen. The container only asks for the key; it does not check whether the key behaves consistently with itself. This lesson measures where that inconsistency lands: which promise comes from the library, which promise rests on the shoulders of the class the caller wrote, and how the program reports it when a crack opens between the two — or does not report it at all.

Every flaw the previous two lessons measured was instantly visible in a compiled program, or not visible at all — if an exception was thrown, it was thrown; if not, the behavior was consistent. A key flaw in a map opens a third path: the program compiles, runs, throws no exception, and still works incorrectly. This third path is not a gap in the library, it is an obligation the library leaves to the caller going unanswered.

The Interface Promise of Holding Key-Value Pairs

A map, like the previous two lessons, is tested with three implementations (HashMap, LinkedHashMap, TreeMap); the measurement engine is the same, only the questions asked in this lesson are new.

• CO11 — The engine is semantically identical to the previous two lessons; only the questions asked in this lesson are added. Adding a new question to the Guarantee class does not change the existing questions’ behavior.
• CO12 — The map is filled with five keys, in the same order, with the same fill helper.

// Guarantee.java — who gives a behavior's guarantee: the interface, or the implementation
import java.util.*;
import java.util.function.*;

public class Guarantee {
    static int byInterface = 0;
    static int byImplementation = 0;

    final List<String> names = new ArrayList<>();
    final List<Supplier<Object>> suppliers = new ArrayList<>();

    Guarantee add(String name, Supplier<Object> supplier) {
        names.add(name);
        suppliers.add(supplier);
        return this;
    }

    void header(String family) {
        StringBuilder sb = new StringBuilder(String.format("%-40s", family));
        for (String name : names) sb.append(String.format("%-15s", name));
        sb.append("guarantee giver");
        System.out.println(sb);
    }

    void ask(String question, Function<Object, String> observe) {
        List<String> answers = new ArrayList<>();
        for (Supplier<Object> u : suppliers) {
            String y;
            try {
                y = observe.apply(u.get());
            } catch (RuntimeException e) {
                y = "error";
            }
            answers.add(y);
        }
        boolean shared = new HashSet<>(answers).size() == 1;
        if (shared) byInterface++; else byImplementation++;
        StringBuilder sb = new StringBuilder(String.format("%-40s", question));
        for (String y : answers) sb.append(String.format("%-15s", y));
        sb.append(shared ? "interface" : "implementation");
        System.out.println(sb);
    }

    static void summary() {
        System.out.printf("observations: %d interface guarantees, %d implementation behaviors%n",
                byInterface, byImplementation);
    }
}

// Maps.java — the interface promise of holding key-value pairs, and the hash/sorted split
import java.util.*;

public class Maps {
    static final List<String> SOURCE = List.of("zulu", "delta", "alfa", "carli", "bravo");

    static Map<String, Integer> fill(Map<String, Integer> m) {
        for (int i = 0; i < SOURCE.size(); i++) m.put(SOURCE.get(i), i);
        return m;
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Guarantee map = new Guarantee()
                .add("HashMap", () -> fill(new HashMap<>()))
                .add("LinkedHashMap", () -> fill(new LinkedHashMap<>()))
                .add("TreeMap", () -> fill(new TreeMap<>()));
        map.header("map");
        map.ask("is the key unique", o -> {
            Map<String, Integer> m = (Map<String, Integer>) o;
            m.put("alfa", 99);
            return String.valueOf(m.size());
        });
        map.ask("is the key view live", o -> {
            Map<String, Integer> m = (Map<String, Integer>) o;
            Set<String> g = m.keySet();
            m.put("extra", 5);
            return String.valueOf(g.contains("extra"));
        });
        map.ask("what is the answer for a missing key",
                o -> String.valueOf(((Map<String, Integer>) o).get("missing")));
        map.ask("is iteration order insertion order",
                o -> String.valueOf(new ArrayList<>(((Map<String, Integer>) o).keySet())
                        .equals(SOURCE)));
        map.ask("is a null key accepted", o -> {
            try { ((Map<String, Integer>) o).put(null, 0); return "yes"; }
            catch (RuntimeException e) { return "no"; }
        });
        System.out.println();
        Guarantee.summary();
    }
}

map                                     HashMap        LinkedHashMap  TreeMap        guarantee giver
is the key unique                       5              5              5              interface
is the key view live                    true           true           true           interface
what is the answer for a missing key    null           null           null           interface
is iteration order insertion order      false          true           false          implementation
is a null key accepted                  yes            yes            no             implementation

observations: 3 interface guarantees, 2 implementation behaviors

Three rows gather in the interface column. Writing to a key a second time does not grow the size — all three stay at five keys, because the Map interface directly defines that a key will be unique. The set keySet() returns is a view bound to the container itself: the "extra" key added to the map afterward also shows up in the view taken earlier; the view is not a point-in-time copy, it is a window opened onto the container itself. The third row is a map’s most often forgotten promise: looking up a key that does not exist throws no exception, it returns null. All three separate implementations keep these three promises exactly; when choosing a map, these three can be accepted without argument.

This third promise has its own limit, and a single line is enough to see it. If the map also accepts null as a value, get returning null cannot distinguish between two separate situations: the key does not exist at all, or the key exists and its counterpart is already null.

// NullOrMissing.java — get(key) cannot tell absence apart from a null value
import java.util.*;

public class NullOrMissing {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("alfa", null);
        System.out.println("get(alfa)            : " + m.get("alfa"));
        System.out.println("get(missing)         : " + m.get("missing"));
        System.out.println("containsKey(alfa)    : " + m.containsKey("alfa"));
        System.out.println("containsKey(missing) : " + m.containsKey("missing"));
    }
}

get(alfa)            : null
get(missing)         : null
containsKey(alfa)    : true
containsKey(missing) : false

Both get calls give the same answer, null; but one describes a key that really does not exist, the other a key that exists and is deliberately bound to null. This is where get alone is not enough: to fully read the absence promise, containsKey is needed as a separate call. The interface’s promise is “a missing key returns null”; it is not “if null is returned, the key is missing” — the two are not the same proposition.

Where Hash-Based and Sorted Diverge

The table’s bottom two rows separate HashMap/LinkedHashMap from TreeMap. Iteration order looks at the keys’ hash value in HashMap, at insertion order in LinkedHashMap, at the keys’ natural order in TreeMap — all three a decision of the chosen class, not the interface. Null-key acceptance splits along the same line: HashMap and LinkedHashMap hold the null key in a single special slot, TreeMap rejects it, because placing a key requires comparing it against the existing keys, and null has no order to compare.

This last observation points to a third distinction: what TreeMap wants from a key is different from what HashMap wants. HashMap recognizes a key only through equals and hashCode; TreeMap expects an order. This is a difference that does not show up in the interface itself — both implement Map<K, V>, neither writes any extra constraint on K in its signature. The difference only surfaces at run time, when a key is placed for the first time. What happens if the key class is not sortable?

• CO13 — The same key class writes equals and hashCode fully but declares no ordering at all (does not implement Comparable). A single put call, with the same single key, is made to all three maps.

// Requirement.java — in which implementation is a sortable key required
import java.util.*;

public class Requirement {
    static class IncomparableKey {
        final String name;
        IncomparableKey(String name) { this.name = name; }
        @Override public boolean equals(Object o) {
            return o instanceof IncomparableKey a && a.name.equals(name);
        }
        @Override public int hashCode() { return name.hashCode(); }
    }

    static String attempt(Runnable action) {
        try { action.run(); return "succeeded"; }
        catch (RuntimeException e) { return e.getClass().getSimpleName(); }
    }

    public static void main(String[] args) {
        Map<IncomparableKey, Integer> hash = new HashMap<>();
        Map<IncomparableKey, Integer> linked = new LinkedHashMap<>();
        Map<IncomparableKey, Integer> sorted = new TreeMap<>();

        System.out.println("HashMap.put       : " + attempt(() -> hash.put(new IncomparableKey("a"), 1)));
        System.out.println("LinkedHashMap.put : " + attempt(() -> linked.put(new IncomparableKey("a"), 1)));
        System.out.println("TreeMap.put       : " + attempt(() -> sorted.put(new IncomparableKey("a"), 1)));
    }
}

HashMap.put       : succeeded
LinkedHashMap.put : succeeded
TreeMap.put       : ClassCastException

equals and hashCode are both fully written, nothing is missing — and the third row still collapses. HashMap and LinkedHashMap only need to know the key’s hash value and equality to place it in its slot; TreeMap, though, has to compare the key against something to place it at its position in the tree even on the first put call, and it has neither a Comparable nor a Comparator in hand. The flaw is not visible at compile time — the Map<K, V> definition puts no ordering constraint on K at all — and at run time, on the first write, it falls by its name.

The Caller’s Rule: Writing equals Without hashCode

The two sections above separated the interface’s and the implementation’s promises. A third source remains: the rule the caller’s own written key class has to follow. The Object class defines a contract — if two objects are considered equal by equals, their hashCodes must be equal too — but the compiler checks this contract nowhere. What happens when equals is written and hashCode is not?

• CO14 — The key class writes equals correctly (compares the name) and never overrides hashCode; the inherited Object.hashCode() looks at run-time identity. Two separate new calls carrying the same name produce two separate hash values.

// MismatchedKey.java — a lookup with a key that has equals but no hashCode
import java.util.*;

public class MismatchedKey {
    static class Key {
        final String name;
        Key(String name) { this.name = name; }
        @Override public boolean equals(Object o) {
            return o instanceof Key a && a.name.equals(name);
        }
        // hashCode deliberately not written
    }

    public static void main(String[] args) {
        Map<Key, Integer> store = new HashMap<>();
        store.put(new Key("alfa"), 9);
        Integer found = store.get(new Key("alfa"));
        String result = String.valueOf(found);
        System.out.printf("%-30s %-9s found=%-6s expected=9%n", "key without hashCode",
                result.equals("9") ? "succeeded" : "silent", result);
    }
}

key without hashCode           silent    found=null   expected=9

Both the writer and the searcher use the same name, "alfa"; equals would consider them equal. But HashMap consults hashCode first to decide which slot to look in, and the two separate new Key("alfa") objects, because of the default hashCode inherited from Object, almost certainly fall into two separate slots. The lookup never visits the slot the value sits in and does not even get the chance to call equals. The result is silent: no exception falls, get just returns null — as if the key was never added at all. Where the flaw shows up may not be the write line, it may be a lookup line written months later.

The three-way classification this course sorts results into — exception, silent, ineffective — is met here for the first time with a concrete example. The missing hashCode does not fall into the exception class: no line crashes, the program runs from start to finish. Had the same map been filled with thousands of keys, the flaw would still be invisible; only a wrong-seeming number of “lost” elements would appear, and finding this loss’s cause would be a bug that has to be tracked down days later, without ever touching the source.

The Bounding Measurement: The Same Key Is Found in a Sorted Map

The previous measurement seems to lead to the conclusion “this key class is broken.” The bounding measurement corrects this: the same class, the same missing hashCode, the only difference is the implementation chosen.

• CO15 — The key class is byte-for-byte identical to the one above; hashCode is still not written. The only thing that changes is that the map is a TreeMap, built with a Comparator.

// FoundInSorted.java — the same flawed key is found in a map relying on ordering
import java.util.*;

public class FoundInSorted {
    static class Key {
        final String name;
        Key(String name) { this.name = name; }
        @Override public boolean equals(Object o) {
            return o instanceof Key a && a.name.equals(name);
        }
        // hashCode deliberately not written
    }

    public static void main(String[] args) {
        Map<Key, Integer> sorted = new TreeMap<>(Comparator.comparing(a -> a.name));
        sorted.put(new Key("alfa"), 9);
        Integer found = sorted.get(new Key("alfa"));
        System.out.println("TreeMap.get, same flawed key      : " + found);
    }
}

TreeMap.get, same flawed key      : 9

The same class, the same missing method, and this time the lookup finds it. The difference is not in the key, it is in the implementation reading the key: TreeMap never looks at hashCode to find a position, it only calls the given Comparator, and that Comparator only reads the name field. This prevents the first measurement from being misread. The key class itself was not the flawed thing; the flaw was a mismatch between the promise a class gives (only equals) and the promise the chosen implementation expects (hashCode and equals together). The same key, in the hands of an implementation with different expectations, works flawlessly.

Placing these two measurements side by side brings the course’s question to exactly this point. Saying “this class is broken” when describing a flaw is, most of the time, the wrong question; the right question is “which promise does this class give, and which promise does the side reading it expect?” HashMap expects hashCode and the key does not give it — the flaw is there. TreeMap expects only an order, and the key, indirectly through a Comparator, gives it — the flaw is not there. The key class never changed; what changed was which contract the key was tested against.

Summary

• A map’s three promises — the key’s uniqueness, the key view’s liveness, a missing key returning null — came out the same across all three implementations and belonged to the interface.
• Iteration order and null-key acceptance diverged between the hash-based and the sorted implementation; at the root of the divergence is TreeMap’s requirement to compare the key.
• A key that cannot be sorted works fine in HashMap but falls with ClassCastException on the first write in TreeMap — the flaw shows up not at compile time, but at run time.
• The caller’s rule: when equals is written but hashCode is not, a lookup returns null with no exception at all; the flaw does not surface on the write line, it surfaces on the lookup line.
• Bounding measurement: the same key class with the missing method is found without trouble in a sorted map, because the promise sought there is compareTo/Comparator. The flaw was not in the key, it was in the key’s promise not matching the implementation’s expectation.

Next Step

This lesson measured whether a map can find its key; what happens, though, if the container changes while being walked? Adding a new element to the same container, or removing one, while advancing over a map or a set with for is a situation all three families run into. The next lesson measures this situation: some implementations throw an exception immediately and by name, some complete a wrong walk without saying anything at all — and which one happens is decided, again, not by the interface but by the implementation. The “the flaw compiles, runs, and silently gives the wrong result” pattern seen in this lesson will meet us there once more, for a different reason.