Collections Framework

7 pages · ~5 min✓ Reviewed

Builds on OOP in Java. Next up: Exceptions.

JavaPage 1

Collections Hierarchy Mental Model

1. The Hierarchy

Collection extends Iterable; List, Set and Queue extend Collection
Map does NOT extend Collection

2. Pick by Behaviour

	Rule	Implementations
List	ordered, indexed, duplicates ok	ArrayList, LinkedList
Set	no duplicates	HashSet (unordered), LinkedHashSet (insertion), TreeSet (sorted)
Queue / Deque	FIFO; Deque is double-ended	ArrayDeque, LinkedList
PriorityQueue	heap order, not FIFO	min-heap by default

3. Common Mistake

Iterating a PriorityQueue does not give sorted order
Iterating a HashSet does not give insertion order

java

var pq = new PriorityQueue<Integer>();
pq.add(5); pq.add(1); pq.add(3);
System.out.println(pq);

prints heap array order

output

[1, 5, 3]

Fix

Sorted: poll() repeatedly or use TreeSet. Insertion order: LinkedHashSet.

JavaPage 2

ArrayList vs LinkedList

1. ArrayList: a resizable array

ArrayList is a resizable Object[]
get(i) is O(1); add at end is amortized O(1)
Insert/remove in the middle is O(n): elements shift
Grows by ~1.5x when full; pass an initial capacity if the size is known

2. LinkedList and the comparison

LinkedList is a doubly linked list: each node holds prev and next
get(i) is O(n): walk the nodes
Add/remove at either end or at a known node is O(1)
Rarely faster in practice: per-node overhead, poor cache locality

	ArrayList	LinkedList
`get(i)`	O(1)	O(n)
Add at end	amortized O(1)	O(1)
Insert in middle	O(n) shift	O(1) at known node
Memory	compact, cache-friendly	node overhead

3. Mistake: remove(int) vs remove(Object)

java

List<Integer> a = new ArrayList<>(List.of(10, 20, 1));
a.remove(1);
System.out.println(a);
a.remove(Integer.valueOf(1));
System.out.println(a);

remove(1) is an index, not a value

output

[10, 1]
[10]

On a List<Integer>

remove(1) removes the index. Use remove(Integer.valueOf(1)) to remove the value.

JavaPage 3

HashMap Internals

1. Buckets and Resize

Array of buckets; index = (n-1) & hash(key.hashCode())
Default capacity 16, load factor 0.75
Resize when size > capacity x load factor (12 at default)
Resize doubles the table and rehashes entries

2. Collisions and Cost

get/put are O(1) average; tree bin gives O(log n) worst case
Tree bin shrinks back to a list at 6 entries
Equal objects must have equal hash codes, so keep equals() and hashCode() consistent

3. Mistakes and Nulls

Mutating a key after insertion
Overriding equals without hashCode

	HashMap	Hashtable	ConcurrentHashMap
Null key	one allowed	no	no

Unfindable entry

Either mistake makes get look in the wrong bucket, so the entry is unfindable. Use immutable keys.

JavaPage 4

TreeMap and Map Variants

1. TreeMap

TreeMap is a red-black tree
Keys are kept sorted (natural order or a Comparator)
get / put / remove are O(log n)

2. Navigation methods

Method	Returns
`firstKey()` / `lastKey()`	smallest / largest key
`floorKey(k)`	greatest key ≤ k
`ceilingKey(k)`	least key ≥ k
`headMap(k)`	view of keys < k
`tailMap(k)`	view of keys ≥ k
`subMap(a, b)`	view of keys ≥ a and < b

3. LinkedHashMap

Keeps insertion order by default
Constructor flag accessOrder=true gives access order
LRU cache: override removeEldestEntry

java

new LinkedHashMap<K, V>(16, 0.75f, true) {
  protected boolean removeEldestEntry(
      Map.Entry<K, V> e) {
    return size() > 3;
  }
};

evicts the least recently used entry past 3

4. Compared, and the pitfall

Map	Order	Cost
`HashMap`	none	O(1)
`LinkedHashMap`	insertion / access	O(1)
`TreeMap`	sorted	O(log n)

Key equality

TreeMap judges keys by compareTo/compare, not equals. Keys comparing 0 are one entry. A null key throws NullPointerException.

JavaPage 5

Comparable, Comparator and Safe Iteration

1. Comparable vs Comparator

	Comparable	Comparator
Method	`compareTo(T o)`	`compare(a, b)`
Defined	inside the class	external, separate object
Orders	one natural order	many, class unchanged

Chain keys with comparing, thenComparing; flip with reversed()

java

Comparator<Person> c = Comparator
    .comparing(Person::getAge)
    .thenComparing(Person::getName)
    .reversed();

age, then name, whole order reversed

2. Safe Iteration

list.remove(x) inside for-each throws ConcurrentModificationException
Fix: call Iterator.remove() while iterating
Or one line: list.removeIf(x -> x < 0)

3. Common Mistake

Comparing with a - b can overflow and flip the sign
Use Integer.compare(a, b) instead

Remember

Comparable = the class's single default order. Comparator = any extra order, no class change.

JavaPage 6

Generics Basics and Cheat Sheet

1. Generics and Erasure

List<String> gives compile-time type safety, so no casts
Type arguments must be reference types: List<Integer>, not List<int>
Erasure: generic types are erased at runtime
List<String> and List<Integer> are the same class

2. Wildcards

Wildcard	Role	Allowed
`? extends T`	Producer	read as T, no adding
`? super T`	Consumer	add T, read as Object

PECS

Producer Extends, Consumer Super.

3. Cheat Sheet

Need	Use
Default list	`ArrayList`
Stack / queue	`ArrayDeque`
Lookup	`HashMap` / `HashSet`
Sorted	`TreeMap` / `TreeSet`
Min-heap	`PriorityQueue`

List.of / Set.of / Map.of build immutable collections
Any modification throws UnsupportedOperationException

java

Map<String, Integer> m = Map.of("a", 1);
m.put("b", 2); // UnsupportedOperationException

JavaPage 7

Check yourself

What does this print?

[10, 30, 1]
remove(1) picks remove(int index), not the value
To remove the value: l.remove(Integer.valueOf(1))

List<Integer> l = new ArrayList<>(List.of(10, 20, 30, 1));
l.remove(1);
System.out.println(l);

Why can this loop throw, and what is the fix?

Usually ConcurrentModificationException: the list changed behind the iterator
Fix: names.removeIf(s -> s.startsWith("A"))

for (String s : names)
    if (s.startsWith("A")) names.remove(s);

What does the map hold after both puts?

{a=2}
TreeMap decides key equality by compare, not equals
The old key stays, the value is replaced

Map<String, Integer> m = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
m.put("a", 1);
m.put("A", 2);
System.out.println(m);