--- title: Maps source: 'https://academia.sh/en/courses/java-standard-library/maps' course: 'The Standard Library and Streams' language: en updated: '2026-08-17T18:09:42+00:00' license: 'CC BY-SA 4.0' --- # Maps A key-value map's three promises — the key's uniqueness, the key view's liveness, a missing key giving null — come out the same across all three implementations and belong to the interface. Iteration order, null-key acceptance, and the requirement that a key be comparable, though, diverge between the hash-based and the sorted implementation. The caller's rule is put at the center for the first time: a lookup with a key that writes equals but not hashCode returns null with no exception at all, while the same key is found silently in a sorted map, because the promise used there is compareTo. 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. ```java // 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 names = new ArrayList<>(); final List> suppliers = new ArrayList<>(); Guarantee add(String name, Supplier 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 observe) { List answers = new ArrayList<>(); for (Supplier 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); } } ``` ```java // Maps.java — the interface promise of holding key-value pairs, and the hash/sorted split import java.util.*; public class Maps { static final List SOURCE = List.of("zulu", "delta", "alfa", "carli", "bravo"); static Map fill(Map 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 m = (Map) o; m.put("alfa", 99); return String.valueOf(m.size()); }); map.ask("is the key view live", o -> { Map m = (Map) o; Set 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) o).get("missing"))); map.ask("is iteration order insertion order", o -> String.valueOf(new ArrayList<>(((Map) o).keySet()) .equals(SOURCE))); map.ask("is a null key accepted", o -> { try { ((Map) 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. ```java // 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 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`, 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. ```java // 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 hash = new HashMap<>(); Map linked = new LinkedHashMap<>(); Map 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` 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 `hashCode`s 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. ```java // 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 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`. ```java // 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 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.