Primitive Collections and Memory Cost

Standard collections hold references, so an int stored in a List<Integer> or a HashMap<Integer, Integer> becomes an Integer object. This lesson measures what that costs in objects and bytes, then shows the alternatives: plain arrays, BitSet, and hash maps that store primitives directly (fastutil and Agrona). It ends with a table for choosing a collection. Object headers and JOL are introduced in Object Layout and Allocation; buckets and load factor in HashMap Internals.

Structure	Stores	Objects per element
`int[]`	`int` values inline	0
`ArrayList<Integer>`	references to `Integer`	1 (`Integer`)
`HashMap<Integer, Integer>`	references to nodes	3 (`Node`, key, value)
`BitSet`	1 bit per possible value	0
`Int2IntOpenHashMap`, `Int2IntHashMap`	`int` keys and values in arrays	0

The memory examples run with compressed references on and compact object headers off, so the byte counts do not depend on the machine's heap size. JOL prints two warning lines on startup; they do not affect the numbers.

Example 1: boxing and the Integer cache

Boxing converts a primitive to its wrapper object, for example int to Integer, and happens automatically when a primitive goes into a collection. Integer.valueOf returns cached objects for values from -128 to 127 (the upper bound can be raised with -XX:AutoBoxCacheMax), and a new object for any other value.

Java

import java.util.ArrayList;
import java.util.IdentityHashMap;
import java.util.List;

public class BoxingCount {
    static int distinctObjects(List<Integer> list) {
        IdentityHashMap<Integer, Boolean> seen = new IdentityHashMap<>();
        for (Integer i : list) seen.put(i, true);       // keyed by identity, not equals
        return seen.size();
    }

    public static void main(String[] args) {
        List<Integer> small = new ArrayList<>();
        List<Integer> large = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            small.add(i % 100);              // values 0..99, all cached
            large.add(1000 + i % 100);       // values 1000..1099, not cached
        }
        System.out.println("small values: 1000 elements, distinct Integer objects = "
                + distinctObjects(small));
        System.out.println("large values: 1000 elements, distinct Integer objects = "
                + distinctObjects(large));
        System.out.println("valueOf(127) == valueOf(127): " + (Integer.valueOf(127) == Integer.valueOf(127)));
        System.out.println("valueOf(128) == valueOf(128): " + (Integer.valueOf(128) == Integer.valueOf(128)));
    }
}

Output

small values: 1000 elements, distinct Integer objects = 100
large values: 1000 elements, distinct Integer objects = 1000
valueOf(127) == valueOf(127): true
valueOf(128) == valueOf(128): false

Each add(1000 + i % 100) created a new Integer, even for a value already in the list. Comparing boxed values with == compares identities, which is why the last line differs from the line above it.

Example 2: int[] vs ArrayList<Integer> in bytes

JOL's GraphLayout.parseInstance walks every object reachable from a root and reports the count and total size.

Java

import java.util.ArrayList;
import java.util.List;
import org.openjdk.jol.info.GraphLayout;

public class ArrayVsList {
    public static void main(String[] args) {
        int n = 10_000;
        int[] array = new int[n];
        List<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            array[i] = 1_000 + i;
            list.add(1_000 + i);
        }
        GraphLayout a = GraphLayout.parseInstance((Object) array);
        GraphLayout l = GraphLayout.parseInstance(list);
        System.out.println("int[]              objects " + a.totalCount() + ", bytes " + a.totalSize()
                + ", per element " + a.totalSize() / n);
        System.out.println("ArrayList<Integer> objects " + l.totalCount() + ", bytes " + l.totalSize()
                + ", per element " + l.totalSize() / n);
    }
}

Output

# WARNING: Unable to attach Serviceability Agent. HotSpot Serviceability Agent attach skipped due to jol.skipHotspotSAAttach flag.
int[]              objects 1, bytes 40016, per element 4
ArrayList<Integer> objects 10002, bytes 200040, per element 20

An int element takes 4 bytes. In the list, each element is a 4-byte compressed reference plus a 16-byte Integer (12-byte header and 4-byte value). The list also scatters values across the heap, so a loop over it follows a reference per element, while a loop over int[] reads consecutive memory.

Example 3: BitSet for sets of small non-negative ints

BitSet stores one bit per possible value in a long[], so a set of ints in the range 0 to n takes about n / 8 bytes regardless of how many values are present. It is the right choice when the values are dense and bounded, such as ids, slot numbers, or flags.

Java

import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;
import org.openjdk.jol.info.GraphLayout;

public class BitSetDemo {
    public static void main(String[] args) {
        BitSet bits = new BitSet(100_000);
        Set<Integer> hash = new HashSet<>();
        for (int i = 0; i < 100_000; i += 3) {
            bits.set(i);
            hash.add(i);
        }
        System.out.println("cardinality " + bits.cardinality() + ", hash size " + hash.size());
        System.out.println("contains 300: " + bits.get(300) + ", contains 301: " + bits.get(301));
        System.out.println("next set bit after 301: " + bits.nextSetBit(301));

        BitSet evens = new BitSet();
        for (int i = 0; i < 100_000; i += 2) evens.set(i);
        evens.and(bits);                                   // set intersection, 64 bits per step
        System.out.println("multiples of 6 below 100000: " + evens.cardinality());

        System.out.println("BitSet bytes:  " + GraphLayout.parseInstance(bits).totalSize());
        System.out.println("HashSet bytes: " + GraphLayout.parseInstance(hash).totalSize());
    }
}

Output

cardinality 33334, hash size 33334
contains 300: true, contains 301: false
next set bit after 301: 303
multiples of 6 below 100000: 16667
# WARNING: Unable to attach Serviceability Agent. HotSpot Serviceability Agent attach skipped due to jol.skipHotspotSAAttach flag.
BitSet bytes:  12544
HashSet bytes: 1862272

and, or, and xor combine 64 values per long operation. A BitSet holding one value near 1,000,000 still allocates about 125 KB, so sparse or unbounded values need a hash set instead.

Example 4: open addressing vs chaining

HashMap uses chaining: each bucket holds a linked list (or tree) of node objects. Open addressing stores entries directly in the table arrays; on a collision it probes other slots in a fixed sequence until it finds the key or an empty slot. Linear probing tries the next slot, then the next. With open addressing there are no node objects, and keys and values can be primitive arrays. The table must keep free slots, so the load factor stays below 1, and a key value is reserved (or tracked separately) to mean "empty". The program below is a minimal open-addressing map from int to int.

Java

import java.util.Arrays;

public class IntIntMap {
    private static final int EMPTY = Integer.MIN_VALUE;   // reserved: cannot be a key
    private int[] keys;
    private int[] values;
    private int size;
    private long probes;

    IntIntMap(int capacity) {             // capacity: power of two
        keys = new int[capacity];
        values = new int[capacity];
        Arrays.fill(keys, EMPTY);
    }

    private int slot(int key) {
        int h = key * 0x9E3779B9;          // multiply to mix bits
        int mask = keys.length - 1;
        int i = (h ^ (h >>> 16)) & mask;
        while (keys[i] != EMPTY && keys[i] != key) {
            i = (i + 1) & mask;            // linear probing
            probes++;
        }
        return i;
    }

    void put(int key, int value) {
        if (key == EMPTY) throw new IllegalArgumentException("reserved key");
        if ((size + 1) * 2 > keys.length) resize();      // load factor 0.5
        int i = slot(key);
        if (keys[i] == EMPTY) { keys[i] = key; size++; }
        values[i] = value;
    }

    int get(int key, int missing) {
        int i = slot(key);
        return keys[i] == EMPTY ? missing : values[i];
    }

    private void resize() {
        int[] oldKeys = keys, oldValues = values;
        keys = new int[oldKeys.length * 2];
        values = new int[oldKeys.length * 2];
        Arrays.fill(keys, EMPTY);
        size = 0;
        for (int j = 0; j < oldKeys.length; j++) {
            if (oldKeys[j] != EMPTY) put(oldKeys[j], oldValues[j]);
        }
    }

    public static void main(String[] args) {
        IntIntMap m = new IntIntMap(16);
        for (int k = 0; k < 1_000; k++) m.put(k * 64, k);
        System.out.println("size " + m.size + ", table length " + m.keys.length);
        System.out.println("get(640) = " + m.get(640, -1) + ", get(641) = " + m.get(641, -1));
        System.out.println("extra probes recorded > 0: " + (m.probes > 0));
    }
}

Output

size 1000, table length 2048
get(640) = 10, get(641) = -1
extra probes recorded > 0: true

Removal is the hard part of open addressing: emptying a slot would break the probe chain of keys stored after it. Libraries either shift later entries back (fastutil and Agrona do this for their linear-probing maps) or leave a "deleted" marker. This sketch has no remove for that reason.

Example 5: fastutil Int2IntOpenHashMap

fastutil (version 8.5.16 here) generates a map class for each pair of primitive types. Int2IntOpenHashMap keeps keys and values in two int[] arrays with linear probing and a default load factor of 0.75 (Hash.DEFAULT_LOAD_FACTOR). get(int) returns an int; a missing key returns the default return value, 0 unless changed with defaultReturnValue. addTo(key, delta) adds to a counter in one lookup.

Java

import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;

public class FastutilCounts {
    public static void main(String[] args) {
        int[] instrumentIds = {7, 3, 7, 9, 7, 3, 0, 0};
        Int2IntOpenHashMap fills = new Int2IntOpenHashMap();
        fills.defaultReturnValue(-1);

        for (int id : instrumentIds) {
            fills.addTo(id, 1);          // missing key starts from the default return value
        }
        fills.defaultReturnValue(0);
        Int2IntOpenHashMap counts = new Int2IntOpenHashMap();
        for (int id : instrumentIds) counts.addTo(id, 1);

        System.out.println("counts: 7->" + counts.get(7) + " 3->" + counts.get(3)
                + " 9->" + counts.get(9) + " 0->" + counts.get(0) + " 5->" + counts.get(5));
        System.out.println("containsKey(5): " + counts.containsKey(5) + ", size " + counts.size());
        System.out.println("addTo with default -1, key 9: " + fills.get(9));
    }
}

Output

counts: 7->3 3->2 9->1 0->2 5->0
containsKey(5): false, size 4
addTo with default -1, key 9: 0

addTo on a missing key stores defaultReturnValue() + delta, so a counter map needs the default left at 0. The key 0 is stored in a separate slot, which is how the map allows every int as a key. fastutil maps also implement java.util.Map<Integer, Integer>, but the methods taking Integer box, so hot code calls the int overloads.

Example 6: Agrona Int2IntHashMap and Int2ObjectHashMap

Agrona (version 2.3.0 here) is a library for low-latency code. Int2IntHashMap takes a missing value in its constructor: get returns it for an absent key, and it cannot be stored as a value. Int2ObjectHashMap<V> maps int keys to objects and returns null for a missing key. Both use linear probing with a default load factor of 0.65 (Hashing.DEFAULT_LOAD_FACTOR).

Java

import org.agrona.collections.Int2IntHashMap;
import org.agrona.collections.Int2ObjectHashMap;

public class AgronaMaps {
    record Order(int id, String side, long qty) {}

    public static void main(String[] args) {
        Int2IntHashMap position = new Int2IntHashMap(Integer.MIN_VALUE);
        position.put(42, 100);
        position.merge(42, -30, Integer::sum);
        System.out.println("position 42 = " + position.get(42));
        System.out.println("position 43 missing: " + (position.get(43) == position.missingValue()));
        try {
            position.put(44, Integer.MIN_VALUE);
        } catch (IllegalArgumentException e) {
            System.out.println("storing the missing value: IllegalArgumentException");
        }

        Int2ObjectHashMap<Order> byId = new Int2ObjectHashMap<>();
        byId.put(1, new Order(1, "BUY", 500));
        byId.put(2, new Order(2, "SELL", 200));
        Order created = byId.computeIfAbsent(3, id -> new Order(id, "BUY", 0));
        System.out.println("order 2: " + byId.get(2));
        System.out.println("created: " + created + ", size " + byId.size());
        System.out.println("order 9: " + byId.get(9));
    }
}

Output

position 42 = 70
position 43 missing: true
storing the missing value: IllegalArgumentException
order 2: Order[id=2, side=SELL, qty=200]
created: Order[id=3, side=BUY, qty=0], size 3
order 9: null

Example 7: memory per entry, measured

The program fills five structures with the same 10,000 int to int pairs and prints bytes per entry. Keys are spread out (multiples of 7) so most are outside the Integer cache.

Java

import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import java.util.HashMap;
import java.util.TreeMap;
import org.agrona.collections.Int2IntHashMap;
import org.openjdk.jol.info.GraphLayout;

public class PerEntry {
    static void report(String name, Object root, int n) {
        GraphLayout g = GraphLayout.parseInstance(root);
        System.out.printf("%-22s objects %6d  bytes %7d  per entry %3d%n",
                name, g.totalCount(), g.totalSize(), g.totalSize() / n);
    }

    public static void main(String[] args) {
        int n = 10_000;
        HashMap<Integer, Integer> hash = new HashMap<>();
        TreeMap<Integer, Integer> tree = new TreeMap<>();
        Int2IntOpenHashMap fast = new Int2IntOpenHashMap();
        Int2IntHashMap agrona = new Int2IntHashMap(-1);
        int[] sortedKeys = new int[n], sortedValues = new int[n];
        for (int i = 0; i < n; i++) {
            int key = i * 7, value = i * 3;
            hash.put(key, value);
            tree.put(key, value);
            fast.put(key, value);
            agrona.put(key, value);
            sortedKeys[i] = key;
            sortedValues[i] = value;
        }
        report("HashMap<Integer,Int>", hash, n);
        report("TreeMap<Integer,Int>", tree, n);
        report("Int2IntOpenHashMap", fast, n);
        report("Agrona Int2IntHashMap", agrona, n);
        report("two sorted int[]", new Object[]{sortedKeys, sortedValues}, n);
        System.out.println("binary search for 700: value "
                + sortedValues[java.util.Arrays.binarySearch(sortedKeys, 700)]);
    }
}

Output

# WARNING: Unable to attach Serviceability Agent. HotSpot Serviceability Agent attach skipped due to jol.skipHotspotSAAttach flag.
HashMap<Integer,Int>   objects  29995  bytes  705488  per entry  70
TreeMap<Integer,Int>   objects  29994  bytes  719936  per entry  71
Int2IntOpenHashMap     objects      3  bytes  131184  per entry  13
Agrona Int2IntHashMap  objects      2  bytes  131136  per entry  13
two sorted int[]       objects      3  bytes   80056  per entry   8
binary search for 700: value 300

Structure	Where the bytes go
`HashMap`	32-byte `Node`, two 16-byte `Integer` objects, a 4-byte table slot with spare capacity
`TreeMap`	40-byte `Entry` (key, value, left, right, parent, color), two `Integer` objects
Primitive hash maps	8 bytes per slot (key and value), times spare slots from the load factor
Sorted `int[]` pair	8 bytes per entry, O(log n) lookup, O(n) insert

The node and Integer objects also cost GC work: a collector traces each live object, and each insert into a boxed map allocates up to three new objects. GC cost is covered in GC Fundamentals.

Choosing a collection

Need	Choose	Reason
Fixed or known count of primitives	`int[]`, `long[]`	no objects, contiguous memory
Growable list of objects	`ArrayList`	amortized O(1) append, contiguous references
Set of dense ints in a known range	`BitSet`	1 bit per value, bulk `and`/`or`
General key-value, object keys	`HashMap`	standard, O(1) average
Sorted keys or range queries	`TreeMap`, sorted arrays	O(log n) navigation
Primitive keys or values, hot path or large size	fastutil or Agrona maps	no boxing, 2 to 8 times less memory
Read-mostly lookup table built once	sorted primitive arrays plus `Arrays.binarySearch`	smallest footprint
Shared between threads	concurrent collections	see Concurrent Collections

Primitive maps have costs too: a reserved missing value (Agrona) or a default return value (fastutil) that callers must not confuse with a stored value, another dependency, and APIs that differ from java.util.

Interview points

Boxing creates an Integer per value outside -128..127; == on boxed values compares identity.
ArrayList<Integer> costs about 20 bytes per element with compressed references; int[] costs 4.
HashMap<Integer, Integer> allocates a node and up to two boxes per entry, about 70 bytes per entry for 10,000 entries in Example 7.
Chaining stores nodes per bucket; open addressing stores entries in arrays and probes on collision, which removes per-entry objects.
Removing from a linear-probing table requires shifting entries back or marking deleted slots.
fastutil Int2IntOpenHashMap: get(int) returns defaultReturnValue() when missing; addTo updates a counter in one lookup; load factor 0.75.
Agrona Int2IntHashMap: the missing value is chosen in the constructor and cannot be stored; load factor 0.65.
BitSet suits dense bounded ints; its memory depends on the largest value, not the count.

Summary

Each boxed element is a separate heap object with a 12-byte header (compressed class pointers) plus padding.
Primitive arrays and open-addressing primitive maps hold values inline and allocate no per-entry objects.
JOL's GraphLayout measures the total count and bytes reachable from a collection.
The choice of collection follows from key type, density, ordering needs, size, and thread sharing.