Lesson 1 of 5
The Collections Framework, Chosen Well
"Nothing is more dangerous than an idea, when it is the only one you have." — Émile Chartier (Alain), Propos sur la religion (1938)
Most Java programs reach for ArrayList and HashMap and stop there. That is not a bad instinct — between them they are correct for the large majority of cases, and a program built from them will work. But "will work" is doing a lot of hiding, and the gap between a collection that works and the one that fits shows up as a method that is quadratic when it could be linear, an iteration order that changes between runs, or a ConcurrentModificationException in production that nobody can reproduce.
This chapter is about choosing deliberately. Not memorising a complexity table — those are in the Javadoc and you will forget them — but knowing what question each collection answers, so the choice falls out of what your code actually does.
It is also, unavoidably, about the traps. The framework was designed in 1998 and has accumulated three different meanings of "unmodifiable", a null policy that differs per implementation, and a safety check that is explicitly documented as unreliable. All three are measured here.
You need a collection. Before you type ArrayList, what are the three questions whose answers determine the right one — and which of them does your code actually depend on?
Choose by what the code does to it
Start with the decision itself. The interfaces describe capabilities, and the implementations differ in what those capabilities cost. Counting the work is more honest than timing it, and portable besides.
Click Run to compile and execute the code.
Those counts are the whole argument. Inserting at the front of a 100,000-element ArrayList moves 100,000 elements; the LinkedList relinks two nodes. Reading the middle is the mirror image: one array index against 50,000 pointer hops.
What the table does not show, and what decides it in practice, is that ArrayList's loser case is a fast memory copy over contiguous data while LinkedList's is 50,000 cache-missing pointer chases through objects scattered across the heap. That is why the practical advice has converged on use ArrayList unless you have a specific reason, and why LinkedList is one of the least justified classes in the library. Its genuine niche — constant-time insertion at a position you already hold an iterator for — is real and rare, and for queue-like use ArrayDeque is better at both ends.
The useful habit is to pick the interface by what your code needs and the implementation by how it will be used. Declare List, Set, Map, Deque; instantiate ArrayList, HashSet, HashMap, ArrayDeque. Then changing the implementation is one line and nothing else has to know.
A filing cabinet, a stack of trays and a card index all store documents, and asking which is best is a question with no answer until you say what you will do with them. If you mostly add to the top and take from the top, the trays win and the index is wasted effort. If you need to find one document by name among ten thousand, the index wins and the trays are a disaster. The documents are identical in all three. The right container is a statement about your workflow, not about your data — which is why "what will this code do to the collection?" is a better first question than "what am I storing?".
Growth is not free, and it is not visible
One cost that never appears in a complexity table: these collections start small and grow by reallocating.
An ArrayList holds an array. When it fills, it allocates a larger one — the current implementation grows by about half again — copies everything across, and abandons the old one. Each individual growth is O(n), but because the capacity grows geometrically the cost amortises to roughly constant per element, which is why add is documented as amortised constant rather than constant.
HashMap does the same with a table of buckets. It starts at 16, and when the number of entries exceeds the load factor — 0.75 by default, so 12 entries — it doubles the table and redistributes every entry into it. The load factor is a deliberate trade: lower means more empty space and fewer collisions, higher means a fuller table and longer bucket chains. Three-quarters is the compromise the library settled on, and it is almost never worth changing.
What makes this worth knowing is that the cost is invisible at the call site. A loop that adds a million entries to a default-sized HashMap performs around sixteen full rehashes along the way, each one touching every entry present at the time. None of that appears in the code, and none of it is wrong — it is simply work you can avoid when you already know the answer:
new ArrayList<>(expectedSize)
new HashMap<>(expectedSize * 4 / 3 + 1)
The awkward arithmetic on the map is because the constructor argument is capacity, not expected entries, and the resize happens at capacity times load factor. Passing the count you expect gives you a table that resizes once anyway, which is a common and silent mistake. Java 19 added HashMap.newHashMap(int numMappings) to do the arithmetic for you, which is a small admission that nobody was getting it right.
Pre-sizing matters when the size is known and large — reading a file of records, copying a collection, building a lookup table at startup. It matters very little for the small collections most code creates, and premature pre-sizing makes code noisier for no gain. The honest rule is to pre-size where the count is already in your hand, and otherwise leave it alone.
There is one more consequence worth holding on to. Because growth copies, a collection that has grown large and then shrunk does not give the memory back: an ArrayList that held a million elements and now holds ten still owns a million-element array. trimToSize() exists for that, and the situation is rare enough that most people have never called it — but a long-lived list used as a buffer is exactly where it bites, and it looks like a leak.
Three different things called immutable
The framework offers several ways to produce a collection that cannot be modified, and they differ in ways that matter.
Click Run to compile and execute the code.
Three constructs, three different promises.
List.of(...) is immutable. Nothing can change it, it rejects nulls at construction, and it is the right default for a constant. The null rejection is deliberate: these collections were added in Java 9 with a clean slate, and the designers took the chance to exclude a value that had caused decades of ambiguity.
Arrays.asList(...) is fixed-size, not immutable. add throws, set succeeds — and worse, it is a view over the array you passed, so changing the array changes the list and vice versa. It is a bridge between arrays and collections, not an immutable factory, and it is routinely misused as one.
Collections.unmodifiableList(...) is a read-only view of something else. You cannot modify it through the view, and anyone holding the backing list can modify what you see. If the point is to hand out something that cannot change, wrapping is not enough — you must copy first, or the "unmodifiable" collection will change under its holder.
The null disagreement is worth memorising because it crosses implementations rather than interfaces. HashMap permits one null key and any number of null values. TreeMap rejects null keys, because it must compare them. Map.of and List.of reject nulls entirely. Arrays.asList accepts them. There is no rule to derive here; it is history, and the only defence is knowing it.
The Collections Framework arrived in Java 1.2 in 1998, designed largely by Josh Bloch, replacing Vector, Hashtable and Enumeration — all of which were synchronised whether you wanted it or not, which is why they survive only in old code and in interview questions. The framework's great idea was separating interface from implementation, so that a method could accept any List and a caller could change its mind about which one. Its visible compromises are all from that era: UnsupportedOperationException exists because the designers chose fewer interfaces with optional operations over an interface for every combination of capabilities, so an unmodifiable list is still a List that throws for half its methods. Java 9's List.of family is the correction, twenty years later, with immutability by construction rather than by refusal.
Order you can rely on, and order you cannot
The second decision is about iteration, and the default implementation makes no promise at all.
Click Run to compile and execute the code.
HashMap iteration order is a function of hash codes and table size. It is deterministic for a given program and a given JVM, which is exactly what makes it dangerous: a test passes consistently, and the order changes when the map resizes, when a key is added, or when someone upgrades Java. If your output depends on order, say so in the type — LinkedHashMap for insertion order, TreeMap for sorted order.
TreeMap buys you the navigation methods, and they are the reason to accept O(log n). ceilingKey, floorKey, headMap, tailMap, subMap answer range questions a hash map simply cannot, and "find the nearest entry at or above this value" is a common enough need — time buckets, price ladders, version ranges — to be worth knowing.
LinkedHashMap has a third mode most people never meet. Constructed with accessOrder = true and with removeEldestEntry overridden, it is a complete LRU cache, and it is the one in the standard library that everybody rewrites badly.
A safety check that is explicitly best-effort
Now the trap that produces irreproducible bugs, and it is worse than its reputation.
Click Run to compile and execute the code.
Read that first table again, because it is the part people do not know. ConcurrentModificationException is thrown by next(), which compares a modification counter against the one it recorded. Remove the second-to-last element and the list's size drops to equal the iterator's cursor, so hasNext() returns false, the loop ends, and next() is never called again — no check, no exception, and one element silently never visited.
On a two-element list that means removing the first element skips the second entirely and reports success. The bug is not that an exception was thrown; it is that one was not.
The Javadoc is unusually frank about this: the check is best-effort and "fail-fast behaviour cannot be guaranteed", so programs must not depend on it for correctness. It is a debugging aid, not a guard.
The correct tools are Iterator.remove(), which updates the iterator's expectations as well as the list, and removeIf, which does one pass, reads as its own documentation, and is what you should reach for by default.
While probing this chapter I wrote a small helper that caught Throwable and printed getClass().getSimpleName() plus getMessage() — the kind of thing you write without thinking. It worked for UnsupportedOperationException and then blew up on List.of(null) with UnsatisfiedLinkError: Java_java_lang_NullPointerException_getExtendedNPEMessage. Calling getMessage() on a NullPointerException the JDK raised internally throws here, because the JVM tries to compute a helpful message through a native method this runtime does not implement. It is safe for an NPE you constructed yourself and returns null for a plain dereference, so the helper worked for every exception type except one — and failed with an Error rather than an exception, so a catch (Exception e) around it would not have saved me. The blocks in this chapter print class names only.
Views are not copies
The last recurring surprise: several methods that look like they return a new collection return a window onto the old one.
Click Run to compile and execute the code.
subList returns a window. Setting through it writes to the original; clearing it deletes that range from the original — which is the idiomatic way to remove a range, and startling the first time you meet it. And because the view holds the parent's modification count, any structural change to the parent makes the view throw on its next use.
keySet(), values() and entrySet() are the same. Removing from a key set removes the entry from the map. That is often exactly what you want — map.values().removeIf(v -> v == null) is a neat way to purge entries — and a surprise if you expected a copy.
The rule is simple once you expect it: if you need a snapshot, take one. new ArrayList<>(source), new HashMap<>(source), or List.copyOf and Map.copyOf when you want it immutable as well. The copy constructors are cheap and the ambiguity is not.
It is worth asking why the library works this way, because "views are confusing" is not the whole story. A view costs nothing to create and stays in step with its source, which is exactly right for keySet() — a map with a million entries should not have to materialise a million-element set just so you can iterate the keys. The design is sound; the problem is that nothing in the name or the return type distinguishes a window from a copy, so the only way to know is to know. That is a documentation failure rather than a design one, and it is why this list of which methods return views is worth committing to memory rather than deriving each time.
These produce recognisable production failures. A service returns an "unmodifiable" list to a caller, the backing list is mutated later by the owning class, and the caller's data changes under it. A test depends on HashMap ordering, passes for a year, and fails after a JDK upgrade. A nightly job removes expired entries in a for-each loop and works fine until the day exactly two entries expire. A cache built on HashMap grows without bound because nobody knew LinkedHashMap had removeEldestEntry. And the quiet one: a method takes ArrayList rather than List, and three years later nobody can change the implementation without touching forty call sites.
Common Mistakes
Choosing
LinkedListfor "lots of insertions". Insertion is only cheap at a position you already hold an iterator to; reaching an index costs a walk, and the pointer chasing loses toArrayList's memory copy. For queue behaviour useArrayDeque.Treating
Arrays.asListas immutable. It is fixed-size:addthrows,setsucceeds, and it writes through to the array you passed.Handing out
Collections.unmodifiableListwithout copying. The view cannot be modified; the thing behind it can, and the holder will see the changes.Depending on
HashMapiteration order. It is unspecified, stable enough to pass tests, and free to change on resize or on a JDK upgrade. UseLinkedHashMaporTreeMapwhen order matters.Assuming every collection accepts null.
HashMappermits a null key,TreeMapdoes not, and theList.of/Map.offamily rejects nulls entirely. It is history, not a rule you can derive.Relying on
ConcurrentModificationExceptionto catch mistakes. It is documented as best-effort and does not fire when the second-to-last element is removed, which silently skips an element instead.Removing inside a for-each. Use
Iterator.remove()or, better,removeIf, which is one pass and states its intent.Expecting
subList,keySetorvaluesto be copies. They are views: writes go through, and a structural change to the parent invalidates them.Declaring concrete types in signatures. A parameter of type
ArrayListforecloses every other implementation for all callers. Declare the interface.Reaching for
VectororHashtable. They synchronise every method, which is rarely the granularity you need and never free. UseArrayList/HashMap, orConcurrentHashMapwhen you genuinely share across threads.
Interview Corner
List, a Set and a Map?List when order matters and duplicates are allowed, and when you need to address elements by position. A Set when you care only about membership and want duplicates excluded automatically. A Map when each value is reached by a key rather than a position. The implementations then answer a second question: ArrayList and HashMap by default, LinkedHashMap or LinkedHashSet when you need insertion order preserved, and the tree versions when you need sorted order or range queries. I would declare the interface in the signature and the implementation only where the object is created.ConcurrentModificationException is thrown by next(), which compares a modification count — but if you remove the second-to-last element, the size drops to equal the iterator's cursor, hasNext() returns false, the loop exits, and next() never runs the check. So the last element is silently never visited. The job worked for months because that exact arrangement had not come up; last night exactly the wrong number of entries expired. The Javadoc says plainly that fail-fast is best-effort and must not be relied on for correctness. The fix is removeIf, or Iterator.remove() if the condition needs more than a predicate.Collections.unmodifiableList stops the caller but not you — it is a view, so your own later mutations are visible to everyone holding it, which is a subtle aliasing bug rather than an obvious one. Returning a defensive copy costs an allocation proportional to size and gives genuine isolation; List.copyOf makes it immutable as well and skips the copy when the source is already an immutable list. Returning a stream defers the cost and lets the caller choose, at the price of a one-shot result. My default is List.copyOf for small results, because the correctness is unconditional and the cost is visible. For large or hot results I would return a stream or document the view's lifetime explicitly, since the real failure mode is not performance but a caller holding something they believe is a snapshot.ArrayList versus LinkedList, HashMap versus TreeMap, and why you declare the interface.Hands-on
Model the rules you have just measured. Implement chooseFor, picking an implementation from a usage pattern; mutability, distinguishing the three kinds of unmodifiable; acceptsNull, applying the per-implementation null policy; failsFast, predicting when the modification check actually fires; and isView, separating windows from copies. A stub scores zero, so a passing run means the model is real rather than lucky.
Click Run to compile and execute the code.
Summary
- Choose the collection by what the code does to it, not by what it stores: positional access, end insertion, membership, keyed lookup, ordering.
- Declare the interface and instantiate the implementation, so a change of mind is one line rather than a refactor across every caller.
LinkedListis almost never right. Its advantage needs an iterator you already hold, andArrayDequebeats it for queue and stack use.List.ofis immutable,Arrays.asListis fixed-size, andCollections.unmodifiableListis a read-only view whose contents can still change beneath its holder.- Null policy varies by implementation —
HashMapallows a null key,TreeMapdoes not, theoffactories reject nulls — and it is history rather than a derivable rule. HashMapiteration order is unspecified, stable enough to pass tests and free to change on resize or upgrade. UseLinkedHashMaporTreeMapwhen order is part of the contract.TreeMap's navigation methods are whatO(log n)buys, andLinkedHashMapwithremoveEldestEntryis a complete LRU cache in six lines.ConcurrentModificationExceptionis best-effort and does not fire for the second-to-last element, which silently skips an item instead of failing.removeIfis the right default for conditional removal, withIterator.remove()where the condition needs more context.subList,keySet,valuesandentrySetare views, not copies. Writes go through, structural changes invalidate them, and a snapshot must be taken deliberately.
A collection answers what you have. The next chapter opens one of them up — HashMap from the inside, where the hashing questions that sound like folklore turn out to have a short mechanical answer, and where the choices Java made about collisions explain a denial-of-service attack and the fix that shipped in Java 8.
The detail from this chapter I expect to stay with me is that ConcurrentModificationException does not fire for the second-to-last element. Not because it is obscure, but because of what it implies about how we treat safety checks. Most engineers I know — I include myself — have used that exception as a guarantee: if I had made that mistake, I would have been told. The Javadoc has said for twenty-five years that this is wrong, in plain language, and almost nobody has read it, because the check works nearly always and nearly always is indistinguishable from always until the day it is not. There is a general pattern there about tools that are right 95% of the time. They do not teach you the 5%; they teach you to stop checking. The dangerous safety net is not the one that fails, it is the one that fails rarely enough that you stop looking down.
Q&A · 0
Enrol to ask questions and join the discussion.
No questions yet — be the first to ask.