Collections and HashMap: the must-knows

For this sheet, we'll revise the collections hierarchy, a Big-O table for choosing the right type, ArrayList against LinkedList, HashMap from hashCode() to treeified bins, then LinkedHashMap, TreeMap, ConcurrentHashMap, iterators, ordering, generics and immutable collections. Each item gives you the why in a few sentences and the exact numbers an interviewer expects. When you want the long version, follow the link.

01Picture it first: the collections map

Think of the Collections Framework as a set of contracts with several engines behind each one. List promises order and index access, Set promises uniqueness, Queue promises an order of removal, and Map promises key lookup. The engine you choose (array, linked nodes, hash table, red-black tree) decides the cost of every operation.

Here is the whole family on one page, including the detail people forget: Map does not extend Collection.

Fig. 1

The Java collections hierarchy: Iterable and Collection at the top, List, Set and Queue below with their main implementations, and Map as a separate tree with HashMap, LinkedHashMap, TreeMap and ConcurrentHashMap

• Map is not a Collection: Map has no add(E) or iterator(); you iterate keySet(), values() or entrySet(). Interviewers ask this to see whether you've looked at the hierarchy or memorised class names. Module 03: Collections
• Sets are maps in disguise: HashSet stores elements as keys of an internal HashMap with a shared dummy value, LinkedHashSet uses a LinkedHashMap, and TreeSet uses a TreeMap. Everything you learn about the map applies to the set.
• Java 21 sequenced collections (JEP 431): SequencedCollection adds getFirst(), getLast(), addFirst(), reversed() to List, Deque and LinkedHashSet; SequencedMap adds firstEntry(), pollLastEntry() and putFirst() to LinkedHashMap and TreeMap. Mentioning it shows you're current.
• Legacy classes: Vector, Stack and Hashtable are synchronized on every method and date from Java 1.0. Use ArrayList, ArrayDeque and HashMap (or ConcurrentHashMap) instead.

02Choosing the right collection

When an interviewer says "which collection would you use?", they want the access pattern first, then the type, then its cost. This is the table I'd keep in my head.

Notice the pattern. Hash structures give O(1) by giving up order, tree structures give order for O(log n), and the linked variants add order back to a hash structure for a few extra pointers per entry.

03ArrayList vs LinkedList

ArrayList is a resizable Object[]. A no-argument new ArrayList<>() starts with a shared empty array and allocates 10 slots on the first add. When it's full, it grows to old + (old >> 1), which is 1.5x, and copies everything with Arrays.copyOf.

• Amortised O(1) append: a copy of n elements happens only after roughly n/2 cheap appends since the last copy, so the total copying work over n appends is a constant multiple of n. Any single add can still cost O(n); that's the copy.
• Middle inserts are O(n) in both: ArrayList shifts elements with System.arraycopy, LinkedList walks to the position first (from the nearer end), then relinks. The shift is a memory copy and wins in practice.
• Memory: with compressed oops, an ArrayList slot is 4 bytes; a LinkedList.Node is an object with a 12-byte header plus three references, about 24 bytes per element, and scattered on the heap so every step is a likely cache miss.
• When LinkedList is fine: removing via a ListIterator you already hold, or as a Deque if you need null elements. Otherwise ArrayDeque beats it as a queue and ArrayList beats it as a list. Module 03: Collections

04HashMap internals in depth

This is the question. Let's get the picture right first, then walk put and get step by step.

A HashMap is a Node<K,V>[] table whose length is always a power of two. Each Node holds four things: the cached hash, the key, the value and next. A bucket (bin) is empty, a linked list of nodes, or a red-black tree of TreeNodes.

Fig. 2

A HashMap table of 16 buckets: bucket 0 holds the null key, bucket 5 holds a linked list bin of three nodes, and bucket 11 holds a red-black tree bin, with the treeify, resize and untreeify rules underneath

The numbers to say out loud

The table itself is created lazily: new HashMap<>() allocates nothing until the first put.

Step 1: spread the hash

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

With 16 buckets, only the low 4 bits of the hash pick the bucket. Many real hashCodes differ only in their high bits (think Float keys or small multiples of large numbers), so without help they'd all collide. XOR-ing the top 16 bits into the bottom 16 lets the high bits influence the index for the cost of one shift and one XOR. A null key gets hash 0, so it always lives in bucket 0, and HashMap allows exactly one.

Step 2: pick the bucket

index = (n - 1) & hash. For n = 16, n - 1 is 0b1111, so the mask keeps the low 4 bits. This is the same as hash % n for a power of two, but it's a single AND, and it is never negative. That's why the capacity you pass to the constructor is rounded up to the next power of two: new HashMap<>(100) gets 128 buckets.

Step 3: put, step by step

1. If the table is null, resize() allocates it (16 buckets by default).
2. Compute i = (n - 1) & hash. If table[i] is empty, place a new Node there. Done.
3. Otherwise compare the first node: same stored hash, then == on the key, then equals. If it matches, this is an update.
4. If the bin is a tree, call putTreeVal (O(log k) for k nodes in the bin).
5. Otherwise walk the list. If a node matches, update it. If you reach the end, append at the tail (Java 8+), and if the bin has now passed 8 nodes, call treeifyBin.
6. For an update, replace the value and return the old one; modCount does not change.
7. For a new entry, increment modCount and size. If ++size > threshold, resize().

Step 4: get, step by step

get is the read-only version: spread the hash, mask to a bucket, check the first node, then either search the tree or walk the list comparing stored hash, then ==, then equals. The stored-hash check skips almost every equals call, which matters when equals is expensive, like on long strings.

Map<String, Integer> m = new HashMap<>();
m.put("Aa", 1);
m.put("BB", 2);
System.out.println(m.size() + " " + m.get("Aa") + " " + m.get("BB"));
// 2 1 2
// 2112 is 0x840; (2112 >>> 16) is 0, so the spread hash is 2112.
// 2112 & 15 = 0, so both nodes share bucket 0, as a 2-node list.

A collision is not a bug. Both entries survive because equals tells them apart inside the bucket. The hash only decides where to look; equals decides what matches.

Step 5: resize and the lo/hi split

When size passes the threshold, the table doubles: 16 to 32, threshold 12 to 24. Because the new mask has exactly one more bit, every node either stays at index j or moves to j + oldCap. The JDK tests one bit, hash & oldCap, and splits each bin into a "lo" list and a "hi" list without calling hashCode() again.

Fig. 3

A resize from 16 to 32 buckets: bucket 5 with hashes 5, 21, 37 and 53 splits on the bit worth 16, so 5 and 37 stay at index 5 and 21 and 53 move to index 21

Each resize is still O(n) for the whole map, which is why presizing matters. And because Java 8 keeps the order inside each half, two threads racing through a resize can no longer build the cyclic list that made Java 7's HashMap spin at 100% CPU. It's still not thread-safe: you can lose entries instead.

Step 6: treeify, and why it waits for 64

When you add a node to a bin that already has 8, treeifyBin runs. If the table has fewer than 64 buckets, it resizes instead: with a small table, a long chain more likely means "too many entries for 16 buckets" than "pathological hashes", and doubling spreads the chain out. Only with 64 or more buckets does the bin become a red-black tree of TreeNodes, ordered by hash, then by compareTo if the keys are mutually Comparable, then by a tie-break on identity hash.

• Why Java 8 changed collision handling: before Java 8 a bucket was always a list, so an attacker who sends thousands of keys with the same hash (the 2011 hash-flooding attacks on web frameworks used colliding form-parameter names) turns each lookup into an O(n) scan and a request into O(n²) work. Tree bins cap the damage at O(log n) per lookup. The javadoc's Poisson estimate for a well-distributed hash at load factor 0.75 puts the chance of a bin reaching 8 nodes at about 0.00000006, so treeification is a defence, not a normal path.
• Comparable keys help: with String or Integer keys a tree bin is searched by compareTo. With keys that are not Comparable, equal hashes force the tree search down both branches, and the worst case drifts back toward O(n).
• Untreeify at 6: when a resize splits a tree bin and a half ends up with 6 or fewer nodes, it becomes a plain list again. The gap between 8 and 6 stops a bin from flipping back and forth on every insert and delete. The equals() and hashCode() contracts

05The mutable key bug

The stored hash is computed once at insertion. If you change a field that hashCode() reads, the node stays in the old bucket while lookups go to the new one.

record Point(int x, int y) {}          // immutable: safe as a key

final class MutablePoint {             // mutable: dangerous as a key
    int x, y;
    MutablePoint(int x, int y) { this.x = x; this.y = y; }
    @Override public boolean equals(Object o) {
        return o instanceof MutablePoint p && p.x == x && p.y == y;
    }
    @Override public int hashCode() { return 31 * x + y; }
}

Set<MutablePoint> seen = new HashSet<>();
MutablePoint p = new MutablePoint(1, 2);
seen.add(p);
p.x = 10;                               // hash changes, node does not move
System.out.println(seen.contains(p));   // false
System.out.println(seen.size());        // 1, and remove(p) also fails: a leak

The fix is design, not a clever map: make keys immutable (records, String, Integer) or at least never mutate the fields used by equals and hashCode while the object sits in a hash structure. If you must change a key, remove it, change it, and put it back. The equals() and hashCode() contracts

06LinkedHashMap and the LRU cache

LinkedHashMap is a HashMap whose entries are also threaded onto a doubly linked list. By default the list is in insertion order. Pass accessOrder = true and every get or put of an existing key moves that entry to the tail, so the head is always the least recently used entry. After each insertion, the map calls removeEldestEntry(eldest); return true and the head is evicted.

Interview questions for this topicComing soon