Choosing a Collection: Complexity and Memory Footprint

Two tables and a decision procedure. This page is the reference you should be able to reconstruct from memory, plus the reasoning that makes it more than memorisation.

Time complexity#

Two rows repay a second look. HashMap iteration is O(n + capacity), not O(n): the iterator walks every table slot including the empty ones. A map that once held a million entries and now holds ten still costs a million slot reads per iteration, because the table never shrinks.

And CopyOnWriteArrayList has an O(n) add. It is not "a thread-safe ArrayList" — it is a read-optimised structure whose writes copy everything. Using it for a collection that is appended to in a loop turns an O(n) build into O(n²).

Memory, per element#

Assuming a 64-bit JVM with compressed oops (the default below a 32GB heap): object header 12 bytes, reference 4 bytes, everything padded to an 8-byte boundary.

int[] a                = new int[1_000_000];        //  ~4 MB
List<Integer> b        = new ArrayList<>(1_000_000);// ~20 MB (4 ref + 16 Integer)
Set<Integer> c         = new HashSet<>(...);        // ~64 MB
Map<Integer,Integer> d = new HashMap<>(...);        // ~80 MB

A factor of twenty between the first and the last, for the same information. On a container with a 512MB heap limit that difference decides whether the service runs.

Boxing#

List<Integer> list = new ArrayList<>();
list.add(42);                     // Integer.valueOf(42) — cached, no allocation
list.add(1_000_000);              // new Integer(1000000) — a heap allocation
int x = list.get(0);              // intValue() — a dereference, possibly a cache miss
 
// The classic puzzle:
Integer a = 127, b = 127;   a == b;   // true  — both from the Integer cache
Integer c = 128, d = 128;   c == d;   // false — two distinct objects

The Integer cache covers -128 to 127 by default (the upper bound is settable with -XX:AutoBoxCacheMax). Real data escapes it immediately, so every element becomes a separate 16-byte object that must be dereferenced to read a 4-byte value — the allocation is bad, and the cache miss on each read is usually worse.

Where numeric collections are large or hot, the options are: IntStream and the primitive streams; plain arrays; or a primitive-collection library — Eclipse Collections, fastutil, HPPC or Agrona. A fastutil IntArrayList of a million values costs 4MB against roughly 20MB for ArrayList<Integer>, and iterating it never dereferences anything.

Sizing#

new ArrayList<>(expectedSize);                    // exact — no resize at all
new HashMap<>((int) (expectedSize / 0.75f) + 1);  // account for the load factor
HashMap.newHashMap(expectedSize);                 // Java 19+ does the arithmetic
new StringBuilder(expectedLength);
new ArrayBlockingQueue<>(capacity);               // bounded on purpose

The HashMap line is the one people get wrong: new HashMap<>(1000) sets the capacity to 1024, and with a 0.75 load factor it resizes at 768 entries. Sizing for the expected count requires dividing by the load factor first.

Presizing matters most in two places: building a large collection in a loop, where it eliminates a logarithmic number of full copies; and any collection allocated per request, where the resize garbage multiplies by your request rate.

Where Big-O stops predicting#

An O(1) HashMap lookup involves computing a hash, masking, reading a table slot, following a reference to a Node (likely a cache miss), comparing the hash, and calling equals. An O(n) scan of a 20-element ArrayList is twenty sequential reads from one or two cache lines, with the branch predictor getting every iteration right.

Below roughly 50–100 elements the linear scan often wins. That is not a licence to use lists as maps, but it does explain why micro-optimising a small collection by "upgrading" it to a HashMap usually achieves nothing, and why the JDK itself uses linear search inside small EnumMaps and inside HashMap buckets before treeification.

The same reasoning explains ArrayList beating LinkedList at middle insertion, and ArrayDeque beating LinkedList everywhere — covered in ArrayList vs LinkedList.

The decision procedure#

Then apply three modifiers:

1. Shared between threads? ConcurrentHashMap, ConcurrentHashMap.newKeySet(), a bounded BlockingQueue, or CopyOnWriteArrayList if reads overwhelmingly dominate.
2. Keys are enums? EnumMap or EnumSet, always.
3. Millions of primitives? An array, a primitive stream, or a primitive-collection library.

What gets asked#

Interviewers usually ask this as a scenario: "you need to store X and do Y with it — what do you use?" Answer with the collection and the reason, and state the cost you are accepting. "TreeMap, because I need floorEntry for effective-dated lookups, and I am accepting O(log n) and about 64 bytes per entry to get it" is a complete answer.

The follow-up worth preparing is the memory one. Most candidates can recite Big-O; being able to say "roughly 48 bytes per HashMap entry, so a million entries is about 48MB before the keys and values" is much rarer, and it is exactly the reasoning that matters when a service is running in a container with a fixed memory limit.