Foundation · Module 5 · Lesson 2
Sets & maps
Presence checks, key-value lookup, and uniqueness.
15–25 min readLesson 28 of 123
Lesson 28 of 123
1d streakSets & Maps: Uniqueness, Key-Value Lookups & Implementations
A Set represents a collection of distinct unique elements, while a Map associates unique keys with values. Under the hood, a HashSet is simply a HashMap where the value is a dummy placeholder object.
| Implementation | Underlying Structure | Search / Insert Time | Ordering Guarantee | Allows Null? |
|---|---|---|---|---|
| HashSet / HashMap | Hash Table (Chaining) | O(1) average, O(n) worst | No ordering guaranteed | Yes (1 null key) |
| LinkedHashSet / Map | Hash Table + Doubly Linked List | O(1) average | Insertion order preserved | Yes |
| TreeSet / TreeMap | Self-Balancing Red-Black Tree | O(log n) guaranteed | Sorted natural / Comparator order | No null keys |
Use it when
Use HashSet/HashMap for fast O(1) membership checks, duplicates filtering, and key-value lookups when ordering does not matter.
Reconsider when
Use TreeSet/TreeMap when you need sorted range queries (e.g., floorKey, ceilingKey, subMap) or when keys must remain ordered.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Build and query
Expected O(n)
O(n)
The bound follows from the number of states visited and the work performed per transition.When to use it
- Presence, uniqueness, frequency, complement, and previously seen state queries.
- Replacing repeated scans with indexed history.
- Grouping values by a canonical key.
Common mistakes
- Assuming hash lookup has a deterministic O(1) worst case.
- Updating the map before a query that requires a distinct earlier item.
- Using mutable or inconsistent keys.
Practice prompts
- Reproduce the worked Sets & maps example without looking at the trace.
- Change one input condition and explain whether the Sets & maps invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.