Metadata Card

• Difficulty: (Novice Village 3-star)
• Prerequisites: Ch9 (Strings)
• Core concepts: 7 (Collection overview, ArrayList/LinkedList, HashSet/TreeSet, HashMap, TreeMap, Collections utilities, equals/hashCode)
• Estimated time: 5-7 hrs

The Breakthrough · Tracing the Origins

You've mastered strings, but 80% of your workshop's production incidents are related to collections. The collection framework isn't just "know how to use" — you need to "understand it."

Collection Framework Overview

Iterable
 └── Collection
 ├── List (ordered, allows duplicates)
 │ ├── ArrayList — array-backed, fast reads, slow inserts (except at end)
 │ └── LinkedList — linked list, fast inserts, slow reads
 ├── Set (no duplicates)
 │ ├── HashSet — based on HashMap, O(1)
 │ └── TreeSet — based on TreeMap, sorted
 └── Queue
 ├── PriorityQueue
 └── ArrayDeque (preferred over Stack)

ArrayList vs LinkedList

int N = 100_000;
List<String> arr = new ArrayList<>();
for (int i = 0; i < N; i++) arr.add(0, "x"); // Head insert
// ArrayList: ~3000ms — shifts all elements

List<String> link = new LinkedList<>();
for (int i = 0; i < N; i++) link.add(0, "x"); // Head insert
// LinkedList: ~13ms — just changes pointers

Operation	ArrayList	LinkedList
Tail append	O(1)*	O(1)
Head insert	O(n)	O(1)
Index read	O(1)	O(n)
Search by value	O(n)	O(n)

HashMap Internals

How put/get works:

1. Call key.hashCode() → get hash value h
2. h & (n-1) → compute bucket index (n = array size, power of 2)
3. Locate bucket:
   • Empty → insert directly
   • Has elements → traverse linked list/tree, compare with equals()
   • Same key → overwrite value
   • Not found → append to list/tree

Resize: Load factor = 0.75. When size > capacity × 0.75, double capacity and rehash.

Key rule: Use immutable objects as keys! If you modify a key after putting it into a HashMap, you can't get it back.

equals() and hashCode() Contract

The golden rule: If two objects are equal via equals(), they must have the same hashCode().

public class Villager {
 private final String id; // Use immutable fields for hashCode

 @Override
 public boolean equals(Object o) {
 if (this == o) return true;
 if (!(o instanceof Villager)) return false;
 Villager v = (Villager) o;
 return Objects.equals(id, v.id);
 }

 @Override
 public int hashCode() {
 return Objects.hash(id);
 }
}

Five pitfalls: Don't override equals without hashCode; don't use mutable fields in hashCode; always use IDE-generated equals/hashCode; check instanceof; maintain consistency.

Collections Utilities

Collections.sort(list);
Collections.reverse(list);
Collections.shuffle(list);
Collections.unmodifiableList(list); // Read-only wrapper
Collections.synchronizedList(list); // Thread-safe wrapper

Final Challenge: Implement a hot keyword cache. Needs to:

• Track search frequency per keyword (case-insensitive)
• Return top 10 keywords
• Handle 1M+ unique keywords efficiently

Traveler's Notes

ArrayList works for 90% of use cases; LinkedList for specific insertion patterns.
HashMap is worth studying deeply — interview staple and production essential.
equals and hashCode must always be paired — always use IDE generation.
Remove during iteration requires Iterator.remove() or removeIf().