Sets and Maps

Sets: collections without duplicates

A set is a collection in which every element appears at most once. The Set<E> interface adds no new methods to Collection<E>; it changes the contract (the promise the methods make): add refuses an element that is already present and tells you so through its boolean result.

Set<String> seen = new HashSet<>();
System.out.println(seen.add("red"));   // true  - added
System.out.println(seen.add("red"));   // false - already there, set unchanged
System.out.println(seen.size());       // 1

Worked example. Add five names to a LinkedHashSet (it keeps arrival order, so the printout is predictable):

Step	Call	Returns	Set after the step	Why
1	add("Ana")	true	[Ana]	new name
2	add("Ben")	true	[Ana, Ben]	new name
3	add("Ana")	false	[Ana, Ben]	Ana is already there
4	add("Chen")	true	[Ana, Ben, Chen]	new name
5	add("Ben")	false	[Ana, Ben, Chen]	Ben is already there

Five calls, but size() is 3.

"Already present" does not mean "the same object". It means equal according to the set's own rule: equals/hashCode for hash-based sets, compareTo/compare for tree-based sets. Everything in this chapter follows from that one sentence.

A set has no index: there is no get(int). You ask questions (contains), you add and remove, and you iterate.

Three implementations, three orders

Class	Built on	Iteration order	add / contains / remove
HashSet	hash table	unspecified — may look random and may change as the set grows	O(1) expected
LinkedHashSet	hash table + linked list	insertion order (re-adding an element does not move it)	O(1) expected
TreeSet	red-black tree	sorted (natural order or a Comparator)	O(log n) guaranteed

int[] data = {5, 1, 3, 1, 9, 5};
Set<Integer> linked = new LinkedHashSet<>();
Set<Integer> tree = new TreeSet<>();
for (int d : data) { linked.add(d); tree.add(d); }
System.out.println(linked);   // [5, 1, 3, 9]
System.out.println(tree);     // [1, 3, 5, 9]

Step by step — the state of both sets after each add:

Added	LinkedHashSet	TreeSet	Note
5	[5]	[5]
1	[5, 1]	[1, 5]	tree puts 1 before 5
3	[5, 1, 3]	[1, 3, 5]
1	[5, 1, 3]	[1, 3, 5]	duplicate: nothing changes
9	[5, 1, 3, 9]	[1, 3, 5, 9]
5	[5, 1, 3, 9]	[1, 3, 5, 9]	duplicate: 5 does not move to the end

Never write code — or tests — that depends on the order of a HashSet. If the order matters, say so in the type you choose.

The equals/hashCode contract

A HashSet (and a HashMap) finds an element in two steps: hashCode() chooses a bucket, then equals() is used to compare only with the elements in that bucket. For this to work, Object defines a contract:

1. If a.equals(b) is true, then a.hashCode() == b.hashCode() must hold.
2. If the hash codes are equal, the objects may still be different (a collision is allowed).
3. hashCode() must return the same value while the fields used by equals do not change.

public final class Point {
    private final int x, y;
    public Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return 31 * x + y;           // or Objects.hash(x, y)
    }
}

Worked example. Take a table with 16 buckets and, to keep it simple, bucket = hash code mod 16. (The real HashMap mixes the bits a little first, but the idea is the same; Chapter 14 shows the details.)

Point	hashCode = 31·x + y	Bucket (mod 16)
(1, 2)	33	1
(2, 1)	63	15
(0, 33)	33	1 — a collision with (1, 2)

bucket:  0     1                    2  ...  15
        [ ]  [(1,2) -> (0,33)]     [ ]     [(2,1)]

Now contains(new Point(1, 2)):

1. Compute the hash code: 33. Go to bucket 1. The other 15 buckets are never looked at.
2. Compare with (1, 2) using equals → true. Found.

Point (0, 33) is in the same bucket but equals says it is different, so it is not confused with (1, 2). That is rule 2: a collision costs a little time, never a wrong answer.

What goes wrong when you override only one of them?

You override…	Effect in a HashSet
equals only	Two equal points usually get different identity hash codes, land in different buckets and are never compared: the set keeps "duplicates", and contains(new Point(1, 2)) is usually false.
hashCode only	Equal points share a bucket, but Object.equals compares references, so they are still considered different: duplicates again, and contains of a new equal object is false.
both, consistently	Works as expected.

In the coat-check picture: overriding only equals is an attendant who can recognise your coat but walks to a random hook; overriding only hashCode is an attendant who walks to the right hook but only accepts the very same ticket paper, not a copy with the same number.

Ordering: Comparable and Comparator in a TreeSet

A TreeSet needs to compare elements. It uses either:

• the elements' natural order — the class implements Comparable<T> (String, Integer, LocalDate …), or
• a Comparator<T> passed to the constructor.

If you give neither and the class is not Comparable, the code compiles (the constructor cannot check), but the first add throws ClassCastException.

String's natural order compares UTF-16 code units, so upper-case letters come before lower-case ones: [Apple, Banana, apple, banana].

The crucial rule: a TreeSet never calls equals. Two elements for which compare returns 0 are the same element as far as the tree is concerned, and the second one is silently dropped.

Set<String> byLength = new TreeSet<>(Comparator.comparingInt(String::length));
byLength.add("cat");
byLength.add("dog");   // length 3 again: compare returns 0 -> not added
byLength.add("ox");
System.out.println(byLength);   // [ox, cat]

Step by step with two more words:

Call	compare says	Returns	Set after
add("cat")	(empty tree)	true	[cat]
add("dog")	length 3 vs 3 → 0, "same"	false	[cat]
add("ox")	length 2 < 3 → before	true	[ox, cat]
add("horse")	length 5 > 3 → after	true	[ox, cat, horse]
add("pig")	length 3 vs 3 → 0, "same"	false	[ox, cat, horse]

"dog" and "pig" are not equal to "cat", but the tree never asks equals, so they are lost.

This is why the API documentation asks for compareTo to be consistent with equals: a.compareTo(b) == 0 exactly when a.equals(b). If you really want to sort by length, add a tie-breaker so that only truly equal strings compare as 0:

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

With this comparator the same five words give [ox, cat, dog, pig, horse]: sorted by length, and alphabetically inside each length.

Sometimes an inconsistent comparator is exactly what you want: new TreeSet<>(String.CASE_INSENSITIVE_ORDER) keeps one spelling of each word, whatever its case. Adding "Java", "java", "JAVA", "Python" gives [Java, Python] — the first spelling wins.

NavigableSet and NavigableMap

TreeSet implements NavigableSet, and TreeMap implements NavigableMap. Because the elements are sorted, the tree can answer "nearest" questions in O(log n):

Method (set / map-key form)	Returns
first() / firstKey(), last() / lastKey()	smallest / largest
floor(x) / floorKey(x)	greatest element ≤ x, or null
ceiling(x) / ceilingKey(x)	least element ≥ x, or null
lower(x), higher(x)	strictly < x, strictly > x, or null
headSet(x) / headMap(x)	view of the elements < x (exclusive)
tailSet(x) / tailMap(x)	view of the elements ≥ x (inclusive)
subSet(a, b) / subMap(a, b)	view of a ≤ e < b

Worked example on the set {10, 20, 30, 40}. Picture it on a number line:

        10        20        30        40
  5 ?----|---------|----25---|---------|----? 45

x	floor(x) (≤)	ceiling(x) (≥)	lower(x) (<)	higher(x) (>)
25	20	30	20	30
30	30	30	20	40
5	null	10	null	10
45	40	null	40	null

The row for 30 shows the difference: floor and ceiling may return x itself; lower and higher never do. For the views: headSet(30) = [10, 20], tailSet(30) = [30, 40], subSet(15, 35) = [20, 30].

TreeMap<Integer, String> grade = new TreeMap<>();
grade.put(90, "A"); grade.put(80, "B"); grade.put(70, "C"); grade.put(0, "F");
System.out.println(grade.floorEntry(84).getValue());   // B  (largest key <= 84 is 80)

This is a neat way to turn a score into a grade without a chain of ifs: 90 → A, 69 → F (largest key ≤ 69 is 0), 100 → A.

These methods live in NavigableSet/TreeSet, not in Set. A variable declared as Set<String> does not have first() — the code does not compile. Declare it as TreeSet<String> or NavigableSet<String> when you need them.

The Map API

A Map<K, V> stores key → value pairs; keys are unique (they behave like a set), values may repeat.

Map<String, Integer> stock = new HashMap<>();
Integer old = stock.put("pen", 4);      // null: there was no previous value
old = stock.put("pen", 7);              // 4: put replaces and returns the OLD value
int pens = stock.get("pen");            // 7
int ink  = stock.getOrDefault("ink", 0); // 0 instead of null
boolean has = stock.containsKey("ink"); // false
stock.remove("pen");

Step by step:

Call	Returns	Map after	Why
put("pen", 4)	null	{pen=4}	no old value
put("pen", 7)	4	{pen=7}	same key: value replaced, old one returned
get("pen")	7	{pen=7}
getOrDefault("ink", 0)	0	{pen=7}	missing key, default used
get("ink")	null	{pen=7}	missing key
remove("pen")	7	{}

Two Java 8 methods replace most "get, test for null, put" code:

// counting: add 1, or start at 1 if the key is new
freq.merge(word, 1, Integer::sum);

// grouping: create the list the first time, then add to it
groups.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);

In words: merge(key, 1, Integer::sum) means "if the key is new, store 1; otherwise store old + 1". computeIfAbsent(key, k -> new ArrayList<>()) means "give me the list for this key, and create an empty one first if there is none".

To walk a map, iterate over entrySet() — you get key and value together without a second lookup, and Map.Entry.setValue changes the value in place:

for (Map.Entry<String, Integer> e : freq.entrySet()) {
    System.out.println(e.getKey() + " -> " + e.getValue());
}

keySet() (a Set<K>), values() (a Collection<V>, may contain duplicates) and entrySet() are views: removing from them removes from the map. Adding or removing through the map while a for-each loop runs over one of its views throws ConcurrentModificationException; use iterator.remove() or map.keySet().removeIf(...) / map.entrySet().removeIf(...) instead.

HashMap, LinkedHashMap, TreeMap

	HashMap	LinkedHashMap	TreeMap
Key order when iterating	unspecified	insertion order	sorted by key
get / put / remove	O(1) expected	O(1) expected	O(log n)
null key	one allowed	one allowed	not allowed (NullPointerException) — compareTo cannot be called on null
null values	allowed	allowed	allowed
Needs from the key	equals + hashCode	equals + hashCode	Comparable or a Comparator
Extra	—	re-put of an existing key keeps its position	firstKey, floorKey, headMap, tailMap …

Example. Put pear=1, apple=2, fig=3, then apple=4 into a LinkedHashMap and a TreeMap:

LinkedHashMap: {pear=1, apple=4, fig=3}   arrival order; apple keeps its old place, new value
TreeMap:       {apple=4, fig=3, pear=1}   sorted by key

The same pattern holds for sets: a HashSet is really a HashMap whose values are ignored, and a TreeSet is a TreeMap in disguise.

Typical patterns

Frequency counting — how many times does each word occur?

Map<String, Integer> freq = new TreeMap<>();   // sorted report for free
for (String w : text.split("\\s+")) freq.merge(w, 1, Integer::sum);

Trace for the text "the cat and the hat and the cat":

Word	What merge does	Map after the step
the	new → 1	{the=1}
cat	new → 1	{cat=1, the=1}
and	new → 1	{and=1, cat=1, the=1}
the	1 + 1	{and=1, cat=1, the=2}
hat	new → 1	{and=1, cat=1, hat=1, the=2}
and	1 + 1	{and=2, cat=1, hat=1, the=2}
the	2 + 1	{and=2, cat=1, hat=1, the=3}
cat	1 + 1	{and=2, cat=2, hat=1, the=3}

The TreeMap keeps the keys sorted after every step, so the final report is alphabetical.

Grouping — Map<K, List<V>>, e.g. students by class, words by first letter, anagrams by their sorted letters. Grouping the words sun, moon, sky, star, cloud by length with computeIfAbsent:

Word	List for its length	Map after the step
sun	3: created, then add	{3=[sun]}
moon	4: created, then add	{3=[sun], 4=[moon]}
sky	3: exists, add	{3=[sun, sky], 4=[moon]}
star	4: exists, add	{3=[sun, sky], 4=[moon, star]}
cloud	5: created, then add	{3=[sun, sky], 4=[moon, star], 5=[cloud]}

For anagrams, use the sorted letters as the key: "listen", "silent" and "enlist" all become "eilnst" and land in the same list.

First repetition — if (!seen.add(x)) return x; uses the boolean returned by add.

static int firstRepeat(int[] xs) {
    Set<Integer> seen = new HashSet<>();
    for (int x : xs) {
        if (!seen.add(x)) return x;   // add returned false: seen before
    }
    return -1;
}

For {4, 7, 2, 7, 4}: add 4 (true), add 7 (true), add 2 (true), add 7 (false) → returns 7. One pass, O(n) expected, instead of comparing every pair, Θ(n²).

Set algebra — the bulk operations modify the set they are called on, so copy first if you need the original:

Set<Integer> union = new TreeSet<>(a);   union.addAll(b);
Set<Integer> inter = new TreeSet<>(a);   inter.retainAll(b);
Set<Integer> diff  = new TreeSet<>(a);   diff.removeAll(b);

With a = {1, 2, 3, 4} and b = {3, 4, 5}:

   a              b
 ( 1  2  (3  4)  5 )
union = [1, 2, 3, 4, 5]   everything in a or b
inter = [3, 4]            only what is in both
diff  = [1, 2]            in a but not in b
a is still [1, 2, 3, 4] because we worked on copies

Expected complexities

Operation	HashSet / HashMap	TreeSet / TreeMap
add, put, contains, get, remove	O(1) expected, O(n) worst case with many collisions	O(log n)
iterate over all n elements	O(n + capacity)	O(n)
first, floor, ceiling, headSet …	not available	O(log n) (views are created lazily)

"Expected O(1)" assumes a reasonable hashCode that spreads keys over the buckets. A hashCode that returns a constant is legal but turns every lookup into a scan of one long bucket.

Key takeaways

• A set keeps each element at most once; add returns false for a duplicate. A map keeps each key once; put returns the old value (or null).
• Order: Hash… = no promised order, LinkedHash… = arrival order, Tree… = sorted.
• Hash structures use hashCode to find the bucket and equals inside it: override both, consistently, and do not change a key after inserting it.
• Tree structures use only compareTo/compare: a result of 0 means "same element", so a comparator that ties different objects makes the tree drop them.
• floor/ceiling include x, lower/higher exclude it; headSet(x) excludes x, tailSet(x) includes it. They exist only on TreeSet/TreeMap (or Navigable… variables).
• Use getOrDefault, merge (counting) and computeIfAbsent (grouping) instead of "get, test for null, put"; iterate with entrySet().
• TreeMap rejects null keys; HashMap and LinkedHashMap allow one.
• Costs: hash = O(1) expected, tree = O(log n) guaranteed plus sorted order and nearest-element queries.