Collections Framework

Introduction

Every enterprise Java service — payment ledgers, user sessions, rate-limit counters, in-memory caches — stores data in the Java Collections Framework (JCF). Pick the wrong collection and your API goes from 5ms to 500ms. Use ArrayList where you need HashSet dedup and you leak memory. Share a plain HashMap across threads and you corrupt production state under load.

The JCF is a hierarchy of interfaces — List, Set, Map, Queue — with multiple implementations tuned for different access patterns. Staff engineers do not memorize APIs; they know internal architecture (array vs linked nodes vs hash buckets), Big-O complexity, and thread-safety trade-offs to choose correctly in architecture review.

This lesson teaches collections the way Netflix, LinkedIn, and Goldman Sachs engineers apply them: ArrayList for indexed access, LinkedList almost never in production, HashMap for O(1) lookups, ConcurrentHashMap for shared caches — with internal diagrams, complexity tables, and Spring Boot usage patterns.

Business problem

Wrong collection choice causes production incidents:

• O(n) in hot path: LinkedList.get(500000) in pagination — 500ms response times because random access walks the chain.
• HashMap race condition: Shared static HashMap<String, Session> in Spring singleton — infinite loop or lost entries under concurrent requests (JDK 7) or corrupted buckets (JDK 8+).
• Memory blow-up: ArrayList holding 10M dedup keys — should be HashSet; 4× memory waste storing duplicate slot semantics.
• ConcurrentModificationException: Iterating ArrayList while another thread removes — 2 AM alert storm after deploy.

Why this topic exists

Collections exist because raw arrays are insufficient for enterprise software:

• Dynamic sizing: Arrays fixed at creation — ArrayList grows automatically with amortized O(1) append.
• Abstraction: Code to List<Payment> interface — swap ArrayList for CopyOnWriteArrayList without caller changes.
• Domain semantics: Set enforces uniqueness; Queue enforces FIFO — types express intent to readers and compilers.
• Algorithm leverage: Collections.sort(), streams, and binary search require List — framework built on JCF.
• Performance tuning: Choosing implementation is an architecture decision — same as choosing database index strategy.

Core concepts

JCF hierarchy — four core interfaces:

• List: Ordered, allows duplicates. ArrayList (array-backed), LinkedList (doubly-linked nodes). Use when index access or positional order matters.
• Set: No duplicates. HashSet (hash table), LinkedHashSet (insertion order), TreeSet (sorted, red-black tree). Use for uniqueness — seen IDs, dedup.
• Map: Key-value pairs, no duplicate keys. HashMap (hash buckets), LinkedHashMap (order), TreeMap (sorted keys), ConcurrentHashMap (thread-safe). Use for lookups by key.
• Queue / Deque: FIFO/LIFO processing. LinkedList, ArrayDeque, PriorityQueue, BlockingQueue. Use for task queues, BFS, rate limiting buffers.

Internal architecture

Internal architecture — how data is stored:

ArrayList                          LinkedList
┌───┬───┬───┬───┬───┬───┐          ┌──────┐    ┌──────┐    ┌──────┐
│ 0 │ 1 │ 2 │ 3 │ 4 │...│          │ Node │◀──▶│ Node │◀──▶│ Node │
└───┴───┴───┴───┴───┴───┘          │ data │    │ data │    │ data │
  Object[] elementData              │ next │    │ prev │    │ next │
  size, modCount                    └──────┘    └──────┘    └──────┘
  default cap 10 → grow 1.5×         head/tail pointers

HashMap (JDK 8+)                   ConcurrentHashMap
┌─────────────────────────┐        ┌─────────────────────────┐
│ Node[] table (buckets)  │        │ Node[] segments/buckets │
│  [0]→ Node→Node (chain) │        │  lock per bucket/seg    │
│  [1]→ null              │        │  CAS + synchronized     │
│  [2]→ TreeNode (RB tree)│        │  no whole-map lock      │
│  load factor 0.75       │        │  safe concurrent R/W    │
│  resize 2× when full    │        │                         │
└─────────────────────────┘        └─────────────────────────┘
  hash(key) → bucket index             computeIfAbsent atomic

Big-O Summary (average case):
                    get      add       remove    contains   iterate
  ArrayList         O(1)     O(1)*     O(n)      O(n)       O(n)
  LinkedList        O(n)     O(1)      O(1)**    O(n)       O(n)
  HashMap           O(1)     O(1)      O(1)      —          O(n)
  ConcurrentHashMap O(1)     O(1)      O(1)      —          O(n)
  HashSet           O(1)     O(1)      O(1)      O(1)       O(n)
  * amortized; ** O(1) if you have Node reference; O(n) by index

Architecture and complexity diagrams:

Code walkthrough

Collections in a banking transaction processor — with output and complexity notes:

• ArrayList: Default List — array backing, O(1) get, amortized O(1) add at tail. Use for 99% of List cases.
• HashSet: Backed by HashMap — O(1) contains for dedup. Use when uniqueness matters.
• HashMap: O(1) lookup by account ID — default Map. Never null in multi-threaded shared state.
• ArrayDeque: Preferred Queue over LinkedList — array ring buffer, better cache locality.
• ConcurrentHashMap: Thread-safe without locking entire map — use for caches, rate limiters, session stores.

import java.util.*;
import java.util.concurrent.*;

public class CollectionsDemo {

    public static void main(String[] args) {
        // ── LIST: ordered payments, duplicates allowed ──
        List<String> paymentLog = new ArrayList<>();  // O(1) append amortized
        paymentLog.add("PAY-001");
        paymentLog.add("PAY-002");
        paymentLog.add("PAY-001");  // duplicate OK in List
        System.out.println("List (ArrayList): " + paymentLog);
        System.out.println("  get(0): " + paymentLog.get(0));  // O(1) random access

        // ── SET: unique account IDs seen today ──
        Set<String> seenAccounts = new HashSet<>();   // O(1) add/contains
        seenAccounts.add("ACC-100");
        seenAccounts.add("ACC-200");
        seenAccounts.add("ACC-100");  // silently ignored — no duplicate
        System.out.println("Set (HashSet): " + seenAccounts + " size=" + seenAccounts.size());

        // ── MAP: account ID → balance lookup ──
        Map<String, Double> balances = new HashMap<>();  // O(1) get/put
        balances.put("ACC-100", 1500.00);
        balances.put("ACC-200", 3200.50);
        System.out.println("Map (HashMap): ACC-100 balance = " + balances.get("ACC-100"));

        // ── QUEUE: pending transactions (FIFO) ──
        Queue<String> pendingQueue = new ArrayDeque<>();  // O(1) offer/poll
        pendingQueue.offer("TXN-A");
        pendingQueue.offer("TXN-B");
        System.out.println("Queue (ArrayDeque): process " + pendingQueue.poll());  // FIFO → TXN-A

        // ── CONCURRENT MAP: thread-safe rate limit cache ──
        ConcurrentHashMap<String, Integer> rateLimits = new ConcurrentHashMap<>();
        rateLimits.put("user-42", 0);
        // Atomic compute — safe under concurrent HTTP requests
        rateLimits.compute("user-42", (k, v) -> v == null ? 1 : v + 1);
        rateLimits.compute("user-42", (k, v) -> v + 1);
        System.out.println("ConcurrentHashMap: user-42 hits = " + rateLimits.get("user-42"));

        // ── ArrayList vs LinkedList — random access demo ──
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 100_000; i++) { arrayList.add(i); linkedList.add(i); }
        long t1 = System.nanoTime();
        arrayList.get(50_000);   // O(1) — direct array index
        long arrayTime = System.nanoTime() - t1;
        long t2 = System.nanoTime();
        linkedList.get(50_000);  // O(n) — walk 50k nodes
        long linkedTime = System.nanoTime() - t2;
        System.out.printf("get(50000): ArrayList=%dns LinkedList=%dns (LinkedList ~%dx slower)%n",
            arrayTime, linkedTime, linkedTime / Math.max(arrayTime, 1));
    }
}

/*
 * Expected output (approximate):
 *   List (ArrayList): [PAY-001, PAY-002, PAY-001]
 *     get(0): PAY-001
 *   Set (HashSet): [ACC-200, ACC-100] size=2
 *   Map (HashMap): ACC-100 balance = 1500.0
 *   Queue (ArrayDeque): process TXN-A
 *   ConcurrentHashMap: user-42 hits = 2
 *   get(50000): ArrayList=~100ns LinkedList=~500000ns (LinkedList ~5000x slower)
 */

Production example

Spring Boot — collections in production services:

• computeIfAbsent: Atomic check-then-act — prevents cache stampede vs get + put race.
• ConcurrentHashMap.newKeySet(): Thread-safe Set backed by ConcurrentHashMap.
• @RequestBody List: Jackson deserializes JSON array to ArrayList — document max batch size to prevent OOM.
• Stream on List: Prefer streams over indexed for-loop unless index needed — clearer and parallelizable.

@Service
public class PaymentCacheService {
    // ConcurrentHashMap — thread-safe cache shared across requests
    private final ConcurrentHashMap<String, PaymentStatus> statusCache =
        new ConcurrentHashMap<>();

    public PaymentStatus getStatus(String paymentId) {
        return statusCache.computeIfAbsent(paymentId, this::fetchFromDatabase);
    }
}

@Service
public class FraudDetectionService {
    // HashSet — O(1) blacklist lookup
    private final Set<String> blockedAccounts = ConcurrentHashMap.newKeySet();
    // or load into HashSet at startup for read-heavy, rarely-updated data

    public boolean isBlocked(String accountId) {
        return blockedAccounts.contains(accountId);  // O(1)
    }
}

@RestController
public class PaymentController {
    @PostMapping("/batch")
    public BatchResult processBatch(@RequestBody List<PaymentRequest> requests) {
        // Spring deserializes JSON array → ArrayList by default
        Map<String, PaymentResult> results = new HashMap<>();
        Queue<PaymentRequest> retryQueue = new ArrayDeque<>();
        for (PaymentRequest req : requests) {
            try {
                results.put(req.id(), process(req));
            } catch (RetryableException e) {
                retryQueue.offer(req);  // FIFO retry
            }
        }
        return new BatchResult(results, retryQueue.size());
    }
}

// Repository returns List — use Stream API, not manual index loops
List<Payment> overdue = paymentRepository.findOverdue(since);
overdue.stream().filter(p -> p.amount() > threshold).toList();

Enterprise case study

LinkedIn — ConcurrentHashMap at feed scale: LinkedIn's early feed caching layer used ConcurrentHashMap<Long, FeedItem> for in-memory hot feeds — millions of concurrent reads/writes without global lock contention. When teams mistakenly replaced it with Collections.synchronizedMap(new HashMap<>()), p99 latency spiked 10× under peak traffic because every read acquired the global lock. Reverting to ConcurrentHashMap restored throughput. Lesson: synchronized wrappers serialize all access; ConcurrentHashMap enables parallel bucket access.

• Problem: synchronizedMap global lock — 500 threads blocked on every cache read.
• Root cause: Developer assumed "synchronized = thread-safe = good" without understanding lock granularity.
• Fix: ConcurrentHashMap with computeIfAbsent for cache population; Caffeine for TTL eviction at next scale tier.
• ArrayList lesson: Feed ranking pre-computes scores into ArrayList — O(1) index access for pagination; LinkedList would fail SLA.

Performance considerations

Big-O in production — when constants matter:

• ArrayList get: O(1) — nanoseconds. Use for pagination, random access, sorting.
• LinkedList get: O(n) — avoid entirely for random access. Only use for frequent head/tail insert AND no random access.
• HashMap get/put: O(1) average — dominates database lookup when used as cache. Initial capacity if size known: new HashMap<>(expectedSize / 0.75f) avoids resize.
• ConcurrentHashMap: O(1) with lower concurrency overhead than synchronizedMap. Size() is approximate under concurrent writes — do not use for strict counts.
• ArrayList remove(0): O(n) — shifts all elements. Use ArrayDeque for queue semantics, not ArrayList.remove(0).
• Iteration + modify: Use iterator.remove() or removeIf — not enhanced-for with list.remove() (ConcurrentModificationException).

Security considerations

Collection misuse creates security vulnerabilities:

• HashMap hashDoS: Attacker submits keys with colliding hashes — O(n) bucket chains. JDK 8+ treeifies; still use bounded input validation.
• Unbounded collections from user input: JSON array with 10M elements → ArrayList OOM. Enforce max batch size in API validation.
• Shared mutable collections: Returning internal HashMap from getter — caller modifies internal state. Return Collections.unmodifiableMap() or copy.
• ConcurrentHashMap and null: Does not allow null keys/values — fail-fast vs HashMap null ambiguity in concurrent code.

Scalability considerations

Collections at enterprise scale:

• In-memory limits: HashMap with 10M entries ≈ GB heap — move to Redis/Caffeine with eviction for large caches.
• ConcurrentHashMap sizing: Set initial capacity for known load — resize is expensive (rehash all entries).
• Parallel streams: List.parallelStream() uses ForkJoinPool — fine for CPU-bound on large lists; avoid for I/O or small collections (overhead > benefit).
• Batch processing: Partition List into chunks — process 1000 payments per batch to bound memory and transaction size.

Production challenges

Real collection-related production failures:

• ConcurrentModificationException: Enhanced for-loop + list.remove() during iteration — use removeIf or Iterator.remove().
• HashMap infinite loop (JDK 7): Concurrent resize corruption — fixed in JDK 8 but lesson remains: never share unsynchronized HashMap across threads.
• LinkedList in pagination: ORM returns LinkedList, code calls get(page * size) — O(n) per page request, SLA breach.
• Null key in ConcurrentHashMap: NPE at put time — validate before cache put.
• equals/hashCode missing on key object: HashMap get returns null despite "containing" object — custom key classes must override both.

Common mistakes

• Using LinkedList "because insert is O(1)" — ArrayList tail insert is O(1) amortized and get is O(1); LinkedList loses on almost every workload.
• Vector or Hashtable — legacy synchronized collections; use ArrayList + Collections.synchronizedList or ConcurrentHashMap instead.
• HashMap as shared cache without ConcurrentHashMap — data corruption under Spring singleton @Service.
• Forgetting to override hashCode when overriding equals — HashSet/HashMap silently break.
• Assuming iteration order of HashMap — non-deterministic; use LinkedHashMap for insertion order, TreeMap for sorted.

Debugging guide

Diagnose collection performance and correctness issues:

• Slow lookup: Check collection type — O(n) linear scan in List vs O(1) HashMap. Profile with JFR or async-profiler.
• ConcurrentModificationException: Stack trace shows modCount mismatch — find concurrent modification during iteration.
• Memory leak in cache: HashMap grows unbounded — add eviction (Caffeine), TTL, or WeakReference for cache keys.
• Wrong equals: map.get(key) null but map.containsKey similar object — inspect hashCode/equals implementation.

# Heap dump analysis — dominator tree for ArrayList/HashMap retention
jcmd <pid> GC.heap_dump /tmp/heap.hprof
# Eclipse MAT: look for largest ArrayList, HashMap, ConcurrentHashMap dominators

# Quick size check in running pod
jcmd <pid> GC.class_stats | grep -E "HashMap|ArrayList|ConcurrentHashMap"

Best practices

• Program to interfaces: List<T>, Set<T>, Map<K,V> — declare interface type, instantiate ArrayList/HashMap.
• Default choices: ArrayList for List, HashMap for Map, HashSet for Set, ArrayDeque for Queue.
• Multi-threaded shared state: ConcurrentHashMap — never HashMap + synchronized wrapper for high concurrency.
• Set initial capacity when size known — new HashMap<>( (int)(size / 0.75f) + 1 ) avoids rehash.
• Return unmodifiable views from getters: Collections.unmodifiableMap(internalMap) — preserve encapsulation.
• Override equals AND hashCode together for any class used as HashMap/HashSet key.
• Use Stream API and removeIf — not manual index manipulation during removal.

Anti-patterns

• LinkedList<E> list = new LinkedList<>() as default List — almost always wrong in 2026.
• Vector / Hashtable — legacy; use ArrayList or ConcurrentHashMap.
• synchronizedMap for high-concurrency cache — global lock bottleneck.
• Storing large datasets entirely in HashMap without eviction — heap OOM; use Caffeine/Redis.
• Using List.contains() in hot path for membership — O(n); use HashSet for O(1) contains.

Staff engineer notes

• In code review, ask "why this collection?" — ArrayList vs HashMap vs ConcurrentHashMap reveals whether author understands access pattern.
• LinkedList exists in interviews, not production — staff engineers flag LinkedList in PRs unless explicit deque use case with benchmarks.
• ConcurrentHashMap.computeIfAbsent is the idiomatic cache pattern — replaces manual double-checked locking on HashMap.
• Big-O matters when n > 1000 in hot paths — O(n) List scan on 100 items is fine; on 1M items is an outage.
• At Netflix/LinkedIn scale, in-memory ConcurrentHashMap is tier-1 cache; Caffeine adds TTL/size eviction for tier-2 — know when to graduate.

Interview questions

Hands-on exercise

Lab: Collection selection — run playground, then extend:

• Run demo — observe List duplicates vs Set uniqueness vs Map lookup vs Queue FIFO.
• Add duplicate detection: given List of account IDs, return unique count using HashSet.
• Implement simple cache: ConcurrentHashMap computeIfAbsent simulating DB fetch (sleep 100ms first call only).
• Time ArrayList.get(50000) vs LinkedList.get(50000) on 100k elements — record ratio.
• Bonus: explain which collection you'd use for fraud blacklist, payment log, and pending retry queue.

Press Run to execute. Real javac + JVM via remote API. Falls back to simulator on network failure.

Architecture trade-offs

• ArrayList vs LinkedList: ArrayList wins virtually all workloads; LinkedList for niche deque with no random access.
• HashMap vs ConcurrentHashMap: HashMap wins single-threaded simplicity; ConcurrentHashMap wins shared mutable state.
• HashMap vs TreeMap: HashMap O(1) unsorted; TreeMap O(log n) sorted keys.
• In-memory ConcurrentHashMap vs Redis: CHM wins latency (nanoseconds); Redis wins multi-JVM and persistence.

Summary

The Collections Framework is the data structure layer every Java service runs on — choosing ArrayList over LinkedList, HashMap over synchronized wrappers, and ConcurrentHashMap for shared state separates staff engineers from bug generators. You now understand internal architecture, Big-O trade-offs, and production patterns in Spring Boot. Next: Generics and type-safe collections.

Key takeaways

• List/Set/Map/Queue — program to interfaces; default impls: ArrayList, HashSet, HashMap, ArrayDeque.
• ArrayList: O(1) get/add-tail; LinkedList: O(n) get — avoid LinkedList in production hot paths.
• HashMap: bucket array + chain/tree; O(1) avg; override equals+hashCode on keys.
• ConcurrentHashMap: bucket-level concurrency; use for shared caches; computeIfAbsent for atomic load.
• Big-O matters at scale — List.contains O(n) fails at 1M; HashSet.contains O(1) wins.