Languages · Java

Collections Framework

Almost every collection type implements one of three root interfaces: Collection (lists, sets, queues), Map (key-value pairs — notably NOT a Collection), and their shared iteration contract.

💻 Languages● Intermediate⏱ 7 min read🛠️ 3 exercises🎤 5 interview Q&As

🎯 What you'll learn

The Core Hierarchy
List: ArrayList vs LinkedList
Set: HashSet vs LinkedHashSet vs TreeSet
Map: HashMap vs LinkedHashMap vs TreeMap
Comparable vs Comparator

1The Core Hierarchy

Almost every collection type implements one of three root interfaces: Collection (lists, sets, queues), Map (key-value pairs — notably NOT a Collection), and their shared iteration contract.

text

Iterable<E>
  └── Collection<E>
        ├── List<E>     — ordered, indexable, duplicates allowed   (ArrayList, LinkedList)
        ├── Set<E>       — no duplicates                            (HashSet, LinkedHashSet, TreeSet)
        └── Queue<E>      — FIFO/priority access                    (ArrayDeque, PriorityQueue)

Map<K, V>                — key-value pairs, NOT a Collection        (HashMap, LinkedHashMap, TreeMap)

java

List<String> names = new ArrayList<>();
Set<Integer> uniqueIds = new HashSet<>();
Map<String, Integer> ages = new HashMap<>();

2`List`: `ArrayList` vs `LinkedList`

Operation	`ArrayList`	`LinkedList`
`get(index)`	O(1) — direct array index	O(n) — walks the list from the nearer end
`add(end)`	amortized O(1)	O(1)
`add(index)` / `remove(index)`	O(n) — shifts elements	O(1) once positioned, O(n) to get there
Memory	one contiguous backing array	one node object (with 2 references) per element
Cache locality	good — contiguous memory	poor — nodes scattered on the heap

In practice, ArrayList is the default choice almost always; LinkedList only wins for workloads dominated by insert/remove at both ends combined with never doing random-access get, and even then ArrayDeque usually beats it as a double-ended queue.

java

List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);
list.add(0, 5);      // insert at index 0 — shifts everything right
list.remove(Integer.valueOf(20)); // removes the VALUE 20, not index 20 — overload ambiguity trap

3`Set`: `HashSet` vs `LinkedHashSet` vs `TreeSet`

java

Set<String> hash = new HashSet<>();        // no order guarantee at all
Set<String> linked = new LinkedHashSet<>(); // preserves INSERTION order
Set<String> sorted = new TreeSet<>();        // always kept in SORTED order (needs Comparable or a Comparator)

hash.add("banana"); hash.add("apple"); hash.add("cherry");
// iteration order of `hash` is unspecified and can differ across runs/JVMs

sorted.addAll(hash);
System.out.println(sorted); // [apple, banana, cherry] — always sorted

4`Map`: `HashMap` vs `LinkedHashMap` vs `TreeMap`

Same ordering trade-off as Set (unsurprising — HashSet is literally backed by a HashMap internally with dummy values).

java

Map<String, Integer> scores = new HashMap<>();
scores.put("Ada", 100);
scores.merge("Ada", 5, Integer::sum);        // Ada -> 105, functional update-or-insert
scores.computeIfAbsent("Grace", k -> 0);       // insert 0 only if key absent
scores.getOrDefault("Missing", -1);              // -1, no NullPointerException

5`Comparable` vs `Comparator`

Comparable<T> is implemented by the element type itself to define one natural ordering; Comparator<T> is an external, swappable strategy — you can have as many as you like without touching the element class.

java

class Person implements Comparable<Person> {
    String name; int age;
    Person(String name, int age) { this.name = name; this.age = age; }

    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age); // natural order: by age
    }
}

List<Person> people = new ArrayList<>(List.of(new Person("Bob", 30), new Person("Ana", 25)));
Collections.sort(people); // uses compareTo — natural order (by age)

people.sort(Comparator.comparing((Person p) -> p.name));         // external, by name
people.sort(Comparator.comparingInt((Person p) -> p.age).reversed()); // chainable, reversed

6Iteration and Fail-Fast Behavior

Modifying most collections while iterating over them with a for-each loop (which uses an Iterator under the hood) throws ConcurrentModificationException — even in single-threaded code.

java

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer n : nums) {
    if (n == 2) nums.remove(n); // ConcurrentModificationException on the NEXT iteration
}

// Correct: use the Iterator's own removal method
Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    if (it.next() == 2) it.remove(); // safe — the iterator tracks the removal itself
}

7Immutable and Unmodifiable Collections

java

List<String> immutable = List.of("a", "b", "c");         // truly immutable, fixed size
immutable.add("d"); // UnsupportedOperationException

List<String> mutable = new ArrayList<>(List.of("a", "b"));
List<String> view = Collections.unmodifiableList(mutable); // a VIEW — blocks writes THROUGH view...
mutable.add("c");                                            // ...but the underlying list can still change
System.out.println(view); // [a, b, c] — the view reflects the mutation

A HashMap's table array holds buckets; each bucket is a linked list of entries until it grows past the treeify threshold, at which point that one bucket becomes a red-black tree

Under the HoodHow it works internally▾

ArrayList grows by 1.5x, not doubling, and copies the whole backing array on resize. Internally it wraps a plain Object[]. On overflow, ArrayList.grow() computes newCapacity = oldCapacity + (oldCapacity >> 1) (old capacity plus half of itself — a 1.5x growth factor, not the 2x some other languages use) and copies every element into the new array via System.arraycopy (a JVM intrinsic, typically compiled to a highly optimized bulk memory copy rather than a per-element Java loop). This is why appending to an ArrayList is amortized O(1) — most appends are a cheap array write, but occasionally one append triggers an O(n) full copy, averaging out over many operations.

HashMap is an array of buckets, and Java 8 added a real fallback data structure per bucket. The backing store is Node<K,V>[] table, sized to a power of two. hashCode() on the key isn't used directly as the bucket index — HashMap runs it through a spreading function, h ^ (h >>> 16) (XOR the hash with itself shifted right 16 bits), to fold the high bits into the low bits before masking with (table.length - 1), which meaningfully reduces collisions for hash codes that vary mostly in their high bits. Each bucket starts as a simple linked list of entries with the same post-spread hash bucket index. Since Java 8, if a single bucket's chain grows to TREEIFY_THRESHOLD (8) entries and the table itself has at least MIN_TREEIFY_CAPACITY (64) buckets, that one bucket is converted into a red-black tree, changing worst-case lookup in that bucket from O(n) to O(log n) — a defense specifically against hash-flooding (many keys colliding into the same bucket, whether by bad luck or a hostile hashCode()). If entries are later removed and the bucket shrinks back to UNTREEIFY_THRESHOLD (6), it's converted back to a plain list during a resize. The default load factor is 0.75 — the table resizes (doubling capacity) once the number of entries exceeds capacity * loadFactor, trading some extra empty bucket space for keeping average chain length short.

HashSet is a thin wrapper around HashMap. Every element you add becomes a key in a private, backing HashMap<E, Object>, mapped to a single shared dummy sentinel value (PRESENT) — there is no independent HashSet storage implementation; add, contains, and remove all delegate straight to the map's key operations.

Fail-fast iteration is implemented with a modCount counter, not real concurrency detection. Every structural modification (add/remove, not element replacement via set) increments an internal modCount field on the collection. Each Iterator snapshots modCount when created and re-checks it on every next()/remove() call; a mismatch throws ConcurrentModificationException. This is a best-effort heuristic, not a guarantee — it exists to catch bugs early, not to provide thread safety, and it can still miss some modification patterns or produce false negatives under genuine concurrent access.

⚠️ Common Pitfalls

Modifying a collection while iterating it with for-each — throws ConcurrentModificationException; use Iterator.remove(), a removeIf(predicate), or collect indices/elements to remove into a separate list first.
Using a mutable object as a HashMap/HashSet key and then mutating it after insertion — changes the key's hashCode(), so the entry becomes unreachable at its original bucket; the entry effectively "disappears" from lookups even though it's still physically in the table.
Not overriding equals/hashCode on a custom key/element class — falls back to Object's reference-identity versions, so two logically-equal objects are treated as different keys/elements (see the Inheritance and Polymorphism topic's contract discussion).
list.remove(int) vs list.remove(Object) overload ambiguity — list.remove(5) on a List<Integer> removes the element at index 5, not the value 5; use list.remove(Integer.valueOf(5)) to remove by value.
Assuming HashMap/HashSet iteration order is meaningful or stable — it depends on hash spreading and current bucket layout, and can change across JVM versions or even after a resize on the same run; use LinkedHashMap/LinkedHashSet (insertion order) or TreeMap/TreeSet (sorted order) when order matters.

📋 Quick Reference

java

List<T>  new ArrayList<>()     // fast random access, default choice
         new LinkedList<>()     // rarely the right call — ArrayDeque usually better

Set<T>   new HashSet<>()        // no order
         new LinkedHashSet<>()  // insertion order
         new TreeSet<>()         // sorted order (Comparable/Comparator)

Map<K,V> new HashMap<>()        // no order, O(1) average get/put
         new LinkedHashMap<>()  // insertion order
         new TreeMap<>()         // sorted by key

map.getOrDefault(k, def)
map.computeIfAbsent(k, fn)
map.merge(k, v, BiFunction)

list.sort(Comparator.comparing(x -> x.field).reversed().thenComparing(...));

Iterator<T> it = list.iterator();
while (it.hasNext()) { T v = it.next(); if (cond) it.remove(); } // safe removal during iteration

List.of(...); Set.of(...); Map.of(k, v, ...); // truly immutable factories

🎤 Interview Q&A

Questions interviewers ask about this topic. Answer out loud first, then open a card to compare.

Q1ArrayList vs LinkedList?core▾

ArrayList: dynamic array, O(1) random access, amortized O(1) append, O(n) middle inserts; cache-friendly and the default. LinkedList: O(1) inserts with an iterator, O(n) access, more memory; rarely better in practice.

Follow-ups interviewers ask

Queue use? ArrayDeque beats LinkedList.

Q2How does HashMap work?core▾

An array of buckets indexed by hash; collisions chain in lists that become balanced trees when large (Java 8+). It resizes when the load factor (0.75) is exceeded. Average O(1) get/put.

Follow-ups interviewers ask

Mutable keys pitfall? Changing a key's hash after insertion makes it unreachable.

Q3HashMap vs LinkedHashMap vs TreeMap?core▾

HashMap: no order, fastest. LinkedHashMap: insertion or access order (LRU caches). TreeMap: sorted keys, O(log n), navigation methods (floorKey, subMap).

Follow-ups interviewers ask

LRU with LinkedHashMap? accessOrder=true and override removeEldestEntry.

Q4How do you handle collections across threads?senior▾

Use ConcurrentHashMap, CopyOnWriteArrayList, blocking queues, or immutable collections; Collections.synchronizedX wrappers lock coarsely. Iterating a non-concurrent collection while modifying causes ConcurrentModificationException.

Follow-ups interviewers ask

ConcurrentHashMap atomic ops? compute, merge, putIfAbsent.

Q5What are immutable collections in modern Java?core▾

List.of, Set.of, Map.of, copyOf create unmodifiable collections (null elements not allowed); stream().toList() returns an unmodifiable list.

Follow-ups interviewers ask