Capacity, load factor and resizing

Key points

• A HashMap starts with 16 buckets and a load factor of 0.75, so it resizes as the 13th entry goes in.
• A resize allocates a table twice the size and moves every entry into it. Doing that repeatedly costs real time.
• Capacity is always rounded up to a power of two, so the bucket index can be a cheap bit mask.
• Pre-size with new HashMap<>((int)(n / 0.75f) + 1), or HashMap.newHashMap(n) on Java 19 and later.
• ArrayList grows by about half its size each time and copies the array. new ArrayList<>(n) avoids all of it.
• Only tune when the size is known and large. For a handful of entries the defaults are already right.

Example

import java.util.*;

public class Main {
    static final int N = 400_000;

    public static void main(String[] args) {
        System.out.println("default HashMap   : capacity 16, load factor 0.75, threshold 12");
        System.out.println("each resize       : new table, every entry rehashed and moved");
        System.out.println("table for " + N + "  : " + tableSizeFor((int) (N / 0.75f) + 1) + " slots");

        long grown = time(() -> {
            Map<Integer, Integer> m = new HashMap<>();
            for (int i = 0; i < N; i++) m.put(i, i);
        });
        long sized = time(() -> {
            Map<Integer, Integer> m = new HashMap<>((int) (N / 0.75f) + 1);
            for (int i = 0; i < N; i++) m.put(i, i);
        });
        System.out.println("HashMap growing   : " + grown + " ms");
        System.out.println("HashMap pre-sized : " + sized + " ms");

        long listGrown = time(() -> {
            List<Integer> l = new ArrayList<>();
            for (int i = 0; i < N; i++) l.add(i);
        });
        long listSized = time(() -> {
            List<Integer> l = new ArrayList<>(N);
            for (int i = 0; i < N; i++) l.add(i);
        });
        System.out.println("ArrayList growing : " + listGrown + " ms");
        System.out.println("ArrayList sized   : " + listSized + " ms");
    }

    static int tableSizeFor(int wanted) {
        int n = 1;
        while (n < wanted) n <<= 1;
        return n;
    }

    static long time(Runnable r) {
        long t = System.nanoTime();
        r.run();
        return (System.nanoTime() - t) / 1_000_000;
    }
}

Growth is copying. If you know roughly how many entries there will be, say so at construction.