Java Collections Framework — Lists, Sets, Maps, and Their Implementations

Two roots, and why Collection has no get

The first thing to fix is the shape. Iterable is the top of one tree: it declares iterator() and nothing else, and implementing it is the entire qualification for appearing on the right-hand side of an enhanced for loop. Collection extends it and adds the operations that make sense for any bag of elements -- add, remove, contains, size, stream. List, Set and Queue extend Collection. Map does not. It is a separate root with no supertype, which is why it has no add, no iterator(), and why you reach its contents through the three view collections keySet(), values() and entrySet().

The question people ask next is why Collection has no get(int). Reflect over the interface and you find no method whose name even begins with get. The reason is that an index is not a universal concept: a HashSet has no third element, and a PriorityQueue's third slot is a heap position, not a rank. Positional access is a promise only List can keep, so it lives on List. Each sub-interface adds exactly the guarantee its name implies and nothing more -- List adds position, Set adds uniqueness, Queue adds a defined removal order. Note what Set does not add: it says nothing about being unordered. LinkedHashSet and TreeSet are perfectly ordered sets.

The practical consequence is the oldest style rule in Java, and it is a consequence rather than a preference: declare the interface, construct the implementation. A field typed ArrayList has frozen a cost model into your API; a field typed List has frozen only a contract.

Map<String, List<Integer>> index = new HashMap<>();
index.computeIfAbsent("a", k -> new ArrayList<>()).add(1);
// the views are live, not copies:
index.keySet().remove("a");   // removes the entry from the map itself

ArrayList against LinkedList, and why LinkedList is almost always wrong

The textbook comparison says ArrayList is O(1) for indexed access and O(n) for insertion in the middle, while LinkedList is O(n) for indexed access and O(1) for insertion. Both halves are true and the conclusion people draw from them is usually wrong, because the constants differ by more than the exponents do.

An ArrayList is one contiguous Object[]. Walking it is a linear scan over adjacent memory: the hardware prefetcher predicts it perfectly and each cache line delivers many elements. A LinkedList is one heap object per element, each holding the payload reference plus next and prev. Under compressed oops that is a 12-byte header plus three 4-byte references, so roughly 24 bytes per element against 4 bytes per slot in an ArrayList -- and those nodes are scattered wherever the allocator put them, so every step is a potential cache miss. Insertion in the middle is only O(1) once you hold the node; reaching it costs the O(n) walk you were trying to avoid.

The marker interface tells you what the JDK itself thinks. ArrayList implements RandomAccess and LinkedList does not, and library code branches on it -- Collections.binarySearch and friends switch between an indexed loop and an iterator loop depending on that test.

System.out.println(new ArrayList<>()  instanceof RandomAccess);   // true
System.out.println(new LinkedList<>() instanceof RandomAccess);   // false

The honest rule: default to ArrayList. Reach for a linked structure when you need a deque, and then reach for ArrayDeque, not LinkedList -- it is array-backed and beats LinkedList at both ends. LinkedList's remaining niche is holding a ListIterator across many splice operations, which is a real but rare shape.

One more ArrayList trap, and it is an overload-resolution accident rather than a performance one. List declares both remove(int) and remove(Object), so on a List<Integer> the two mean completely different things and the compiler picks the primitive overload without comment.

List<Integer> l = new ArrayList<>(List.of(10, 20, 30));
l.remove(1);                    // removes INDEX 1  -> [10, 30]
l.remove(Integer.valueOf(30));  // removes the VALUE -> [10]

Inside HashMap: bins, resizing, and treeified bins

HashMap is an array of bins. A key's hashCode() is spread (the high bits are XORed down into the low bits, because the bin index is a mask of the low bits and a table of 16 would otherwise ignore everything above bit 3), the low bits select a bin, and the bin holds whatever collided there. Lookup is therefore O(1) on average and O(bin length) in the worst case, and the whole design is a bet on bins staying short.

Two mechanisms keep that bet honest in the OpenJDK implementation, and it is worth being precise that these are implementation details of a particular JDK rather than language guarantees. First, resizing: when the entry count exceeds capacity times the load factor -- 0.75 by default -- the table doubles and every entry is redistributed. Second, treeification: when a single bin's chain grows past a threshold (8 in current OpenJDK), that bin converts from a linked list to a red-black tree, bounding its worst case at O(log n) instead of O(n). The clause most summaries omit is that treeification only happens if the table is already reasonably large, 64 bins in OpenJDK; below that a long chain is treated as evidence the table is too small, so the map resizes instead of treeifying. Treeified bins order by the keys' natural ordering when they are Comparable, and fall back to a tie-break on class name and identity hash when they are not.

Sizing matters more than people expect, and the constructor argument is the classic trap: new HashMap<>(1000) asks for a table of 1000, which with a 0.75 load factor starts resizing at 750 entries. Since JDK 19 there is a factory that takes the number you actually have in mind.

Map<String, String> a = new HashMap<>(1000);            // 1000 = table size
Map<String, String> b = HashMap.newHashMap(1000);      // 1000 = expected entries
// b will hold 1000 mappings without a single resize

Collisions are not hypothetical: "Aa".hashCode() and "BB".hashCode() are both 2112, and strings that collide can be generated at will. Treeification exists precisely so that adversarial key sets degrade to logarithmic rather than linear behaviour.

The equals and hashCode contract, and the mutable-key trap

Every hash-based collection is built on one rule: equal objects must have equal hash codes. The converse is not required -- unequal objects may share a hash code, which is just a collision. Break the rule in the required direction and the collection does not throw; it quietly loses things, because get looks in the bin the hash selects and the entry is sitting in a different bin.

The contract has a second clause that is easier to violate by accident: the fields you hash on must not change while the object is in the collection. Nothing enforces this, and the failure mode is spectacular -- an object that the set both contains and cannot find.

List<String> key = new ArrayList<>(List.of("a"));
Set<List<String>> set = new HashSet<>();
set.add(key);
key.add("b");                          // mutate a field that feeds hashCode

set.contains(key);                    // false
set.size();                           // 1
set.iterator().next().equals(key);    // true -- it is right there

The element is present, iterable and equal to the key you are holding, and the set still says no. Its hash was computed at insertion time and the bin index was decided then; the lookup now hashes to a different bin. The entry is unreachable by lookup and unremovable by remove until you mutate it back to its original state.

The fix is to make keys immutable. This is one of the strongest arguments for records as map keys: the components are final, and the compiler-generated equals and hashCode are derived from exactly those components, so the two-clause contract holds by construction and there is no hand-written accessor to drift out of sync.

record CacheKey(String tenant, int version) {}
Map<CacheKey, String> cache = new HashMap<>();
cache.put(new CacheKey("acme", 1), "v");
cache.get(new CacheKey("acme", 1));      // "v" -- structural lookup, no identity

Equality also crosses implementations in a way that surprises people. The List contract defines equals and hashCode structurally, so an ArrayList, a LinkedList and a List.of(...) holding the same elements are all equal to each other and share a hash code. A List is never equal to a Set, no matter what is in either.

Ordered and sorted maps: LinkedHashMap, TreeMap, NavigableMap

LinkedHashMap is a HashMap with a doubly-linked list threaded through its entries. Lookup cost is unchanged; you pay two extra references per entry and get a deterministic iteration order in return. Its third constructor argument is the feature most people never find: pass true for access order and every get moves the entry to the end of the list. Override removeEldestEntry and you have a bounded LRU cache in four lines, using only java.util.

Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<String, Integer> e) {
        return size() > 3;
    }
};
lru.put("a", 1); lru.put("b", 2); lru.put("c", 3);
lru.get("a");                  // "a" is now the most recently used
lru.put("d", 4);               // evicts "b", the eldest
System.out.println(lru.keySet());   // [c, a, d]

That cache is not thread-safe and has no expiry, so for anything shared or time-bounded reach for a real cache library. But for a per-request memo table it is exactly right and costs no dependency.

TreeMap is a red-black tree: O(log n) for everything, ordered by the keys' natural ordering or by a supplied Comparator. Sorted iteration is free, and the reason to choose it over sorting a HashMap's keys on demand is NavigableMap -- the range and neighbour queries that a hash table simply cannot answer.

NavigableMap<Integer, String> m = new TreeMap<>(Map.of(10, "a", 20, "b", 30, "c"));
m.floorKey(25);          // 20  -- greatest key <= 25
m.ceilingKey(25);        // 30  -- least key >= 25
m.headMap(20, true);     // {10=a, 20=b}  -- a live view, not a copy
m.descendingKeySet();    // [30, 20, 10]

Those sub-map results are views over the parent: writes go through, and they are the idiomatic way to express "the events in this time window" or "the price levels below the bid". TreeMap also has a sharp edge that follows from being comparison-based: even a read-only containsKey has to compare, so passing an argument of the wrong type throws ClassCastException rather than returning false the way HashMap does.

Deques, stacks and priority queues

Stack should not appear in new code, and the usual justification -- that it is an old synchronized class -- undersells the problem. Stack extends Vector, so it inherits the whole List API including get(int) and add(int, E), which have no business on a stack. Worse, it inherits Vector's iteration order, which is bottom-up: iterating a Stack hands you elements in the opposite order to popping them.

Deque<String> d = new ArrayDeque<>();
d.push("a"); d.push("b"); d.push("c");
System.out.println(d);   // [c, b, a]  -- iteration matches pop order

Stack<String> s = new Stack<>();
s.push("a"); s.push("b"); s.push("c");
System.out.println(s);   // [a, b, c]  -- iteration is the reverse of pop order
System.out.println(s.peek());   // c

Two collections whose toString disagree about the order of the same three pushes is exactly the kind of thing that turns a logging statement into a misdiagnosis. ArrayDeque is the replacement for both roles: a circular array with head and tail indices, O(1) amortised at both ends, no per-element node objects. Use it as a stack via push/pop, or as a FIFO queue via add/poll.

PriorityQueue is a binary heap, and its contract is narrower than the name suggests: it promises only that peek and poll return the smallest element by the comparator. It promises nothing about iteration, and its toString shows raw heap order, which reads as a bug the first time you see it.

Queue<Integer> q = new PriorityQueue<>(List.of(5, 1, 4, 2, 3));
System.out.println(q);         // [1, 2, 4, 5, 3]  -- heap layout, not sorted order
System.out.println(q.poll());  // 1
System.out.println(q.poll());  // 2  -- polling is the only ordered traversal

If the elements are enum constants, EnumSet and EnumMap beat everything else by a wide margin: EnumSet is a bit vector over the ordinals (a single long for enums up to 64 constants) and EnumMap is a plain array indexed by ordinal, so both are ordered by declaration order with no hashing at all.

Comparable, Comparator, and the ordering that throws

Sorted collections do not use equals. TreeSet and TreeMap decide identity purely by whether the comparison returns zero, which means a comparator that ignores case makes two differently-cased strings the same element.

Set<String> s = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
s.add("Hello");
s.add("HELLO");
s.size();      // 1

// same divergence with BigDecimal, whose compareTo ignores scale:
var a = new BigDecimal("1.0");
var b = new BigDecimal("1.00");
new HashSet<>(List.of(a, b)).size();   // 2 -- equals() sees different scales
new TreeSet<>(List.of(a, b)).size();   // 1 -- compareTo() says equal

Neither answer is a bug; they are two different definitions of sameness, and the Comparable javadoc explicitly notes that an ordering inconsistent with equals makes sorted collections behave strangely. Know which one your collection uses.

A comparator must also be a genuine total order: antisymmetric, transitive, and transitive in its equalities. Violate that and one of two things happens, and the quiet one is worse. The loud failure comes from the merge sort behind List.sort, which detects certain inconsistencies while merging runs and aborts.

// a comparator that is simply random -- 1024 elements is enough for the merge
// sort to notice while merging runs
list.sort((x, y) -> rnd.nextInt(3) - 1);
// java.lang.IllegalArgumentException: Comparison method violates its general contract!

That exception is not the sorter being fussy: it means the merge read past the end of a run because the data contradicted the ordering it had been promised. The quiet failure is the subtraction idiom, which is non-transitive as soon as the values are far enough apart to overflow an int. No exception, just wrong output.

Comparator<Integer> bad = (x, y) -> x - y;
bad.compare(Integer.MIN_VALUE + 1, Integer.MAX_VALUE);   //  2  (positive!)
Integer.compare(Integer.MIN_VALUE + 1, Integer.MAX_VALUE); // -1

// correct, and composable:
list.sort(Comparator.comparingInt(Person::age).thenComparing(Person::name));

Build comparators from the factories -- Comparator.comparing, thenComparing, reversed, nullsFirst -- rather than by hand. They delegate to Integer.compare and friends, so the overflow bug is impossible; see lambda expressions for how the method-reference forms are wired up.

Fail-fast, weakly consistent, and snapshot iterators

Structurally modifying a collection while iterating it is undefined, and the java.util implementations try to catch it. Each keeps a modification counter; the iterator records it at creation and checks it on every step, throwing ConcurrentModificationException when they diverge. The javadoc is careful to call this best-effort, and here is the case that proves it.

List<String> l = new ArrayList<>(List.of("a", "b", "c", "d"));
for (String s : l) if (s.equals("c")) l.remove(s);   // second-to-last
// no exception. loop just ends. l == [a, b, d]

for (String s : l) if (s.equals("a")) l.remove(s);   // ConcurrentModificationException
for (String s : l) if (s.equals("d")) l.remove(s);   // ConcurrentModificationException

Remove the second-to-last element and the loop exits silently having never visited the last one. The check lives in next(), but hasNext() is just cursor != size -- and removing one element makes the cursor equal the freshly-decremented size, so the loop believes it finished. The same trap applies to a subList view, which throws ConcurrentModificationException on any use after the backing list is structurally changed, and to computeIfAbsent whose mapping function modifies the same HashMap.

The supported ways to remove during traversal are Iterator.remove(), which updates the counter it is checking against, and removeIf, which is clearer and usually faster.

l.removeIf(s -> s.equals("b"));                       // preferred
for (var it = l.iterator(); it.hasNext(); )
    if (it.next().equals("b")) it.remove();            // equivalent, more verbose
map.replaceAll((k, v) -> v + 1);                      // in-place value update, no CME
for (var e : map.entrySet()) e.setValue(e.getValue() + 1);  // also fine -- writes through

The concurrent collections make different promises, and choosing between them is mostly choosing an iterator semantics. ConcurrentHashMap's iterators are weakly consistent: never throw, reflect the map at some point during traversal, and may or may not see concurrent updates -- see ConcurrentHashMap for its internals and its atomic merge/compute methods. CopyOnWriteArrayList gives a true snapshot iterator by copying the backing array on every write -- correct and immune to interference, but O(n) per write, so it fits listener lists and other read-dominated sets, not working data. ConcurrentSkipListMap is the concurrent answer when you also need ordering. Collections.synchronizedMap is the one to avoid: it serialises every operation behind a single lock and still requires you to hold that lock manually around iteration.

Arrays.asList, List.of, and three flavours of unmodifiable

Three constructs are routinely described as "unmodifiable" and all three behave differently. Knowing which one you are holding decides whether a bug shows up as an exception at the call site or as a mutation somewhere else entirely.

Arrays.asList(array) is a fixed-size view over the array. set works and writes through to the original array; anything that changes the size throws.

String[] arr = {"a", "b"};
List<String> view = Arrays.asList(arr);
view.set(0, "z");     // allowed -- and arr[0] is now "z"
view.add("c");        // UnsupportedOperationException

Collections.unmodifiableList(list) is a read-only wrapper around a live list. Every mutator on the wrapper throws, including iterator().remove(). What it does not do is freeze anything: the caller who still holds the backing list can change it, and the change appears through the wrapper.

List<String> base = new ArrayList<>(List.of("a"));
List<String> ro = Collections.unmodifiableList(base);
base.add("b");
System.out.println(ro);   // [a, b]  -- the "unmodifiable" list changed

List.of(...) and List.copyOf(...) are the real thing: a separate immutable object with no writable back door, rejecting nulls and duplicate keys outright. List.copyOf returns its argument unchanged when it is already immutable, so defensive copying is free in the common case. The caveat that matters is that immutability is shallow -- an immutable list of mutable objects is still a mutable data structure.

Set.of("a", "a");             // IllegalArgumentException: duplicate element: a
Map.of("a", 1, "a", 2);        // IllegalArgumentException: duplicate key: a
System.out.println(List.copyOf(x) == x);   // true when x is already immutable

The same split runs through the stream terminal operations, which is where most collections are born and die. Collectors.toList() makes no promise about mutability and in practice hands back a mutable ArrayList; Stream.toList() (JDK 16) returns an unmodifiable list that does permit nulls; Collectors.toUnmodifiableList() returns an unmodifiable list that rejects them. Going the other way, collection.stream() is the entry point and the collection's own iteration order is the stream's encounter order.

Stream.of("a", null).toList();                                 // [a, null]
Stream.of("a", null).collect(Collectors.toList());             // [a, null]
Stream.of("a", null).collect(Collectors.toUnmodifiableList()); // NullPointerException
Stream.of("a").toList().add("b");                             // UnsupportedOperationException

Null hostility, implementation by implementation

There is no framework-wide rule about nulls. Each implementation decided separately, and the decisions are not obviously consistent, so the only reliable approach is to know the table. All of the following was executed on OpenJDK 23.

TreeMap's behaviour surprises people because it throws on an empty map too. Since JDK 7 put runs compare(key, key) up front specifically to type-check and null-check the key, rather than letting the first key in slip through unvalidated. Give it a Comparator.nullsFirst(...) and nulls become legal.

The immutable collections are null-hostile on queries as well, which catches people who assumed a lookup could never throw.

List.of("a").contains(null);      // NullPointerException, not false
List.of("a").indexOf(null);       // NullPointerException
Map.of("a", 1).containsKey(null); // NullPointerException
new ArrayList<>(List.of("a")).contains(null);   // false -- no throw

And a null value in a HashMap is genuinely ambiguous, which is why ConcurrentHashMap banned them: map.get(k) == null cannot distinguish "absent" from "present and null". Even getOrDefault does not rescue you -- it returns the stored null, not the default, because the key is present. Use containsKey, or do not store nulls.

Iteration order: which guarantees are real

HashMap and HashSet document that they make no guarantee about iteration order and, specifically, no guarantee that it stays constant over time. Both halves get ignored, because in practice a small HashSet of strings iterates in a stable, plausible-looking order run after run -- long enough for a test to be written against it.

The order is a function of the hash values and the table size, so it holds until the table resizes, at which point entries redistribute and the order changes completely.

Map<Integer, Integer> m = new HashMap<>();
for (int i = 1; i <= 12; i++) m.put(i * 17, i);
System.out.println(m.keySet());   // [17, 34, 51, 68, 85, 102, ...]  -- looks sorted!
for (int i = 13; i <= 20; i++) m.put(i * 17, i);
System.out.println(m.keySet());   // [289, 34, 323, 68, 102, 136, ...]  -- order gone

The immutable collections go further and remove the temptation entirely. Set.of and Map.of mix a per-JVM random salt into their probe sequence, so the same five-element set iterates in a different order in different runs of the same program on the same machine. Three consecutive runs of one program:

System.out.println(Set.of("a", "b", "c", "d", "e"));
// run 1: [e, d, c, b, a]
// run 2: [c, d, e, a, b]
// run 3: [a, b, c, d, e]

System.out.println(new HashSet<>(List.of("a", "b", "c", "d", "e")));
// [a, b, c, d, e] on every run -- stable, but still not guaranteed

This is a deliberate anti-feature: the library randomises so that code cannot come to depend on an order it was never promised. If you find an assertion that breaks under Set.of but passes under HashSet, the assertion is the bug.

The orders you may rely on are the ones a type declares: List is positional, LinkedHashMap and LinkedHashSet are insertion order (or access order when so configured), TreeMap and TreeSet are comparator order, EnumSet and EnumMap are declaration order, and ArrayDeque is queue order. Since JDK 21 those guarantees have a name: SequencedCollection, SequencedSet and SequencedMap give the ordered types a common vocabulary -- getFirst, getLast, reversed -- so "reverse a LinkedHashMap" is finally one call instead of a manual rebuild.

List<String> l = new ArrayList<>(List.of("a", "b", "c"));
l.getFirst();    // "a"   (NoSuchElementException when empty)
l.reversed();    // [c, b, a]  -- a view, not a copy

LinkedHashMap<String, Integer> m = new LinkedHashMap<>();
m.put("a", 1); m.put("b", 2);
m.firstEntry();  // a=1
m.reversed();    // {b=2, a=1}