Week 6 Day 2 — Set and Map Contracts

Goal

Today I want Set as uniqueness and Map as lookup, and I want to pick implementations by contract, not by habit.

Main questions:

1. What does a Set promise?
2. HashSet vs LinkedHashSet vs TreeSet?
3. What does a Map promise?
4. How is HashSet implemented?
5. When does JPA care about Set vs List?

---

1. The Set contract

A Set contains no two elements e1 and e2 such that e1.equals(e2) (and at most one null, if allowed).

Order is not part of the Set interface. Iteration order depends on the implementation.

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("java"); // false; still one element

add returns whether the set changed. That is useful.

Memory sentence:

A Set is uniqueness by equals (and hashCode or order, depending on the implementation).

---

2. Three sets I actually name

Type	Uniqueness	Order	null
HashSet	hashCode then equals	none (not predictable)	one null
LinkedHashSet	same as HashSet	insertion order	one null
TreeSet	compareTo / Comparator	sorted	no null with natural order

HashSet is the default unique bag.

LinkedHashSet when I need unique and stable iteration (dedupe a list, keep first-seen order).

TreeSet when I need sorted unique. Trap: uniqueness is compareTo == 0, not equals. If those disagree, the set can hold two equals elements or drop one that equals would keep. Day 5.

---

3. The Map contract

A Map associates keys with values. Keys are unique by the same rules as a set of keys.

Map<String, Integer> counts = new HashMap<>();
counts.put("ada", 1);
counts.put("ada", 2); // replaces value; returns old 1
counts.get("ada");    // 2
counts.getOrDefault("bob", 0);

get returns null if the key is missing or if the value is null. Prefer getOrDefault, containsKey, or Optional wrappers at the edge.

Implementations I name:

Type	Keys	Order	Notes
HashMap	hash / equals	none	default; one null key
LinkedHashMap	hash / equals	insert (or access order)	LRU if access-order
TreeMap	sorted keys	key order	no null key with natural ordering
EnumMap	enum keys	enum declaration	compact
Hashtable	hash / equals	none	legacy, synchronized, no nulls
ConcurrentHashMap	hash / equals	none	concurrent; no null keys/values

Week 8 covers concurrent maps. For now: HashMap is not thread-safe. A singleton bean that mutates a HashMap from many requests is a bug.

---

4. HashSet is a HashMap

HashSet is a map whose values are a dummy object. add is put(element, PRESENT). That is why HashSet needs the same equals/hashCode as map keys (Day 3).

LinkedHashSet is a LinkedHashMap. TreeSet is a TreeMap.

---

5. Spring / JPA connection

@OneToMany + Set: uniqueness in memory uses entity equals/hashCode. If those use a generated id that is null before persist, two new children can collapse into one in the set. Common fix: UUID assigned in the constructor, or List if duplicates and order matter.

Map as a cache on a @Service: shared mutable state (Week 1). Use a real cache or ConcurrentHashMap with a clear policy — not a raw HashMap field.

JSON objects bind to Map<String, Object> in a pinch. Prefer a record DTO.

Spring MultiValueMap: one key, several values (query params). That is not Map<String, String>.

---

6. Common traps

Trap 1: Expecting HashSet iteration to be insertion order.

Trap 2: TreeSet uniqueness via equals. It uses comparison.

Trap 3: get == null meaning “absent” when values can be null.

Trap 4: Hashtable as the “thread-safe HashMap.” It is legacy. ConcurrentHashMap is the concurrent map.

Trap 5: JPA Set of entities with id-based equals before the id exists.

---

Practice Questions and Answers

Question 1

HashSet vs LinkedHashSet vs TreeSet?

Answer:

All unique. HashSet is hash-based, no order. LinkedHashSet keeps insertion order. TreeSet keeps sort order and uses comparison for uniqueness. Default unique bag: HashSet. Need order: LinkedHashSet. Need sorted: TreeSet plus a consistent Comparable/Comparator.

---

Question 2

How is HashSet implemented?

Answer:

It is a HashMap with a dummy value. Element hashCode/equals are the key contract. Performance and mutation-of-elements bugs are the same as for map keys.

---

Question 3

Why is Map not a Collection?

Answer:

A map is not a group of elements; it is a group of associations. Size is the number of keys. Iteration is through views: keys, values, or entries.

---

Question 4

When would I use LinkedHashMap?

Answer:

When I need map lookup plus a defined iteration order. Insertion order is the default. Access-order LinkedHashMap plus removeEldestEntry is a simple LRU cache.

---

Question 5

Why can two new JPA entities disappear in a HashSet?

Answer:

If equals/hashCode use a generated id that is still null, every new entity looks equal (or every hash collides on 0). The set keeps one. Assign a stable id up front, or use a List if the association is a bag.

---

Memory sentences

Set is uniqueness. Map is lookup. Neither promises order unless the implementation does.

HashSet is a HashMap with a dummy value.

TreeSet uniqueness is compareTo, not equals.

Next: Week 6 Day 3 — HashMap Internals