Java Collections Framework — Lists, Maps & Sets Explained

The Java Collections Framework

Almost every Java program stores groups of objects, and the Collections Framework is how. Choosing the right collection — and understanding how HashMap works, why ConcurrentModificationException happens, and how equals/hashCode underpin it all — is a staple of Java interviews and of writing efficient code. This guide covers the interfaces, the implementations, and the trade-offs.

The hierarchy

The root is Iterable -> Collection, which branches into:

• List — ordered, indexed, allows duplicates (ArrayList, LinkedList).
• Set — no duplicates (HashSet, TreeSet, LinkedHashSet).
• Queue/Deque — processing order (ArrayDeque, PriorityQueue).

Map is part of the framework but not a Collection — it stores key->value pairs. Program to the interface (List, not ArrayList) so you can swap implementations freely.

List<String> list = new ArrayList<>();
Set<String>  set  = new HashSet<>();
Map<String, Integer> map = new HashMap<>();

Lists: ArrayList vs LinkedList

• ArrayList — a resizable array. O(1) random access; O(1) amortized append; O(n) middle insert/remove (shifting). Cache-friendly.
• LinkedList — a doubly-linked list. O(1) insert/remove at the ends; O(n) index access; more memory per element.

List<Integer> a = new ArrayList<>(1000); // pre-size to skip resizes
a.get(500); // O(1)

In practice ArrayList wins almost always — its cache locality beats LinkedList even for many insert/remove patterns. ArrayList grows by ~1.5× when full (an O(n) copy), giving amortized O(1) appends; pre-size it if you know the count. One trap: list.remove(int) removes by index, while list.remove(Object) removes by value — for a List<Integer>, box with Integer.valueOf(x) to remove a value.

How HashMap works

A HashMap is an array of buckets. To store a key it computes hashCode(), spreads the bits, and maps it to a bucket. Collisions chain in a linked list, which converts to a balanced tree once a bucket exceeds 8 entries (table ≥ 64), keeping worst-case lookups at O(log n).

Map<String, Integer> m = new HashMap<>();
m.put("a", 1);  // hash -> bucket -> store
m.get("a");     // hash -> bucket -> equals() scan -> 1

Lookups and inserts are O(1) average. The map has a capacity (buckets, default 16) and a load factor (default 0.75); when size > capacity × loadFactor it resizes (doubles) and rehashes — so pre-size a known-large map to avoid repeated O(n) resizes.

HashMap allows one null key and null values and isn't synchronized. Hashtable is the legacy fully-synchronized version; ConcurrentHashMap is the modern thread-safe choice with fine-grained locking and atomic methods (merge, computeIfAbsent).

Sets and Maps: ordering variants

The Set and Map families mirror each other:

• HashSet/HashMap — no order, O(1).
• LinkedHashSet/LinkedHashMap — insertion order (LinkedHashMap also supports access order, enabling LRU caches), O(1).
• TreeSet/TreeMap — sorted, O(log n), with navigation methods (floor, ceiling, subMap) for range and nearest-value queries.

new HashSet<>(List.of(3,1,2));       // order undefined
new LinkedHashSet<>(List.of(3,1,2)); // [3, 1, 2]
new TreeSet<>(List.of(3,1,2));       // [1, 2, 3]

Choose by need: speed -> Hash; remember order -> Linked; sorted/range -> Tree. For enum keys, the specialized EnumSet/EnumMap are far faster.

Why equals and hashCode matter

Hash-based collections locate elements by hash first, then equals. If two equal objects have different hash codes, they land in different buckets and the collection can't recognize them — duplicates in a Set, failed lookups in a Map.

class Key {
  int id;
  @Override public boolean equals(Object o) { return o instanceof Key k && k.id == id; }
  @Override public int hashCode() { return Integer.hashCode(id); }
}

Always override both together, on the same fields. And use immutable keys — mutating a key after insertion changes its hash, stranding it in the wrong bucket.

Iteration and fail-fast behavior

Most iterators are fail-fast: structurally modifying a collection during iteration (other than via the iterator) throws ConcurrentModificationException.

// throws
for (String s : list) if (s.isEmpty()) list.remove(s);

// safe
list.removeIf(String::isEmpty);
// or iterator.remove(), or map.values().removeIf(...)

Concurrent collections (CopyOnWriteArrayList, ConcurrentHashMap) are fail-safe — they iterate over a snapshot and don't throw.

Comparable vs Comparator, and generics

• Comparable<T> — the type's natural ordering, via compareTo implemented by the class.
• Comparator<T> — an external ordering, so you can define many without touching the class, and compose them.

users.sort(Comparator.comparingInt((User u) -> u.age).reversed()
                     .thenComparing(u -> u.name));

Generics give compile-time type safety and remove casts; remember type erasure means List<String> and List<Integer> share a runtime class (so no new T[], no instanceof List<String>). Bounded wildcards follow PECS — Producer extends, Consumer super.

Choosing the right collection

Match the structure to the dominant operation: ordered/indexed -> ArrayList; uniqueness -> HashSet; key lookups -> HashMap; sorted/range -> TreeMap/TreeSet; insertion order -> LinkedHashMap; stack/queue -> ArrayDeque; priority -> PriorityQueue; concurrent -> ConcurrentHashMap. Prefer the immutable factories (List.of, Map.of) for constants, and avoid the legacy synchronized Vector/Stack.

Recap

The framework gives you Lists (ordered), Sets (unique), Maps (key->value), and Queues/Deques, each with implementations tuned for different access patterns. ArrayList and HashMap are the everyday defaults; understand how HashMap's buckets, load factor, and treeification give O(1) average lookups, why equals/ hashCode must be consistent, and how fail-fast iteration and Comparable/ Comparator work. Pick by access pattern — lookup, order, uniqueness, concurrency — and the right collection usually falls out.