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 roughly constant time. A Map stores key → value associations and answers "what's the value for this key?" just as fast. Both come in a hash-based form that's fast but unordered (HashSet, HashMap), a tree-based form that keeps keys sorted (TreeSet, TreeMap), and a linked form that preserves insertion order (LinkedHashSet, LinkedHashMap). The speed of the hash versions comes from hashing entries into buckets — the same mechanism that makes the next chapter's hashCode contract matter.

This builds on the Collections Framework and the null/unboxing hazards. Every output below was produced by compiling and running the code.

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

1. Set: unique elements

A Set holds each element at most once. Adding a duplicate is a no-op, and contains answers membership in (amortized) constant time.

Output:

2
true
false

Analysis. Adding "a" twice left the size at 2 — 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 hashCode picks a bucket, so membership checks one bucket, not every element.

Intuition. Mechanism. A HashSet keeps an array of buckets. 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/contains are O(1) on average instead of O(n). Uniqueness falls out: an element that hashes to an occupied bucket is compared (with .equals) and dropped if already there.

Concrete bite. Because placement is by hashCode, a HashSet has no meaningful order — you cannot ask for "the first element" or expect any particular iteration sequence. That's the trade for O(1): speed in exchange for order. (And it's why a type used in a HashSet must implement hashCode/equals correctly — Tutorial 19.)

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

The same Set interface has three implementations that differ only in iteration order: HashSet (no 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 by implementation. TreeSet printed sorted ([1, 2, 3]); LinkedHashSet printed insertion order ([3, 1, 2]). The HashSet printed [1, 2, 3] here, but that is not guaranteed — small Integers happen to hash to themselves, so they land in numeric order by accident. Never rely on HashSet order.

Intuition. Mechanism. TreeSet is backed by a balanced search tree, so it keeps elements sorted at O(log n) per operation. LinkedHashSet is a HashSet plus a linked list threading entries in insertion order, so it's O(1) and ordered. HashSet is the plain bucket array — fastest, no order.

Concrete bite. The hash: [1, 2, 3] line is a trap dressed as order: it looks sorted, so a test might assume HashSet is sorted — then break when the elements are strings, larger numbers, or a different JVM. Order from a HashSet is coincidence, never contract.

3. Map: key → value

A Map associates each unique key with a value. put stores, get retrieves, containsKey tests, and getOrDefault retrieves with a fallback for absent keys. The same hashed/sorted/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 looks up its value by hashing the key into a bucket, exactly like a Set hashes its elements.

Intuition. Mechanism. get returns the value for the key, or null if the key isn't present — there's no way for get alone to tell "absent" from "present with value null." getOrDefault and containsKey exist precisely 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 (no such key), and assigning it to an int tried to unbox null — the null-unboxing NullPointerException. The map didn't fail; the implicit unboxing of a null did.

4. The counting idiom

The most common Map task — counting occurrences — has a one-line shape with getOrDefault: read the current count (defaulting to 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. The result is a frequency table: a three times, b twice, c once. The getOrDefault(..., 0) is what makes a brand-new key start counting from zero instead of NullPointerException-ing on a null.

Intuition. Mechanism. getOrDefault(k, d) returns the mapped value or d if k is absent — so the first occurrence reads 0, and every later one reads the accumulated count. The idiom folds "initialize on first sight" and "increment on later sights" into one expression.

Concrete bite. Drop the default and use get — counts.put(word, counts.get(word) + 1) — and the first occurrence of each word reads null, unboxes, and throws the same NPE as §3. The getOrDefault(..., 0) is not optional decoration; it's the seed that makes the count work.

5. Mental-model summary

6. Gotcha checklist

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.