Set and Map Implementations

Hash vs Tree

Sets and Maps come in hash-based and tree-based variants. The hash versions offer near-instant lookups with no ordering; the tree versions keep everything sorted but pay a small cost.

HashSet and HashMap

Set<String> tags = new HashSet<>();
tags.add("java");
tags.add("spring");
tags.add("java");     // duplicate ignored
tags.contains("java"); // true - usually O(1)

Map<String, Boolean> flags = new HashMap<>();
flags.put("debug", true);
flags.get("debug");      // true

• Insert, lookup, delete: O(1) on average.
• Order is not guaranteed or meaningful.
• hashCode() and equals() drive the object's slot; objects used as keys should implement both properly.

TreeSet and TreeMap

Set<Integer> sortedSet = new TreeSet<>();
sortedSet.add(30);
sortedSet.add(10);
sortedSet.add(20);
System.out.println(sortedSet); // [10, 20, 30] always sorted

Map<String, Integer> ordered = new TreeMap<>();
ordered.put("b", 2);
ordered.put("a", 1);
System.out.println(ordered.keySet()); // [a, b]

• Elements stay in natural order (or a supplied comparator).
• Lookup is O(log n).

The equals + hashCode Contract

Two equal objects must produce the same hash code, otherwise a HashSet may treat them as different entries. The default implementations use identity, so custom classes should override both together.

class Product {
    String code;
    // IDE-generated equals() and hashCode() based on 'code' is the norm
}

Key Points

• HashSet/HashMap: fastest, no guaranteed order.
• TreeSet/TreeMap: keep elements sorted, slightly slower.
• Override equals and hashCode together for custom keys.