What a collection actually costs in memory

Key points

• A HashMap entry is an object: hash, key reference, value reference and next pointer - roughly 32 to 40 bytes on top of whatever the key and value are.
• Boxing multiplies that. An Integer is a 16-byte object plus a reference, so Map<Integer, Integer> costs around 70 to 80 bytes per entry to store 8 bytes of actual data.
• A primitive-specialised map from Eclipse Collections, fastutil or Koloboke stores the values in arrays and cuts that by roughly an order of magnitude.
• ArrayList grows by 50% when full, so it can hold up to a third more capacity than size. trimToSize matters for long-lived lists that were built once.
• Integer.valueOf caches -128 to 127, so small boxed values are shared. That is why == appears to work for small numbers and fails above 127 - a classic interview trap with a real memory reason behind it.
• Measure rather than estimate. Nesting collections compounds the overhead quickly, and a Map<String, List<Integer>> with small lists is mostly header bytes.

Example

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class CollectionMemory {

    static long usedMemory() {
        Runtime rt = Runtime.getRuntime();
        for (int i = 0; i < 3; i++) { System.gc(); }
        try { Thread.sleep(50); } catch (InterruptedException ignored) { }
        return rt.totalMemory() - rt.freeMemory();
    }

    public static void main(String[] args) {
        int n = 200_000;

        long before = usedMemory();
        Map<Integer, Integer> boxed = new HashMap<>();
        for (int i = 0; i < n; i++) { boxed.put(i, i * 2); }
        long boxedBytes = usedMemory() - before;

        System.out.println("HashMap<Integer,Integer> with " + n + " entries");
        System.out.println("  approx bytes      : " + boxedBytes);
        System.out.println("  bytes per entry   : " + (boxedBytes / n));
        System.out.println("  actual data       : " + (n * 8L) + " bytes (two ints)");

        // Parallel primitive arrays - the same data, no objects at all.
        before = usedMemory();
        int[] keys = new int[n];
        int[] values = new int[n];
        for (int i = 0; i < n; i++) { keys[i] = i; values[i] = i * 2; }
        long arrayBytes = usedMemory() - before;

        System.out.println();
        System.out.println("two int[] arrays");
        System.out.println("  approx bytes      : " + arrayBytes);
        System.out.println("  bytes per entry   : " + (arrayBytes / n));
        if (arrayBytes > 0) {
            System.out.println("  ratio             : ~"
                    + (boxedBytes / Math.max(arrayBytes, 1)) + "x more for the map");
        }

        // ArrayList growth: capacity outruns size by up to 50%.
        List<String> list = new ArrayList<>();
        for (int i = 0; i < 100; i++) { list.add("x"); }
        System.out.println();
        System.out.println("ArrayList size = " + list.size()
                + "  (internal capacity is larger - grows by 50% each time)");

        // The Integer cache: why == sometimes works.
        Integer a = 127, b = 127, c = 128, d = 128;
        System.out.println();
        System.out.println("Integer 127 == 127 : " + (a == b) + "   (cached, shared)");
        System.out.println("Integer 128 == 128 : " + (c == d) + "  (outside the cache)");
        System.out.println("128.equals(128)    : " + c.equals(d));
    }
}

A boxed map costs roughly ten times the data it stores - use primitive arrays or a specialised map when the count is large.