Sets & Maps — Uniqueness and Lookup

A List keeps things in order and allows duplicates. Two other shapes cover most of what's left:

a Set stores unique elements and answers "is this in here?" in about constant time;
a Map stores key → value associations and answers "what's the value for this key?" just as fast.

Both come in three forms:

hash-based, fast but unordered: HashSet, HashMap;
tree-based, with keys sorted: TreeSet, TreeMap;
linked, with insertion order kept: LinkedHashSet, LinkedHashMap.

The hash versions get their speed from hashing entries into buckets. That mechanism is why the next lesson's hashCode contract matters.

💡 The core idea.

A Set stores unique elements; a Map stores key→value.
Hash forms give about constant-time lookup by hashing into buckets, trading order for speed.
Tree* keeps keys sorted; LinkedHash* keeps insertion order.

This builds on the Collections Framework and the null-unboxing hazard. Every output below was produced by compiling and running the code on Java 25.

You'll be able to: predict a set's size and contains results after duplicate adds, and say when a duplicate throws instead; pick HashSet, LinkedHashSet or TreeSet by the iteration order you need, and explain why HashSet order is never a contract; store, update, remove and iterate a map's entries, and predict what get returns for a missing key; write the counting idiom, and explain why get(k) + 1 throws on a new key.

📘 How to read the Intuition boxes. Each one is built in three moves:

The mechanism — what the compiler and the JVM do.
A concrete bite — a specific, runnable failure (often a real compiler error), shown so the trap is visible.
The earned rule — the decision heuristic, now justified rather than asserted, plus its cost.

Set: unique elements
Three flavors: hashed, sorted, insertion-ordered
Map: key → value
The counting idiom
Mental-model summary
Gotcha checklist
Check yourself
Sources

1. `Set`: unique elements

A Set holds each element at most once [1]. Adding a duplicate changes nothing, and contains answers membership in constant time on average.

Output:

2
true
false

Analysis. Adding "a" twice left the size at 2, because the second add found "a" already present and did nothing. contains returned true for a member and false for a non-member, each without scanning the whole set.

The diagram shows why it's fast. An element's hash code is a number computed from its contents: "a" gives 97, and "b" gives 98. The hash code picks a bucket, so a membership check looks in one bucket, not at every element. (The diagram is simplified to 4 buckets. A new HashSet starts with 16 [2].)

Intuition. Mechanism. A HashSet keeps an array of buckets [2]. To add or look up an element, it computes the element's hashCode, maps that to a bucket index, and checks only that bucket.

So add and contains take constant time, "assuming the hash function disperses the elements properly among the buckets" [2]. A List.contains scans every element: O(n).
Uniqueness comes for free: an element that lands in an occupied bucket is compared with .equals, and dropped if an equal one is already there.

Concrete bite. Uniqueness doesn't always mean "a duplicate is ignored". Set.of(...) builds an unmodifiable set, and it rejects duplicates at creation [1]:

Output (prints one line, then a thrown exception):

true
Exception in thread "main" java.lang.IllegalArgumentException: duplicate element: a

Map.of does the same for a repeated key: duplicate key: k. Like List.of, both are unmodifiable, so calling add or put on them throws UnsupportedOperationException.

💡 Earned rule. Use a Set when you need uniqueness or fast membership tests: "have I seen this?", "is this allowed?". Reach for a HashSet by default. Use Set.of only for fixed values you know are distinct.

The cost is losing order, plus a small overhead per element. The payoff is membership in constant time instead of the O(n) scan a List.contains does.

A type stored in a HashSet must define hashCode and equals together, or equal objects land in different buckets. That contract is the subject of equals & hashCode.

2. Three flavors: hashed, sorted, insertion-ordered

The same Set interface has three implementations that differ in iteration order, the order a for-each visits the elements:

HashSet: no promised order;
TreeSet: sorted;
LinkedHashSet: insertion order.

Output:

tree:   [1, 2, 3]
linked: [3, 1, 2]
hash:   [1, 2, 3]

Analysis. All three dropped the duplicate 1, so each holds {1, 2, 3}. But the order differs:

TreeSet printed sorted: [1, 2, 3].
LinkedHashSet printed insertion order: [3, 1, 2].
HashSet printed [1, 2, 3] here, by accident. An Integer's hash code is its own value [3], so small numbers land in buckets in numeric order.

The java.util.* import brings in every class of the package at once.

Intuition. Mechanism. Each implementation stores its elements differently:

TreeSet keeps elements in a sorted tree, with "guaranteed log(n) time cost" for add, remove and contains [4].
LinkedHashSet is a HashSet plus "a doubly-linked list running through all of its entries" in insertion order [5]. It stays constant time.
HashSet is the plain bucket array. Its API "makes no guarantees as to the iteration order", not even that the order stays the same over time [2].

Concrete bite. The hash: [1, 2, 3] line is a trap dressed up as order. Switch to strings, and the order is neither sorted nor the insertion order:

Output:

linked: [pear, fig, apple, kiwi]
hash:   [apple, pear, kiwi, fig]

The HashSet order comes from the strings' hash codes. This run on JDK 25 printed apple, pear, kiwi, fig; another JDK, or more elements, may print another order.

A TreeSet has its own trap, because it must compare its elements. A class with no natural ordering fails on the first add [4]:

Output (a thrown exception):

Exception in thread "main" java.lang.ClassCastException: class Player cannot be cast to class java.lang.Comparable (Player is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')

The fix is the one from sorting a list: implement Comparable, or pass a Comparator to the TreeSet constructor.

💡 Earned rule. Pick the implementation by the order you need:

HashSet when order doesn't matter (fastest);
TreeSet when you need sorted iteration (O(log n), and the elements must be comparable);
LinkedHashSet when you need insertion order (a little more memory).

Tree or Linked costs you speed or memory. Assuming HashSet is ordered costs you a bug that hides until the data changes.

3. `Map`: key → value

A Map associates each unique key with a value, and "each key can map to at most one value" [6]. Its main methods:

put stores a value under a key;
get retrieves the value for a key;
containsKey tests whether a key is present;
getOrDefault retrieves, with a fallback for an absent key.

The same hashed, sorted and linked trio applies: HashMap, TreeMap, LinkedHashMap.

Output:

36
0
true
null

Analysis.

get("Ada") returned the stored 36.
getOrDefault("Zoe", 0) returned the fallback 0, because "Zoe" is absent.
containsKey("Linus") is true.
The last line is the one to watch: get("Zoe") for a missing key returns null, not a default.

A Map finds a value by hashing the key into a bucket, exactly as a Set hashes its elements. Map<String, Integer> names two types: the keys' type, then the values' type.

A map can also update, remove, and let you walk its entries. A Map isn't itself a collection, but it offers three views that are [6]:

keySet(), the set of keys;
values(), the collection of values;
entrySet(), the set of key-value pairs, each a Map.Entry with getKey() and getValue().

Output:

4
7
fig -> 2
pear -> 9
[fig, pear]
[2, 9]

Analysis.

put("pear", 9) on an existing key replaced the value, and returned the previous one, 4 [7].
remove("apple") deleted the entry and returned its value, 7.
The for-each over entrySet() visited every pair. A TreeMap visits keys in sorted order [8], so fig came before pear.

Intuition. Mechanism. get returns the value for the key, or null when the key is absent. A HashMap may also store null as a value, so "a return value of null does not necessarily indicate that the map contains no mapping for the key" [9]. getOrDefault and containsKey exist to handle absence explicitly.

Concrete bite. Because a missing key gives null, assigning get's result straight into a primitive unboxes null and throws:

Output (a thrown exception):

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

m.get("missing") returned null, because there's no such key. Assigning it to an int tried to unbox null, which is the null-unboxing NullPointerException [10]. The map didn't fail. The hidden unboxing of a null did.

💡 Earned rule. Treat Map.get as possibly returning null. Use getOrDefault(key, fallback) or containsKey when a key may be absent, and never assign get's result straight into a primitive. Walk a map through entrySet() when you need both keys and values.

The cost is a fallback value or an extra check. The payoff is no surprise NullPointerException from a lookup that missed.

4. The counting idiom

The most common Map task is counting occurrences, and it takes one line with getOrDefault: read the current count (0 for a new key), add one, and put it back.

Output:

3
2
1

Analysis. For each word, getOrDefault(word, 0) returned the running count (0 the first time a word appeared). + 1 incremented it, and put stored it back over the old value. The result is a frequency table: a three times, b twice, and c once.

Intuition. Mechanism. getOrDefault(k, d) returns the mapped value, or d if k is absent [6]. So the first occurrence reads 0, and every later one reads the count so far. The idiom folds "start at zero on first sight" and "add one on later sights" into one expression.

Concrete bite. Drop the default and use get, and the first occurrence of each word reads null, unboxes it, and throws:

Output (a thrown exception):

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

The getOrDefault(..., 0) isn't decoration. It's the seed that makes the count work.

💡 Earned rule. Count with map.put(k, map.getOrDefault(k, 0) + 1). Once you have the method references of Lambdas, merge(k, 1, Integer::sum) does the same in one call.

The getOrDefault form costs a little length. The payoff is that it works with only what you know so far, and it makes "the default for a new key" explicit.

5. Mental-model summary

Principle	Consequence
A `Set` holds unique elements; a `Map` holds key→value	A duplicate `add` changes nothing; `put` on an existing key replaces its value
`Set.of` and `Map.of` are unmodifiable, and reject duplicates	A repeated element or key throws `IllegalArgumentException` at creation
Hashing into buckets gives constant-time membership and lookup	`HashSet` and `HashMap` are fast but unordered; never rely on their order
`Tree` keep keys sorted; `LinkedHash` keep insertion order	Choose by the order you need; `Tree*` needs comparable keys
A map offers `keySet()`, `values()` and `entrySet()` views	Walk `entrySet()` for keys and values together
`Map.get` returns `null` for an absent key	Use `getOrDefault` or `containsKey`; don't assign `get` into a primitive
Counting: `put(k, getOrDefault(k, 0) + 1)`	The `0` default seeds a new key; plain `get` throws on first sight

6. Gotcha checklist

Symptom	Likely cause	Fix
`NullPointerException … the return value of "java.util.Map.get(Object)" is null`	the key was absent, and `get`'s `null` was unboxed	`getOrDefault`, or `containsKey` first; or keep the result an `Integer`
Counting throws on the first occurrence of a word	`get(k) + 1` on a new key	`getOrDefault(k, 0) + 1`
A `HashSet` or `HashMap` "lost" its order	it never had one	`LinkedHash` for insertion order, `Tree` for sorted
A test assumes `HashSet` iterates in sorted order	a coincidence for small `Integer`s	never depend on hash order
`ClassCastException: … cannot be cast to class java.lang.Comparable` on a `TreeSet` or `TreeMap`	the element or key class has no natural ordering	implement `Comparable`, or pass a `Comparator`
`IllegalArgumentException: duplicate element` or `duplicate key`	a repeated value in `Set.of` or `Map.of`	remove the repeat, or build a `HashSet` or `HashMap`
`UnsupportedOperationException` on `add` or `put`	the set or map came from `Set.of` or `Map.of`	copy it: `new HashSet<>(…)`, `new HashMap<>(…)`
A value changed without warning	`put` on an existing key replaces the old value	check `containsKey`, or use the value `put` returns
Duplicate elements "disappeared" from a `Set`	sets are unique by design	a `List`, or a `Map` of counts

✅ Check yourself

One check per objective. Answer before you open anything.

The 🧪 box below: the set size, the three sets of 5, 3, 5, 1, m.get("a"), and the fixed counting loop.

Adding "x", "y", "x", "z", "y" leaves size 3.
Adding 5, 3, 5, 1: TreeSet prints [1, 3, 5], LinkedHashSet prints [5, 3, 1], and HashSet printed [1, 3, 5] on JDK 25, by the small-Integer accident of §2.
System.out.println(m.get("a")) prints null. int n = m.get("a"); throws NullPointerException, because the null gets unboxed.
The fixed loop is m.put(w, m.getOrDefault(w, 0) + 1);.

📚 Sources

java.util.Set, Java SE 25 API ("Unmodifiable Sets": duplicates "result in IllegalArgumentException") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Set.html
java.util.HashSet, Java SE 25 API (no iteration-order guarantee; constant time "assuming the hash function disperses the elements properly") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/HashSet.html
java.lang.Integer.hashCode(), Java SE 25 API ("equal to the primitive int value") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/lang/Integer.html#hashCode()
java.util.TreeSet, Java SE 25 API ("guaranteed log(n) time cost"; elements "must implement the Comparable interface") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/TreeSet.html
java.util.LinkedHashSet, Java SE 25 API — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/LinkedHashSet.html
java.util.Map, Java SE 25 API (one value per key; the three collection views; getOrDefault; "Unmodifiable Maps") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Map.html
java.util.Map.put(K, V), Java SE 25 API ("Returns: the previous value associated with key") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Map.html#put(K,V)
java.util.TreeMap, Java SE 25 API ("sorted according to the natural ordering of its keys") — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/TreeMap.html
java.util.Map.get(Object), Java SE 25 API — https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/Map.html#get(java.lang.Object)
The Java Language Specification, Java SE 25, §5.1.8 "Unboxing Conversion" — https://docs.oracle.com/javase/specs/jls/se25/html/jls-5.html#jls-5.1.8

🧪 Predict, then check.

Predict the size of a Set<String> after adding "x", "y", "x", "z", "y".
Predict the three lines printed by adding 5, 3, 5, 1 to a TreeSet, a LinkedHashSet and a HashSet, and printing each.
For Map<String,Integer> m = new HashMap<>();, predict what System.out.println(m.get("a")); prints, and what int n = m.get("a"); does instead.
Fix the counting loop m.put(w, m.get(w) + 1) so it doesn't throw.

Your Turn

Before you move on, check your understanding with the coach — explain the idea, apply it, weigh the trade-offs, then defend your reasoning.

Sets & Maps — Uniqueness and Lookup

Table of contents

1. Set: unique elements

2. Three flavors: hashed, sorted, insertion-ordered

3. Map: key → value

4. The counting idiom

5. Mental-model summary

6. Gotcha checklist

✅ Check yourself

📚 Sources

Your Turn

1. `Set`: unique elements

3. `Map`: key → value