Java Collections You Actually Need to Know
Most people overthink this. You do not need to memorize every class in java.util. You need to understand three things: what your data looks like, what operations you run on it, and what happens when the JVM tries to GC an object graph full of circular references. I once had a production service leak memory because someone used ConcurrentHashMap without realizing it holds strong references to values. The map itself was never null. The garbage collector had no reason to touch those entries. We watched RSS climb to 14 gigabytes over four days before the OOM killer stepped in. The fix was switching to a soft-reference wrapper around each value, but honestly the real fix was just not storing 200,000 active sessions in a single map. The map was doing what it was designed to do. The problem was the design around it.Java Data Structures Cheat Sheet for people who forgot
ArrayList — backed by a single array. Random access is O(1). Insertion at the beginning or middle is O(n) because everything shifts. It grows by 50% when full, which means occasional expensive resize operations. Good for read-heavy workloads where you iterate sequentially. Bad if you are inserting into the front of a list that starts at ten thousand elements. LinkedList — doubly linked nodes. Insertion and deletion are O(1) once you have the node reference. Random access is O(n). The constant factors are ugly. Every operation allocates a node object. In practice ArrayList usually beats LinkedList for most real workloads because of cache locality. The JVM loves sequential memory. It does not love pointer chasing. HashMap — the workhorse. O(1) average case for get and put. Worst case is O(n) when every key hashes to the same bucket, though Java 8+ switches to balanced trees at a threshold so you generally see O(log n) instead. The default load factor is 0.75. The default initial capacity is 16. If you know your map will hold roughly 100,000 entries, construct it with that capacity or a power of two above it. Otherwise you get unnecessary resizes. I initialized a map with no capacity hint in a tight loop once and watched the allocation rate spike. It was embarrassing but instructive.
HashSet — just a HashMap with dummy values. Same complexity characteristics. Use it when you care about membership testing, not ordering. TreeMap — Red-Black tree implementation. O(log n) for everything. Keys are sorted. Use it when you need range queries, navigable methods like ceilingKey or lowerKey, or when order matters. It is significantly slower than HashMap for simple lookups. Don't use it just because you want sorted output if you can sort a list after the fact instead. LinkedHashMap — HashMap with a linked list threading through entries. Maintains insertion order or access order depending on the constructor flag. Useful for LRU caches, though the built-in removeEldestEntry method is more of a hook than a full solution. The real LRU cache problem usually needs something like Caffeine.
PriorityQueue — binary heap. O(log n) add and remove. O(1) peek. No guaranteed iteration order. The iterator does not traverse in priority order. That surprised me once when I wrote a test assuming it would. It did not. Use it for scheduling problems, Dijkstra's algorithm, or merging sorted streams. ConcurrentHashMap — segmented locking under the hood in Java 7, bucket-level locking in Java 8+. Much higher throughput than Hashtable or synchronized wrappers. The iteration semantics are weakly consistent, not fail-fast. You may or may not see modifications made after the iterator is created. This matters more than people think. If you need a snapshot, copy to a new collection first. ArrayDeque — circular array backed. Faster than Stack or LinkedList-based Deque implementations. Use it as a stack or queue. The ArrayDeque internals avoid the extra node allocation that LinkedList requires. I replaced a LinkedList used as a stack in a parser and cut allocation overhead by roughly 40 percent on a JSON tokenizer. Not glamorous. The profiler made it obvious.
Get the Full Details
Pitfalls nobody warns you about
hashCode and equals must be consistent. If you put an object in a HashMap and then mutate a field that participates in hashCode, the map loses the entry. It is still there. You just cannot find it. I spent an afternoon debugging a "missing" entry before remembering this rule. The object had been mutated after insertion. Moving the mutation before insertion fixed it. Autoboxing creates hidden allocations. Every time you write int to a List
ArrayList.subList returns a view, not a copy. Modifying the sublist modifies the original list. Returning a sublist and then modifying the original list from another thread is a race condition waiting to happen. Copy it explicitly if you need isolation. Don't use Collections.synchronizedList for anything performance-critical. It wraps every method call in a synchronized block. The granularity is coarse. ConcurrentHashMap or CopyOnWriteArrayList are better choices depending on your read-write ratio. CopyOnWriteArrayList is only suitable for very small lists with predominantly read operations. Every write copies the entire array.
What I actually keep on my desk
A printed page with big-O notation for the common operations of each collection. Not the full API. Just the operation costs. Access, insert, delete, search. That is what you look up under pressure, not method signatures. I wrote one out myself because the ones online are either too dense or too simple. A proper Java Data Structures Cheat Sheet should show the trade-offs side by side so you can make a decision in thirty seconds during a code review. The trade-off matrix is straightforward. ArrayList: fast access, slow insert. LinkedList: fast insert at known position, slow access. HashMap: fast lookup, no order. TreeMap: slower lookup, sorted order. PriorityQueue: fast minimum extraction, no arbitrary access. ConcurrentHashMap: concurrent reads without locking, slightly higher per-operation cost than HashMap. ArrayDeque: fast stack and queue operations, no mid-list efficiency. Pick the structure that matches your access pattern. Not the one that sounds smart. HashMap is not always the right answer. Neither is Stream. Most bugs in this area come from choosing based on habit rather than measurement. Profile before you optimize. A simple timing harness with JMH takes twenty minutes to set up and saves hours of guesswork.
