Java Collections Performance, Measured on JDK 26

Series: Java lecture 3/6 (intermediate). For developers who already write Java classes and want to pick List, Set, Map and Deque implementations from evidence rather than habit. After this lecture you will be able to predict which collection gets slow, avoid the two exceptions that collections throw at beginners, and time your own code without a benchmarking library.

If you write Java for a backend, an Android app or a coding interview, you pick a collection several times a day, and most of the time ArrayList and HashMap are the right answer. This post is for the other times: when a list is used as a queue, when a TreeMap is chosen "because sorted is nice", when a loop removes elements and crashes. Every number below was measured on our machine and every error was copied from a real run.

Environment: OpenJDK 26 (Temurin build 26+35), Apple Silicon Mac (M1 Pro, 8 cores), macOS. Programs were run with java -Xms3g -Xmx3g so heap resizing does not show up in the timings. Random data uses new Random(42).

How we measured without JMH

The right tool for Java micro-benchmarks is JMH. We did not use it, because this series runs only what ships with the JDK and nothing may be installed. Instead, every case goes through one small helper: run the task a few times untimed so the JIT compiler can compile it (warm-up), then time several runs and report the median.

static long sink; // results are added here so the JIT cannot delete the work

static double measure(String name, int warmup, int runs, LongSupplier task) {
    for (int i = 0; i < warmup; i++) sink += task.getAsLong();
    double[] t = new double[runs];
    for (int i = 0; i < runs; i++) {
        long s = System.nanoTime();
        sink += task.getAsLong();
        t[i] = (System.nanoTime() - s) / 1e6;
    }
    Arrays.sort(t);
    System.out.printf("%-34s median %9.3f ms  (min %.3f, max %.3f)%n",
                      name, t[runs / 2], t[0], t[runs - 1]);
    return t[runs / 2];
}

This is good enough to see differences of 2x or more. It is not good enough to settle a 10% argument: there is no fork per benchmark, no dead-code analysis, and GC pauses land wherever they land. We ran the benchmark four times; the outputs below are from one run, and where runs disagreed, we give the range. The complete file is at the end of the post.

ArrayList vs LinkedList: get(i), add at the front, iteration

Both implement List, so they look interchangeable. They are not. ArrayList is a resizable array; LinkedList is a chain of node objects, each with prev and next pointers.

== get(i) x 10,000 random indexes, size 100,000
ArrayList.get                      median     0.082 ms  (min 0.058, max 0.355)
LinkedList.get                     median   454.775 ms  (min 451.945, max 463.801)
== add(0, x) x 50,000 into an empty list
ArrayList.add(0,x)                 median   117.930 ms  (min 116.612, max 122.530)
LinkedList.addFirst                median     0.483 ms  (min 0.397, max 0.761)
ArrayDeque.addFirst                median     0.633 ms  (min 0.571, max 0.691)
== for-each over 1,000,000 elements
ArrayList iterate                  median     0.968 ms  (min 0.964, max 0.977)
LinkedList iterate                 median     1.923 ms  (min 1.909, max 1.937)

Read the three blocks separately:

• get(i): LinkedList.get(i) walks from the nearer end, up to 50,000 hops on a 100,000-element list. Ten thousand random reads took 455 ms against 0.08 ms. A for (int i = 0; i < list.size(); i++) list.get(i) loop over a LinkedList is quadratic, and it is the most common way this class hurts people.
• add at the front: here LinkedList wins by a factor of about 240, because ArrayList.add(0, x) shifts every existing element. But ArrayDeque does the same job in the same time, with less memory per element.
• iteration: even sequential reading, the case where linked lists should be fine, was twice as slow. Each node is a separate object, so the CPU follows pointers instead of reading consecutive memory.

The practical rule: if you need the front, you need a Deque, and the default Deque is ArrayDeque. We have not found a case in application code where LinkedList was the best choice. If you want to see why linked structures behave like this, our linked list walkthrough builds one by hand.

HashMap vs TreeMap lookups, and ArrayDeque vs Stack

== 1,000,000 lookups, 100,000 String keys
HashMap.get                        median     9.623 ms  (min 9.493, max 10.595)
TreeMap.get                        median   259.214 ms  (min 238.363, max 322.357)
== push+pop 1,000,000 (stack use)
Stack push/pop                     median     4.674 ms  (min 4.252, max 5.679)
ArrayDeque push/pop                median     6.911 ms  (min 6.600, max 144.144)

TreeMap was 27 times slower here (across our four runs the HashMap median ranged from 8.9 to 17.2 ms and TreeMap from 259 to 380 ms). Two reasons stack up. A red-black tree with 100,000 keys is about 17 levels deep, so each lookup does around 17 comparisons instead of one hash and usually one equals. And our keys look like "user-12345": every compareTo first walks through the shared "user-" prefix. Real IDs, URLs and file paths share prefixes all the time. TreeMap earns its cost when you need firstKey(), headMap(), ceilingKey() or sorted iteration; if you only need lookups, it is the wrong map. (The tree itself is covered in our binary search tree post.)

The Stack result surprised us. The usual advice is "Stack is synchronized, so it is slow". On JDK 26, an uncontended lock is cheap, and Stack was not slower in any of the four runs (medians 4.7 to 7.0 ms vs 5.3 to 11.3 ms for ArrayDeque, with GC noise on both). So the reason to avoid Stack is its API, not speed:

Stack<String> st = new Stack<>();
ArrayDeque<String> dq = new ArrayDeque<>();
for (String s : List.of("a", "b", "c")) { st.push(s); dq.push(s); }
System.out.println("Stack      " + st + "  peek=" + st.peek());
System.out.println("ArrayDeque " + dq + "  peek=" + dq.peek());

Stack      [a, b, c]  peek=c
ArrayDeque [c, b, a]  peek=c

Both return c from peek(), but Stack iterates and prints bottom-to-top, because it is a Vector underneath. It also lets any caller do st.get(0) or st.add(x) and break the stack discipline. ArrayDeque iterates in pop order and exposes only deque operations. One limit: ArrayDeque rejects null elements with a NullPointerException.

Boxing cost and initial capacity

A List<Integer> holds references to Integer objects, not numbers. Summing ten million values:

== sum of 10,000,000 ints
int[] sum                          median     3.281 ms  (min 3.205, max 3.306)
List<Integer> sum (0..999)         median     6.814 ms  (min 6.670, max 6.951)
List<Integer> sum (distinct)       median     6.764 ms  (min 6.663, max 6.869)

The boxed list was about twice as slow. We tried two versions: values 0..999 (which come from the Integer cache, so the list holds only 1,000 distinct objects) and values 0..9,999,999 (ten million separate objects). The time was the same, because both are allocated in order and sit close together in memory. In a long-running server, where objects are created at different times, they scatter, and the gap tends to grow. The bigger cost is memory: on a 64-bit JVM with compressed pointers, each list slot is a 4-byte reference plus a 16-byte Integer object, against 4 bytes in an int[].

Initial capacity is the other cheap win. A new ArrayList starts empty, allocates 10 slots on the first add, then grows by 50% each time it fills, copying the old array. We measured the bytes allocated by the current thread with ThreadMXBean.getThreadAllocatedBytes (part of the JDK, no install):

grow steps to reach 1000000: 29
allocated, default capacity : 14,586,416 bytes
allocated, new ArrayList<>(N): 4,000,040 bytes
median time, default  : 2.505 ms
median time, presized : 2.205 ms

Filling 1,000,000 elements without a capacity allocated 3.6 times as much memory (all the abandoned intermediate arrays) and took about 12% longer. The memory number is exact and repeatable; the time difference is small. When you know the size, as when converting one collection to another, pass it. For a HashMap, Java 19 added HashMap.newHashMap(n), which accounts for the 0.75 load factor; new HashMap<>(n) gives you a map that resizes before reaching n entries.

Common mistake: ConcurrentModificationException

This is the first collection exception almost everyone meets. Remove even numbers while looping:

import java.util.*;

public class Cme {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
        for (Integer n : nums) {
            if (n % 2 == 0) nums.remove(n);   // remove(Object) while iterating
        }
        System.out.println(nums);
    }
}

What actually happens (java Cme.java):

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1104)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1058)
    at Cme.main(Cme.java:6)

The for-each loop is compiled into an Iterator. ArrayList counts structural changes in a field called modCount, and the iterator compares it on every next(). Line 6 is the for line, not the remove line: the removal succeeded, and the next step of the loop noticed. Note that "concurrent" here has nothing to do with threads.

Worse, the check does not always fire. Remove the second-to-last element and the loop ends before next() is called again:

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer n : nums) {
    if (n == 3) nums.remove(n);
}
System.out.println(nums);

[1, 2, 4]

No exception, and it worked by luck. Code like this passes a test with one data set and fails in production with another. Javadoc calls the check "best-effort" for exactly this reason.

Fix: say what you mean.

List<Integer> a = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
a.removeIf(n -> n % 2 == 0);
System.out.println("removeIf      " + a);

List<Integer> b = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
for (Iterator<Integer> it = b.iterator(); it.hasNext(); )
    if (it.next() % 2 == 0) it.remove();
System.out.println("it.remove()   " + b);

removeIf      [1, 3, 5]
it.remove()   [1, 3, 5]

Prefer removeIf: on ArrayList it compacts the array once, while repeated it.remove() shifts the tail on every call. Use the explicit iterator when the decision needs more than a predicate, such as logging each removed item.

Common mistake: List.of is read-only

List.of, Set.of and Map.of (Java 9+) return immutable collections. That is useful, but nothing in the type says so: they are plain List<String>.

List<String> a = Arrays.asList("x", "y");
a.set(0, "X");                       // fine: fixed-size, not read-only
System.out.println(a);
List<String> fixed = List.of("x", "y");
try { a.add("z"); } catch (UnsupportedOperationException e) { System.out.println("Arrays.asList add -> " + e); }
try { fixed.contains(null); } catch (NullPointerException e) { System.out.println("List.of contains(null) -> " + e); }
fixed.add("z");

[X, y]
Arrays.asList add -> java.lang.UnsupportedOperationException
List.of contains(null) -> java.lang.NullPointerException
Exception in thread "main" java.lang.UnsupportedOperationException
    at java.base/java.util.ImmutableCollections.uoe(ImmutableCollections.java:145)
    at java.base/java.util.ImmutableCollections$AbstractImmutableCollection.add(ImmutableCollections.java:150)
    at Immutable.main(Immutable.java:11)

Three different contracts hide behind one interface. Arrays.asList is fixed-size but lets you set. List.of rejects every change, and also rejects null, even in contains(null). The compiler cannot catch any of this; you find out at runtime. The fix is to copy when you intend to modify: new ArrayList<>(List.of(...)), which is what the examples above do.

Sequenced collections (Java 21): getFirst, getLast, reversed

Before Java 21, "the last element" was list.get(list.size() - 1) for a list, deque.peekLast() for a deque, and a loop for a LinkedHashSet. Java 21 added the SequencedCollection, SequencedSet and SequencedMap interfaces with one vocabulary for all of them:

List<String> list = new ArrayList<>(List.of("mon", "tue", "wed"));
System.out.println(list.getFirst() + " " + list.getLast() + " " + list.reversed());
LinkedHashMap<String, Integer> lhm = new LinkedHashMap<>();
lhm.put("x", 1); lhm.put("y", 2); lhm.putFirst("w", 0);
System.out.println(lhm + " first=" + lhm.firstEntry() + " reversed=" + lhm.reversed());
LinkedHashSet<String> set = new LinkedHashSet<>(List.of("b", "c"));
set.addFirst("a");
System.out.println(set + " last=" + set.getLast());
List<String> rev = list.reversed();
rev.add("thu");          // writes through: adds at the FRONT of the original
System.out.println("original after rev.add: " + list);

mon wed [wed, tue, mon]
{w=0, x=1, y=2} first=w=0 reversed={y=2, x=1, w=0}
[a, b, c] last=c
original after rev.add: [thu, mon, tue, wed]

Two details matter. reversed() returns a view, not a copy: adding to the end of the view added "thu" at the front of the original. And getFirst() on an empty list throws NoSuchElementException, unlike peekFirst() on a deque, which returns null. We confirmed the version: compiling the same code with javac --release 20 fails with error: cannot find symbol ... method getFirst(), and --release 21 compiles.

Decision table

Honest limits and version notes

• Not JMH. Our harness has warm-up and medians but no forked JVMs, no blackhole and no statistical error bars. Treat 2x and larger gaps as real and anything under ~20% as "about the same". GC pauses caused the max values (one ArrayDeque run hit 144 ms).
• One machine. Apple Silicon (M1 Pro), OpenJDK 26, G1 GC (the default). Cache sizes differ on x86 servers; ratios usually hold, absolute numbers do not.
• Versions checked: List.of needs Java 9 (--release 8 fails with cannot find symbol ... method of(String,String); --release 9 compiles). Sequenced collections need Java 21 (checked with --release 20 and 21). HashMap.newHashMap is Java 19; we only ran it on 26. Everything else was run on 26 only.
• We did not measure concurrent collections (ConcurrentHashMap, CopyOnWriteArrayList). They belong with lecture 5 on virtual threads and concurrency.
• C# developers will recognize most of these trade-offs from generic collections in C#; the Java-specific parts are boxing and Stack extends Vector.

Run it yourself

Save as CollBench.java and run java -Xms3g -Xmx3g CollBench.java (it needs about 3 GB of heap and runs for roughly a minute):

import java.util.*;
import java.util.function.*;

public class CollBench {
    static long sink;

    static double measure(String name, int warmup, int runs, LongSupplier task) {
        for (int i = 0; i < warmup; i++) sink += task.getAsLong();
        double[] t = new double[runs];
        for (int i = 0; i < runs; i++) {
            long s = System.nanoTime();
            sink += task.getAsLong();
            t[i] = (System.nanoTime() - s) / 1e6;
        }
        Arrays.sort(t);
        System.out.printf("%-34s median %9.3f ms  (min %.3f, max %.3f)%n", name, t[runs / 2], t[0], t[runs - 1]);
        return t[runs / 2];
    }

    public static void main(String[] args) {
        final int N = 100_000;
        Random rnd = new Random(42);
        int[] idx = new int[10_000];
        for (int i = 0; i < idx.length; i++) idx[i] = rnd.nextInt(N);

        List<Integer> al = new ArrayList<>(), ll = new LinkedList<>();
        for (int i = 0; i < N; i++) { al.add(i); ll.add(i); }
        System.out.println("== get(i) x 10,000 random indexes, size 100,000");
        measure("ArrayList.get", 5, 7, () -> { long s = 0; for (int i : idx) s += al.get(i); return s; });
        measure("LinkedList.get", 2, 5, () -> { long s = 0; for (int i : idx) s += ll.get(i); return s; });

        System.out.println("== add(0, x) x 50,000 into an empty list");
        measure("ArrayList.add(0,x)", 3, 5, () -> { List<Integer> l = new ArrayList<>(); for (int i = 0; i < 50_000; i++) l.add(0, i); return l.size(); });
        measure("LinkedList.addFirst", 3, 5, () -> { LinkedList<Integer> l = new LinkedList<>(); for (int i = 0; i < 50_000; i++) l.addFirst(i); return l.size(); });
        measure("ArrayDeque.addFirst", 3, 5, () -> { ArrayDeque<Integer> l = new ArrayDeque<>(); for (int i = 0; i < 50_000; i++) l.addFirst(i); return l.size(); });

        System.out.println("== for-each over 1,000,000 elements");
        List<Integer> al2 = new ArrayList<>(), ll2 = new LinkedList<>();
        for (int i = 0; i < 1_000_000; i++) { al2.add(i % 1000); ll2.add(i % 1000); }
        measure("ArrayList iterate", 10, 9, () -> { long s = 0; for (int v : al2) s += v; return s; });
        measure("LinkedList iterate", 10, 9, () -> { long s = 0; for (int v : ll2) s += v; return s; });

        System.out.println("== 1,000,000 lookups, 100,000 String keys");
        Map<String, Integer> hm = new HashMap<>(), tm = new TreeMap<>();
        String[] keys = new String[N];
        for (int i = 0; i < N; i++) { keys[i] = "user-" + i; hm.put(keys[i], i); tm.put(keys[i], i); }
        String[] q = new String[1_000_000];
        for (int i = 0; i < q.length; i++) q[i] = keys[rnd.nextInt(N)];
        measure("HashMap.get", 5, 7, () -> { long s = 0; for (String k : q) s += hm.get(k); return s; });
        measure("TreeMap.get", 5, 7, () -> { long s = 0; for (String k : q) s += tm.get(k); return s; });

        System.out.println("== push+pop 1,000,000 (stack use)");
        measure("Stack push/pop", 5, 7, () -> { Stack<Integer> st = new Stack<>(); for (int i = 0; i < 1_000_000; i++) st.push(i & 1023); long s = 0; while (!st.isEmpty()) s += st.pop(); return s; });
        measure("ArrayDeque push/pop", 5, 7, () -> { ArrayDeque<Integer> st = new ArrayDeque<>(); for (int i = 0; i < 1_000_000; i++) st.push(i & 1023); long s = 0; while (!st.isEmpty()) s += st.pop(); return s; });

        System.out.println("== sum of 10,000,000 ints");
        int M = 10_000_000;
        int[] arr = new int[M];
        List<Integer> boxed = new ArrayList<>(M);
        for (int i = 0; i < M; i++) { arr[i] = i % 1000; boxed.add(i % 1000); }
        measure("int[] sum", 10, 9, () -> { long s = 0; for (int v : arr) s += v; return s; });
        measure("List<Integer> sum (0..999)", 10, 9, () -> { long s = 0; for (int v : boxed) s += v; return s; });
        List<Integer> boxedBig = new ArrayList<>(M);
        for (int i = 0; i < M; i++) boxedBig.add(i);
        measure("List<Integer> sum (distinct)", 10, 9, () -> { long s = 0; for (int v : boxedBig) s += v; return s; });
        System.out.println("sink=" + (sink != 0));
    }
}

(The capacity numbers came from a separate 40-line program using com.sun.management.ThreadMXBean; the measuring idea is the same.)

---

Previous: Lecture 2: classes, records and interfaces · Next: Lecture 4: streams, lambdas and Optional