sdlc.dev

Java path · Objects and types · Topic 8 of 12

Collections inside: ArrayList and HashMap

Not started

The two collections you use most are thin layers over plain arrays. ArrayList keeps its elements in an Object[] that it replaces with a bigger one when full. HashMap keeps an array of buckets and uses each key's hashCode to choose one. The Javadoc specifies their complexity and behaviour; the exact growth factors and thresholds below are how OpenJDK implements them, and could change.

Why it matters: A bad hashCode, a mutable key or the wrong initial size turns O(1) into O(n). Knowing the internals makes these bugs obvious.

  1. 1ArrayList is an array

    Reading by index is constant time; adding at the end is amortised constant time; inserting or removing in the middle shifts everything after it.

  2. 2HashMap is an array of buckets

    The key's hashCode picks a bucket and equals finds the entry in it, so both methods must agree.

  3. 3Crowded buckets become trees

    In OpenJDK, a bucket that collects 8 or more entries in a large enough table is turned into a red-black tree, which limits the damage a bad hashCode can do.

  4. 4Fail fast

    Changing a collection while iterating over it, other than through the iterator, usually throws ConcurrentModificationException.

1

How it works

The explanation, with examples you can run.

ArrayList

An ArrayList holds a reference to an Object[] and a size. get(i) is an array read. add(x) writes into the next free slot; when the array is full, OpenJDK allocates one about 1.5 times larger and copies everything across. Copying is rare enough that appending is amortised O(1), which is all the Javadoc promises. Inserting or removing anywhere but the end shifts the elements after it, so remove(0) on a million-element list moves a million references.

If you know the final size, say so with new ArrayList<>(n) or ensureCapacity(n) and skip the copies. Remember too that the array holds references: a List<Integer> is an array of pointers to separate boxed objects, much bigger than an int[].

HashMap

A HashMap is an array of buckets whose length is always a power of two (16 by default). To place a key, OpenJDK takes key.hashCode(), mixes the high bits into the low ones (h ^ (h >>> 16)), and uses the low bits as the index. Entries in the same bucket form a short linked list. When the number of entries passes capacity times the load factor (0.75 by default), the table doubles and entries are redistributed.

Two methods carry the whole design:

  • hashCode must return equal values for equal keys, or the lookup searches the wrong bucket.
  • equals decides which entry in the bucket is the right one.

So never mutate a field that hashCode uses while the object is a key: the entry stays in its old bucket and becomes unreachable by lookup. Records and immutable value classes make good keys.

When hashing goes wrong

import java.util.*; public class Buckets {    record Key(int id) {        @Override public int hashCode() { return 1; }   // every key in one bucket    }     public static void main(String[] args) {        Map<Key, String> map = new HashMap<>();        for (int i = 0; i < 10_000; i++) map.put(new Key(i), "v" + i);        System.out.println(map.get(new Key(9_999)));   // still found, just slowly    }}

Every key collides. Since Java 8, OpenJDK limits the damage: once a bucket holds 8 entries (and the table has at least 64 buckets; below that it resizes instead), the bucket is converted to a red-black tree, and back to a list when it shrinks to 6. The tree is ordered by hash first and then, if the keys are Comparable, by compareTo; then lookups are O(log n). Keys like this Key, with identical hashes and no ordering, can still force a search of the whole tree. Give keys a good hashCode and treat the trees as a safety net.

Iterating safely

ArrayList and HashMap iterators are fail-fast: each collection counts structural changes, and the iterator throws ConcurrentModificationException if the count changes underneath it. That is a best-effort bug detector, not a thread-safety mechanism.

List<Integer> list = new ArrayList<>(List.of(1, 2, 3));for (Integer n : list) if (n == 1) list.remove(n);   // ConcurrentModificationExceptionlist.removeIf(n -> n == 1);                          // the safe way

For sharing between threads use ConcurrentHashMap or CopyOnWriteArrayList, not a synchronised wrapper around a HashMap. And Java 21's sequenced collections (JEP 431) give List, Deque, LinkedHashMap and friends a common getFirst(), getLast() and reversed().

2

Check yourself

3 questions. Get them all right to finish this topic.

  1. 1.Which operation on a large ArrayList is slowest?
  2. 2.A class overrides equals but not hashCode. You put an instance in a HashSet, then call contains with an equal instance. What is the likely result?
  3. 3.In OpenJDK 21, what happens when a HashMap bucket collects many colliding keys?

0 of 3 right so far. Get all three to finish this topic.

Go deeper