17 — Collections

Previous: 16 Exceptions · Next: 18 Generics

▶️ java pkg1core/core19CollectionsDemo.java · java pkg1core/core29HashMapDemo.java · java pkg1core/core28ComparatorDemo.java

Hierarchy at a glance

1Iterable2└── Collection3    ├── List      (ordered, duplicates OK)4    ├── Set       (unique)5    └── Queue/Deque6 7Map (separate — key → value)

Pick the right collection

Quick examples

1List<String> list = new ArrayList<>(List.of("b", "a", "c"));2list.sort(String::compareTo);3 4Map<String, Integer> freq = new HashMap<>();5for (String s : list) freq.merge(s, 1, Integer::sum);6 7Set<String> unique = new TreeSet<>(list);   // sorted unique8 9Queue<Integer> q = new ArrayDeque<>();10q.offer(1); q.poll();

HashMap

HashMap stores key → value pairs for fast lookup. Keys are unique: putting the same key again replaces the previous value. Values may repeat.

Common operations

1Map<String, Integer> ages = new HashMap<>();2ages.put("Ana", 20);3ages.put("Bob", 19);4ages.get("Ana");                 // 205ages.getOrDefault("Zed", 0);     // 0 if missing6ages.containsKey("Bob");         // true7ages.put("Ana", 21);             // update existing key8ages.merge("Ana", 1, Integer::sum);  // read-modify-write idiom

Average lookup and update are O(1) when hashes spread well. Heavy collisions degrade toward O(n) — interview material covers capacity and load factor in depth.

Null keys and values

HashMap allows one null key and any number of null values. Prefer clear keys in new code; treat null entries as a special case when reading older APIs.

Keys need stable equals and hashCode

A key is found by bucket (from hashCode) then equality (from equals). If two objects are equal, their hash codes must match. If you mutate a field used by equals/hashCode after put, the entry can become unfindable.

▶️ See pkg1core/core29HashMapDemo.java for a small key-contract demo.

When to choose HashMap

See it in code

1. API usage — frequency maps and Map helpers: pkg1core/core19CollectionsDemo.java
2. Key contract — equals/hashCode with java.util.HashMap: pkg1core/core29HashMapDemo.java
3. Under the hood — buckets, chaining, resize (teaching reimplementation): pkg3datastructures/datastructures6HashTableImpl.java

Practice (hash-map approaches in this repo)

These solutions document a hash-map technique in their APPROACH comments:

• Two Sum — one-pass hash map
• Group Anagrams — HashMap by signature
• Subarray Sum Equals K — prefix-sum hash map
• Isomorphic Strings — two hash maps
• Contains Duplicate II — hash map of last index

Interview bridge

Now that you understand the fundamentals, these interview questions take you deeper (answers stay in the interview hub — do not skip the demos above):

• How does HashMap work internally?
• HashMap vs Hashtable vs ConcurrentHashMap?
• HashMap vs TreeMap vs LinkedHashMap?
• What is the load factor and capacity?
• Why must map keys be immutable / have stable hashCode?

Comparable vs Comparator

1// Natural order — built into class2class Student implements Comparable<Student> {3    public int compareTo(Student o) { return Integer.compare(score, o.score); }4}5 6// Custom order — external, flexible7list.sort(Comparator.comparingInt(Student::score).reversed()8                    .thenComparing(Student::name));

Thread safety

Default collections are not thread-safe. Use:

• ConcurrentHashMap
• CopyOnWriteArrayList
• Collections.synchronizedList() (with care)

Deep dive → 03-interview/03-Collections.md

Next → 18 Generics