10.3 Map and Set Contracts

After reading the introduction to collections and List, spend about 45 minutes running the Java 17 examples here. The goal isn't to memorize a table of implementations, but to be able to design stable keys and choose between Map and Set based on equality, order, range queries, and concurrency requirements.

Use a Map for “name → quantity”

Storing names and quantities in two separate Lists hides the relationship within the same index. A Map directly expresses material -> quantity. A Set expresses whether a particular participant has already been registered, and the deduplication result depends on the equality rules of the elements.

1. Basic Reading and Updating of Maps

java

Map<String, Integer> stock = new HashMap<>();
stock.put("bolt", 50);
stock.put("nut", 30);

Integer bolts = stock.get("bolt");
boolean hasGear = stock.containsKey("gear");
int missing = stock.getOrDefault("missing", 0);

put returns the old value; when no mapping existed for the key, it returns null. remove(key) also returns the old value. If the Map allows null values, looking only at get returning null cannot distinguish between "no such key" and "the key exists but the value is null":

java

Map<String, Integer> stockWithUnknown = new HashMap<>();
stockWithUnknown.put("pending", null);

stockWithUnknown.get("pending");         // null
stockWithUnknown.containsKey("pending"); // true

GetOrDefault uses its fallback only for an absent key. An existing null mapping still returns null, and unboxing that result to int throws NullPointerException. Whether null is allowed depends on the implementation. HashMap allows one null key and multiple null values; ConcurrentHashMap does not allow null keys or values; the naturally sorted TreeMap does not accept null keys that cannot be compared.

Composite Updates

java

stock.merge("bolt", -2, Integer::sum);
stock.computeIfAbsent("gear", key -> 0);

merge uses the given value if the key is missing or the old value is null; otherwise, it calls the merging function. If the merging function returns null, the mapping is deleted. computeIfAbsent calculates only when the key is missing or the mapping is null; if the mapping function returns null, it does not add a new entry.

These methods can express "read the old value and write the new value" as a single Map operation. Ordinary HashMap still does not support concurrent writing; ConcurrentHashMap provides concurrent semantics for these composite methods, the calculation should be short and must not update any mapping in that map. Implementations differ in how they detect invalid nested updates. Integer::sum also does not check overflow or prevent negative inventory; implement those domain rules explicitly.

2. Hash Map Lookup Model

The general process of a Hash Map is as follows:

Obtain the key's hashCode and perform internal perturbation;
Use the hash to locate the bucket;
Compare stored hashes and then check key identity or equality within the bucket;
If the key is found, read or update its value. Otherwise get returns null, while put adds a new entry.

With a reliable and well-distributed hash, get, put, and remove provide the expected O(1) performance. Collisions, resizing, malicious keys, and expensive equals can alter the cost of a single operation. The Java 8+ implementation can convert buckets into trees when conflicts are severe and the table is sufficiently large. However, thresholds, capacity rounding, and internal node structures are details of the JDK implementation and not guaranteed by the Map interface.

The initial capacity of the constructor is a hint for the internal table capacity, not the number of entries that can be stored without expansion. The default load factor of 0.75 is also the default value for HashMap implementations. For at most n entries, estimate bucket capacity using the load factor instead of using n directly. The Java 17 HashMap documentation gives a condition for avoiding rehashing: initial capacity greater than the maximum entry count divided by the load factor. Oversizing has a cost too: full iteration takes time proportional to capacity plus entry count.

Hash Map does not guarantee iteration order. For insertion order, use LinkedHashMap; for key sorting, nearby keys, or range views, use TreeMap/NavigableMap.

3. equals and hashCode Contract

HashMap and HashSet first narrow down the candidate set using hash, then confirm equality using equals. Keys and elements must adhere to:

equals Reflexive, symmetric, and transitive, and remain consistent when the information involved in the comparison does not change;
If x.equals(y) is true, x.hashCode() == y.hashCode() must also be true;
A hash value being the same does not imply equality via equals, and collisions are a legitimate scenario;
The information involved in equals and hashCode should remain stable during the period when it is used as a hash key.

Records are well-suited for simple value keys, but components must also have correct semantics. Array components use array identity equality, and do not automatically compare elements; mutable List components may change their hash value after insertion.

java

record MaterialKey(String tenantId, String materialCode) {
    MaterialKey {
        Objects.requireNonNull(tenantId, "tenantId");
        Objects.requireNonNull(materialCode, "materialCode");
    }
}

When manually writing a regular class, equals and hashCode use the same set of stable fields. IDEs can generate the skeleton, but the domain must decide "which fields define the same object." Tools cannot make that determination for you.

4. Why Mutating a Key Can Break Lookup

The complete example below defines MutableParticipant with both id and age in equals/hashCode. This snippet changes age after inserting the key:

java

MutableParticipant participant = new MutableParticipant("P-1", 25);
Map<MutableParticipant, String> roles = new HashMap<>();
roles.put(participant, "Accounting");

participant.age = 26;
System.out.println(roles.get(participant)); // null

The object remains in its original node, but lookup computes a new hash. That hash may select another bucket. Even if the bucket index happens to match, a different stored hash can prevent identity or equals checks from happening at all. Not every mutation loses the key, but the lookup contract is no longer reliable. A more stable design is to use only immutable business identifiers as keys, placing variable attributes like age in the value.

"Using no mutable objects as keys is too absolute." Objects can have mutable fields, as long as the equality and hash information for the key remains stable during residency; however, immutable value types are easier to prove this.

5. The repetition and order of a Set are determined by the implementation

Implementation	Equal/Repeat Rule	Iteration Order	Cost of One Lookup/Insertion/Removal
`HashSet`	`hashCode` + `equals`	Not specified	Expected O(1)
`LinkedHashSet`	`hashCode` + `equals`	Insertion order	Expected O(1)
`TreeSet`	`compareTo` or Comparator returns 0	Sorting order	O(log n)

TreeSet has another notion of "same": if the comparator returns 0, it is considered a duplicate, even if equals is false.

java

Set<String> byLengthOnly = new TreeSet<>(
        Comparator.comparingInt(String::length));

System.out.println(byLengthOnly.add("wood")); // true
System.out.println(byLengthOnly.add("bolt")); // false: same length

If you want to retain all strings of the same length, append a stable comparison condition:

java

Comparator<String> byLengthThenText =
        Comparator.comparingInt(String::length)
                .thenComparing(Comparator.naturalOrder());

To obey the general Set/Map contract, ordering must be consistent with equals. A length-only comparator treats different strings as one element. TreeSet still follows its comparator, but this violates the ordinary Set contract defined through equals. Also, do not modify the fields participating in the sorting after insertion; the tree will not automatically move nodes to new positions.

6. TreeMap and NavigableMap Range Views

java

NavigableMap<String, Integer> scores = new TreeMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Charlie", 92);

NavigableMap<String, Integer> range =
        scores.subMap("B", true, "D", false);

range is a view backed by the original TreeMap, not a copy. Modifying the range of keys will reflect in scores; inserting a key outside the range will throw IllegalArgumentException.

NavigableMap also provides lowerKey, floorKey, ceilingKey, higherKey, firstEntry, and lastEntry. These operations express proximity and range requirements, which HashMap does not support.

7. Iterating Maps

java

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

stock.forEach((material, count) ->
        System.out.println(material + " -> " + count));

When both key and value are needed, use entrySet. Just use keySet for the key and values for the value. Don't take "entrySet is always faster" as a mantra; choose the view that best expresses the data you need, and measure the hot path again if necessary.

When iterating over HashMap/HashSet, do not assert order. If stable output is required, it can be copied to a TreeMap, sorted entry, or choose LinkedHash/Tree implementation from the start.

8. Choose Concurrent Semantics for Concurrent Writes

Suppose several workers modify a HashMap concurrently. Unsynchronized structural changes have no safety guarantee: updates may be lost and reads may be inconsistent. The risks extend beyond a particular historical JDK bug.

ConcurrentHashMap provides atomic compound operations for counting. Atomicity does not remove the Integer overflow limit:

java

ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
counts.merge("bolt", 1, Integer::sum);

If multiple keys need to be satisfied together for a single invariant, a single merge is still insufficient; a new state boundary must be designed, or a lock covering the entire composite transaction must be used. Concurrent containers solve the operations declared in their documentation, but they do not automatically turn any business process into an atomic operation.

9. Complete Working Example

First, prepare a temporary directory:

bash

chapter10_map_root=$(mktemp -d)
readonly chapter10_map_root
mkdir -p "$chapter10_map_root/out"
cd "$chapter10_map_root"

Save as MapSetContractsDemo.java. Its ConcurrentHashMap calls run sequentially to check API results; two such calls are not a concurrency stress test.

java

import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Objects;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentHashMap;

public class MapSetContractsDemo {
    public static void main(String[] args) {
        Map<String, Integer> stock = new LinkedHashMap<>();
        stock.put("bolt", 50);
        stock.put("nut", 30);
        stock.merge("bolt", -2, Integer::sum);
        stock.computeIfAbsent("gear", key -> 20);
        checkEquals(48, stock.get("bolt"));

        Map<String, Integer> nullable = new HashMap<>();
        nullable.put("pending", null);
        check(nullable.get("pending") == null, "value should be null");
        check(nullable.containsKey("pending"), "key should exist");
        check(!nullable.containsKey("missing"), "missing key should not exist");

        MutableParticipant mutable = new MutableParticipant("P-1", 25);
        Map<MutableParticipant, String> roles = new HashMap<>();
        roles.put(mutable, "accounting");
        mutable.age = 26;
        check(roles.get(mutable) == null,
                "lookup should fail after changing a hashed field");
        checkEquals(1, roles.size());

        Set<String> encounterOrder = new LinkedHashSet<>(
                List.of("bolt", "nut", "bolt", "gear"));
        checkEquals(List.of("bolt", "nut", "gear"),
                List.copyOf(encounterOrder));

        Set<String> byLengthOnly = new TreeSet<>(
                Comparator.comparingInt(String::length));
        check(byLengthOnly.add("wood"), "first insertion should succeed");
        check(!byLengthOnly.add("bolt"),
                "equal lengths compare as zero and count as duplicates");

        NavigableMap<String, Integer> scores = new TreeMap<>();
        scores.put("Alice", 95);
        scores.put("Bob", 87);
        scores.put("Charlie", 92);
        NavigableMap<String, Integer> range =
                scores.subMap("B", true, "D", false);
        range.put("Bob", 88);
        checkEquals(88, scores.get("Bob"));
        expect(IllegalArgumentException.class,
                () -> range.put("Aaron", 99));

        ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
        counts.merge("bolt", 1, Integer::sum);
        counts.merge("bolt", 1, Integer::sum);
        checkEquals(2, counts.get("bolt"));

        System.out.println("Inventory: " + stock);
        System.out.println("Deduplication order: " + encounterOrder);
        System.out.println("Score range: " + range);
        System.out.println("Concurrent count: " + new TreeMap<>(counts));
        System.out.println("Map/Set contract checks passed");
    }

    static final class MutableParticipant {
        private final String id;
        private int age;

        MutableParticipant(String id, int age) {
            this.id = id;
            this.age = age;
        }

        @Override
        public boolean equals(Object other) {
            return other instanceof MutableParticipant participant
                    && age == participant.age
                    && id.equals(participant.id);
        }

        @Override
        public int hashCode() {
            return Objects.hash(id, age);
        }
    }

    static void expect(Class<? extends Throwable> type, Runnable action) {
        try {
            action.run();
        } catch (Throwable throwable) {
            if (type.isInstance(throwable)) return;
            throw new AssertionError(
                    "expected=" + type + ", actual=" + throwable, throwable);
        }
        throw new AssertionError("expected exception=" + type.getName());
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    static void checkEquals(Object expected, Object actual) {
        if (!Objects.equals(expected, actual)) {
            throw new AssertionError("expected=" + expected + ", actual=" + actual);
        }
    }
}

Run:

bash

javac --release 17 -encoding UTF-8 -Xlint:all -d out MapSetContractsDemo.java
java -cp out MapSetContractsDemo

Expected output:

text

Inventory: {bolt=48, nut=30, gear=20}
Deduplication order: [bolt, nut, gear]
Score range: {Bob=88, Charlie=92}
Concurrent count: {bolt=2}
Map/Set contract checks passed

Save the required output and clean up:

bash

cd
ls -ld -- "$chapter10_map_root"
rm -r -- "$chapter10_map_root"

Keep Key Identity Stable

When designing keys for a repository, start by writing out "under what conditions do two items count as the same material or the same participant." HashMap and HashSet require equal objects to have the same hash; TreeMap and TreeSet consider a comparison result of 0 as the same key or element. Regardless of the path taken, the fields involved in identity judgment should remain stable during the object's residency.

Finally, verify the output against the concurrency boundary: HashMap iteration order is not a guarantee, subMap reflects a live range view of the original map, and one ConcurrentHashMap merge cannot make a multi-key business transaction atomic. Explaining these three points keeps collection code from relying on accidental behavior.

Reviewing the Formal Contracts of Java 17

Map, HashMap, and ConcurrentHashMap: Null, Expected Complexity, and Atomic Composite Operations.
Object.equals and Object.hashCode: Formal Contracts for Hash Container Dependencies.
Set, SortedSet, and NavigableSet: Equality, Sorting, and Nearest Query.
NavigableMap: Range Views and Adjacent Key Operations.

Continue Learning: Exception Mechanism

The ledger has already been able to stably express order, identity, and scope. The next chapter will handle another type of boundary: when a method cannot fulfill its contract, how exceptions propagate along the call stack, and where the caller should recover.

Enter Chapter 11: Exception Mechanism

Chapter 1: Propositional Logic: From Requirement Sentences to Decidable Formulas

Chapter 2: Sets and Operations: Describing Object Scope via Membership

Chapter 3: Direct Proof, Contrapositive, and Case Analysis: Building Verifiable Reasoning Chains

Chapter 4: Recursive Definitions and Mathematical Induction: Proving Along the Construction Process

Chapter 5: Binary Relations: Properties, Composition, and Closure

Chapter 6: Counting Principles: Addition, Multiplication, Inclusion-Exclusion, and the Pigeonhole Principle

Chapter 7: Graph Models and Traversal: First Define Edges, Then Choose Representation

Chapter 8: Probability Space and Conditional Probability: First Build the Model, Then Update Your Judgment

Chapter 9: Divisibility, Congruence, and Euclid's Algorithm: The Fundamental Structure of Integers

Chapter 10: Vectors and Inner Products: Turning Objects into Comparable Coordinates

Chapter 11: Limits, Derivatives, and the Chain Rule: Describing Local Change

Chapter 12: Self-Information, Entropy, and Coding: How Uncertainty Becomes Bits

10.3 Map and Set Contracts

Use a Map for “name → quantity”

1. Basic Reading and Updating of Maps

Composite Updates

2. Hash Map Lookup Model

3. equals and hashCode Contract

4. Why Mutating a Key Can Break Lookup

5. The repetition and order of a Set are determined by the implementation

6. TreeMap and NavigableMap Range Views

7. Iterating Maps

8. Choose Concurrent Semantics for Concurrent Writes

9. Complete Working Example

Keep Key Identity Stable

Reviewing the Formal Contracts of Java 17

Continue Learning: Exception Mechanism