Memory models

An int[] stores its values back to back after a small header, so int[n] costs 16 + 4n bytes rounded up to a multiple of 8 (an int[10] is 56 bytes and an int[100] is 416 on a 64-bit HotSpot JVM with compressed references). Elements that are neighbours in the index are neighbours in memory, so the CPU's cache loads several per cache line and its prefetcher predicts the next ones.

This is why scanning an array is fast even though it is “just O(n)” like a list scan. The animation compares reading a matrix row by row (memory order) with column by column (jumping across memory).

1int sumRowMajor(int[][] m) {                  // inner loop walks along a row
2    int sum = 0;
3    for (int r = 0; r < m.length; r++)
4        for (int c = 0; c < m[0].length; c++) sum += m[r][c];
5    return sum;
6}
7int sumColumnMajor(int[][] m) {               // inner loop jumps down a column
8    int sum = 0;
9    for (int c = 0; c < m[0].length; c++)
10        for (int r = 0; r < m.length; r++) sum += m[r][c];
11    return sum;
12}

Every object carries a header (12 bytes with compressed references) and is padded to a multiple of 8 bytes. A LinkedList node holds an item reference and two links, which makes it 24 bytes, and the Integer it points to is another 16 bytes. One element therefore costs 40 bytes plus the 4-byte reference that points at the node, against 4 bytes in an int[]: about ten times more.

Worse, nodes are allocated at different times and may sit far apart, so traversing a linked list means chasing pointers, and each hop can be a cache miss. A singly linked node you write yourself, with a primitive int field and one link, measures 24 bytes as well: it saves the 16-byte Integer but is still scattered in memory.

A HashMap entry is a node with the cached hash, the key and value references and the next link: 32 bytes. Add 16 bytes for each boxed Integer key and value, and 4 bytes for its slot in the table (which is kept at most 75% full, so about 8 bytes per entry on average). Measured on a map of one million Integer to Integer entries (keys above the small-value cache) the total was 72,388,672 bytes in a table of 2,097,152 slots: roughly 72 bytes per entry.

The same data in two int[] arrays would be 8 MB. When keys are small and dense, an array indexed by the key replaces the map completely.

A TreeMap entry stores key, value, left, right and parent references plus a colour flag: 40 bytes per entry on the measured JVM, plus the boxed key and value. Each lookup follows O(log n) pointers, each of them a potential cache miss, which is why a TreeMap is often several times slower than a HashMap for pure lookups even though both are “fast”.

What a tree buys is order: sorted iteration, floor and ceiling, ranges. If you do not need order, the hash table is smaller and faster; if you do, an array that is sorted once and searched with binary search is smaller still, as long as it rarely changes.

Java's collectors move live objects and compact free space, so the classic C-style fragmentation, where free memory exists but not in one piece, is mostly not a problem for small objects. The practical effect is *locality*: objects allocated together tend to be close, but a structure built up over time (a linked list, a tree, a map) ends up scattered, and each pointer hop may touch a new cache line.

Large arrays are the exception: a collector may need one contiguous region for a very large array and can fail or work harder when none is free. The remedies are to reuse big arrays, to allocate them early and to avoid many short-lived big buffers. A compact array of primitives is the opposite of a fragmented structure.

The garbage collector's work grows with the number of objects it must trace and with how fast you create garbage. A List<Integer> of a million values is a million-and-one objects, 20 MB measured (20,000,016 bytes for an Integer[] and its Integer objects), where an int[] of the same values is one object of 4 MB (4,000,016 bytes). Every boxed value, every node and every temporary Entry is something to allocate, trace and eventually reclaim.

Practical consequences: prefer primitive arrays in tight loops, avoid boxing in hot code (int instead of Integer keys where possible), reuse buffers and presize collections so they do not resize and discard their old arrays, and keep short-lived objects short-lived, because young-generation collection is cheap for objects that die quickly.