Cheatsheet and Decision Guide

📋 At a Glance

"

One-liner: This is your go-to reference for making collection decisions quickly and correctly.

---

Collection Decision Trees

List Decision Tree

Need a List?
│
├── Need thread safety?
│   ├── Mostly reads, rare writes → CopyOnWriteArrayList
│   ├── High concurrency writes → Collections.synchronizedList() or custom
│   └── Single-threaded → Continue below
│
├── Know size upfront?
│   ├── Yes, immutable data → List.of() or Arrays.asList()
│   └── No, or mutable → Continue below
│
├── Access pattern?
│   ├── Random access (get by index) → ArrayList
│   ├── Frequent insert/remove at ends → ArrayDeque (as Deque)
│   ├── Frequent insert/remove in middle* → ArrayList (still usually wins)
│   └── Need ListIterator for bidirectional? → LinkedList (rare)
│
└── Default choice → ArrayList

* LinkedList rarely wins in practice due to cache locality.
  Profile before choosing LinkedList.

Set Decision Tree

Need a Set (unique elements)?
│
├── Need thread safety?
│   ├── High concurrency → ConcurrentHashMap.newKeySet()
│   │                      or ConcurrentSkipListSet (sorted)
│   └── Single-threaded → Continue below
│
├── Need ordering?
│   ├── Sorted order → TreeSet (O(log n) operations)
│   ├── Insertion order → LinkedHashSet
│   └── No ordering needed → HashSet (O(1) operations)
│
├── Enum values only?
│   └── Yes → EnumSet (fastest, most memory efficient)
│
├── Need navigable operations?
│   └── floor(), ceiling(), subSet() → TreeSet or ConcurrentSkipListSet
│
└── Default choice → HashSet

Map Decision Tree

Need a Map (key-value pairs)?
│
├── Need thread safety?
│   ├── General purpose → ConcurrentHashMap
│   ├── Sorted + concurrent → ConcurrentSkipListMap
│   └── Single-threaded → Continue below
│
├── Need ordering?
│   ├── Sorted by key → TreeMap
│   ├── Insertion order → LinkedHashMap
│   ├── Access order (LRU) → LinkedHashMap(capacity, loadFactor, true)
│   └── No ordering → HashMap
│
├── Enum keys?
│   └── Yes → EnumMap (fastest, most memory efficient)
│
├── Weak references needed?
│   ├── Weak keys (for caching) → WeakHashMap
│   └── Weak values → Custom with WeakReference values
│
├── Identity comparison?
│   └── Yes (compare by ==, not equals) → IdentityHashMap
│
├── Need navigable operations?
│   └── floorKey(), ceilingKey(), subMap() → TreeMap
│
└── Default choice → HashMap

Queue/Deque Decision Tree

Need a Queue or Deque?
│
├── Need thread safety?
│   ├── Bounded blocking → ArrayBlockingQueue
│   ├── Unbounded blocking → LinkedBlockingQueue
│   ├── Priority blocking → PriorityBlockingQueue
│   ├── Transfer semantics → LinkedTransferQueue
│   ├── Delay-based → DelayQueue
│   └── Non-blocking concurrent → ConcurrentLinkedQueue/Deque
│
├── Need priority ordering?
│   └── Yes → PriorityQueue (min-heap by default)
│
├── Need both ends (stack + queue)?
│   └── Yes → ArrayDeque
│
├── FIFO queue only?
│   └── Yes → ArrayDeque (as Queue)
│
├── LIFO stack only?
│   └── Yes → ArrayDeque (as Deque, use push/pop)
│
└── Default choice → ArrayDeque

Note: Never use Stack class (legacy). Never use LinkedList for queue
      (poor cache locality).

---

Complexity Tables

List Operations

*Amortized O(1), occasional O(n) for resize **O(1) if already at position via iterator

Set Operations

Map Operations

Queue/Deque Operations

*Amortized O(1) **Has maximum capacity of Integer.MAX_VALUE - 8

---

Code Snippets Reference

Initialization Patterns

JAVA(53 lines)
Code
Loading syntax highlighter...
Show all 53 lines

Common Operations

JAVA(70 lines)
Code
Loading syntax highlighter...
Show all 70 lines

Conversion Between Types

JAVA(54 lines)
Code
Loading syntax highlighter...
Show all 54 lines

Stream Patterns

JAVA(67 lines)
Code
Loading syntax highlighter...
Show all 67 lines

Concurrent Patterns

JAVA(51 lines)
Code
Loading syntax highlighter...
Show all 51 lines

---

Top 20 Collection Pitfalls

1. Not Pre-sizing Collections

JAVA(5 lines)
Code
Loading syntax highlighter...

2. Using LinkedList

JAVA(6 lines)
Code
Loading syntax highlighter...

3. O(n) contains() on List

JAVA(6 lines)
Code
Loading syntax highlighter...

4. Modifying Collection During Iteration

JAVA(13 lines)
Code
Loading syntax highlighter...

5. Forgetting Map Key Immutability

JAVA(8 lines)
Code
Loading syntax highlighter...

6. Wrong hashCode/equals Contract

JAVA(14 lines)
Code
Loading syntax highlighter...

7. Collections.synchronized* Compound Operations

JAVA(9 lines)
Code
Loading syntax highlighter...

8. Not Using Enum Collections

JAVA(5 lines)
Code
Loading syntax highlighter...

9. Returning Mutable Internal Collections

JAVA(11 lines)
Code
Loading syntax highlighter...

10. Boxing Overhead in Hot Paths

JAVA(11 lines)
Code
Loading syntax highlighter...

11. Stream Overhead on Small Collections

JAVA(7 lines)
Code
Loading syntax highlighter...

12. Creating Collections in Hot Paths

JAVA(11 lines)
Code
Loading syntax highlighter...

13. Ignoring Initial Capacity for HashMap

JAVA(8 lines)
Code
Loading syntax highlighter...

14. Using toArray() Wrong

JAVA(10 lines)
Code
Loading syntax highlighter...

15. toMap() Without Merge Function

JAVA(11 lines)
Code
Loading syntax highlighter...

16. Not Using computeIfAbsent for Nested Maps

JAVA(10 lines)
Code
Loading syntax highlighter...

17. Forgetting null Handling in TreeMap/TreeSet

JAVA(6 lines)
Code
Loading syntax highlighter...

18. Using get() + put() Instead of merge()

JAVA(6 lines)
Code
Loading syntax highlighter...

19. Memory Leaks with Static Collections

JAVA(20 lines)
Code
Loading syntax highlighter...

20. Expensive I/O in ConcurrentHashMap.compute()

JAVA(18 lines)
Code
Loading syntax highlighter...

---

Interview Questions Bank

Fundamentals (Questions 1-10)

1. What is the difference between Collection and Collections?
   • Collection: Interface (root of collection hierarchy)
   • Collections: Utility class with static methods
2. Why doesn't Map extend Collection?
   • Map stores key-value pairs, not single elements
   • Semantically different (no meaningful add(E) method)
3. What is the difference between Comparable and Comparator?
   • Comparable: Natural ordering, implemented by class itself
   • Comparator: External comparator, allows multiple orderings
4. What is the contract between equals() and hashCode()?
   • Equal objects must have equal hashCodes
   • Unequal objects may have equal hashCodes (collision)
5. What happens if you use a mutable object as HashMap key?
   • If the object changes after being added, hash lookup fails
   • Entry becomes unreachable but still exists (memory leak)
6. What is the difference between fail-fast and fail-safe iterators?
   • Fail-fast: Throws CME if collection modified during iteration
   • Fail-safe: Operates on copy, doesn't throw (Copy-on-write, concurrent)
7. What is Iterator and what is its advantage over for-each?
   • Iterator allows safe removal during iteration
   • For-each is syntactic sugar over Iterator
8. What is the difference between Iterator and ListIterator?
   • ListIterator: Bidirectional, can add/set elements, knows index
   • Iterator: Forward-only, can only remove
9. What is load factor in HashMap?
   • Threshold for resize (default 0.75)
   • Trade-off between memory and collision probability
10. What is the initial capacity of ArrayList and HashMap?
    • ArrayList: 10 (or 0 for default constructor in Java 8+)
    • HashMap: 16

ArrayList & LinkedList (Questions 11-15)

1. When would you use LinkedList over ArrayList?
   • Almost never in practice
   • Theoretically: Frequent insertions at known positions via iterator
   • ArrayList usually wins due to cache locality
2. How does ArrayList grow?
   • Grows by 50% (newCapacity = oldCapacity + oldCapacity >> 1)
   • Arrays.copyOf() creates new array
3. Why is ArrayList preferred over Vector?
   • Vector is synchronized (unnecessary overhead for single-threaded)
   • Vector grows by 100% (wasteful)
   • ArrayList is more modern
4. What is the time complexity of ArrayList.add(int index, E)?
   • O(n) - must shift all elements after index
5. How do you convert ArrayList to array and vice versa?
   • ArrayList to array: list.toArray(new String[0])
   • Array to ArrayList: new ArrayList<>(Arrays.asList(array))

HashMap & HashSet (Questions 16-25)

1. How does HashMap work internally?
   • Array of buckets, hash determines bucket
   • LinkedList for collisions (tree if > 8 elements)
   • Resize at load factor threshold
2. What is the difference between HashMap and Hashtable?
   • HashMap: Not synchronized, allows null key/value
   • Hashtable: Synchronized, no nulls, legacy
3. Why is String a good HashMap key?
   • Immutable (hashCode cached)
   • Well-distributed hashCode
   • equals() properly implemented
4. What happens when two keys have same hashCode?
   • Both stored in same bucket (collision)
   • equals() distinguishes them
   • Performance degrades to O(n) or O(log n) with tree bins
5. When does HashMap convert LinkedList to tree?
   • TREEIFY_THRESHOLD = 8 (when bin size exceeds)
   • UNTREEIFY_THRESHOLD = 6 (when shrinks below)
   • MIN_TREEIFY_CAPACITY = 64 (minimum table size)
6. What is the difference between HashMap and TreeMap?
   • HashMap: O(1), unordered, uses hashCode/equals
   • TreeMap: O(log n), sorted, uses Comparable/Comparator
7. What is LinkedHashMap?
   • HashMap with insertion-order (or access-order) iteration
   • Doubly-linked list maintains order
   • Useful for LRU caches
8. What is EnumMap and when to use it?
   • Map optimized for enum keys
   • Uses ordinal() as array index
   • 10x faster than HashMap for enum keys
9. What is IdentityHashMap?
   • Uses == instead of equals() for key comparison
   • Uses System.identityHashCode()
   • Useful for object graph traversal
10. How to make HashMap thread-safe?
    • Use ConcurrentHashMap (recommended)
    • Collections.synchronizedMap() (not for compound ops)

Concurrent Collections (Questions 26-35)

1. How does ConcurrentHashMap work?
   • Java 8+: Per-node synchronization + CAS
   • No global lock, high concurrency
   • Atomic compute/merge operations
2. What is the difference between ConcurrentHashMap and synchronizedMap?
   • ConcurrentHashMap: Fine-grained locking, atomic operations
   • synchronizedMap: Single global lock, no atomic operations
3. What is CopyOnWriteArrayList?
   • Creates new array copy on every write
   • Thread-safe iteration without locks
   • Best for read-heavy, write-rare scenarios
4. When would you use BlockingQueue?
   • Producer-consumer patterns
   • Thread communication
   • Rate limiting
5. What is the difference between offer() and put() in BlockingQueue?
   • offer(): Returns false if queue full
   • put(): Blocks until space available
6. What is ConcurrentSkipListMap?
   • Concurrent sorted map (like TreeMap but thread-safe)
   • O(log n) operations
   • Based on skip list data structure
7. What is ConcurrentLinkedQueue?
   • Non-blocking concurrent queue
   • CAS-based operations
   • Unbounded, lock-free
8. How to create thread-safe Set?
   • ConcurrentHashMap.newKeySet() (recommended)
   • Collections.synchronizedSet(new HashSet<>())
   • CopyOnWriteArraySet (read-heavy)
9. What is DelayQueue?
   • Elements become available after delay expires
   • Elements must implement Delayed interface
   • Useful for scheduled tasks
10. What is TransferQueue?
    • Extended BlockingQueue with transfer semantics
    • Producer can wait for consumer to receive
    • LinkedTransferQueue implementation

Streams & Collectors (Questions 36-42)

1. What is the difference between map() and flatMap()?
   • map(): One-to-one transformation
   • flatMap(): One-to-many, flattens nested structures
2. What is the difference between findFirst() and findAny()?
   • findFirst(): Returns first element (deterministic)
   • findAny(): Returns any element (faster in parallel)
3. What are Collectors.toMap() pitfalls?
   • Throws on duplicate keys without merge function
   • Returns HashMap (not guaranteed type)
   • Null values can cause issues
4. How to collect to specific collection type?
   • Collectors.toCollection(TreeSet::new)
5. What is the difference between reduce() and collect()?
   • reduce(): For immutable reduction (combining elements)
   • collect(): For mutable reduction (building collections)
6. How does groupingBy() work?
   • Groups elements by classifier function
   • Returns Map<K, List> by default
   • Can use downstream collectors
7. When to use parallel streams?
   • Large datasets (>10,000 elements)
   • CPU-intensive operations
   • Independent elements (no shared state)

Immutable Collections (Questions 43-47)

1. What is the difference between List.of() and Arrays.asList()?
   • List.of(): Truly immutable, doesn't allow null
   • Arrays.asList(): Fixed-size but elements modifiable, backed by array
2. What is the difference between Collections.unmodifiableList() and List.copyOf()?
   • unmodifiableList(): View, changes in original reflect
   • copyOf(): Independent copy, immutable
3. How to create immutable Map with >10 entries?

   • Map.ofEntries(Map.entry("a", 1), Map.entry("b", 2), ...)

4. What happens if you call add() on immutable collection?
   • Throws UnsupportedOperationException
5. Why use immutable collections?
   • Thread-safe without synchronization
   • Safe to share across components
   • Prevents accidental modification

Java 21+ Features (Questions 48-50)

1. What is SequencedCollection in Java 21?
   • New interface for collections with encounter order
   • Adds getFirst(), getLast(), reversed()
   • ArrayList, LinkedList, TreeSet implement it
2. What is the reversed() method?
   • Returns reversed view of collection
   • Modifications reflect in original
   • O(1) operation (view, not copy)
3. How do Virtual Threads affect collection choice?
   • Blocking operations no longer expensive
   • BlockingQueue preferred over busy-waiting
   • Many threads = more concurrent collection usage

---

Quick Selection Guide

For general-purpose use:
├── List: ArrayList
├── Set: HashSet (unordered) or LinkedHashSet (ordered)
├── Map: HashMap (unordered) or LinkedHashMap (ordered)
├── Queue: ArrayDeque
└── Stack: ArrayDeque (use push/pop)

For sorted data:
├── Set: TreeSet
├── Map: TreeMap
└── Queue: PriorityQueue

For thread safety:
├── Map: ConcurrentHashMap
├── Set: ConcurrentHashMap.newKeySet()
├── List: CopyOnWriteArrayList (read-heavy)
├── Queue: LinkedBlockingQueue or ConcurrentLinkedQueue
└── Don't use: Collections.synchronized*

For memory efficiency:
├── Enum keys: EnumSet, EnumMap
├── Primitives: Eclipse Collections, Trove, FastUtil
└── Small fixed sets: Set.of(), EnumSet

For immutability:
├── List: List.of() or List.copyOf()
├── Set: Set.of() or Set.copyOf()
└── Map: Map.of() or Map.copyOf()

---

📝 Summary

This reference guide consolidates everything you've learned across the Java Collections Compendium. Keep it handy for quick lookups during development and interview preparation.

1. Choose wisely: The right collection makes code faster AND cleaner
2. Know internals: Understanding HashMap's tree bins or ArrayList's growth helps debugging
3. Contract matters: hashCode/equals contract violations cause subtle bugs
4. Thread safety isn't free: Use concurrent collections only when needed
5. Profile before optimizing: Big-O hides constant factors that matter
6. Immutability wins: Prefer immutable collections when possible
7. Modern Java helps: Java 9+ factory methods and Java 21+ sequenced collections

---

Series Navigation

• Previous: Part 28: Performance, Memory & Production Pitfalls
• Series Start: Part 0: How to Use This Series

---

Complete Series Index

Part I: Foundations

• Part 0: How to Use This Series
• Part 1: Collection Framework Architecture
• Part 2: Generics Mastery
• Part 3: equals() & hashCode() Contract
• Part 4: Iterators and Iteration

Part II: Arrays & Primitives

• Part 5: Arrays, BitSet & Primitives

Part III: List Implementations

• Part 6: ArrayList Deep Dive
• Part 7: LinkedList Deep Dive
• Part 8: List Utilities

Part IV: Set Implementations

• Part 9: HashSet Internals
• Part 10: TreeSet & NavigableSet
• Part 11: EnumSet & LinkedHashSet

Part V: Map Implementations

• Part 12: HashMap Buckets & Collisions
• Part 13: HashMap Tree Bins
• Part 14: TreeMap & NavigableMap
• Part 15: LinkedHashMap & Specialized Maps

Part VI: Queue & Deque

• Part 16: Queue, Deque & ArrayDeque
• Part 17: PriorityQueue & Heap

Part VII: Concurrent Collections

• Part 18: ConcurrentHashMap Internals
• Part 19: ConcurrentHashMap Advanced
• Part 20: Copy-on-Write Collections
• Part 21: Blocking Queues

Part VIII: Modern Collections

• Part 22: Immutable Collections
• Part 23: Java 21+ Sequenced Collections
• Part 24: Streams & Collectors
• Part 25: Views, Wrappers & Defensive Patterns

Part IX: Integration & Production

• Part 26: Collections in JPA, Jackson & Spring
• Part 27: Testing & Debugging Collections
• Part 28: Performance, Memory & Production Pitfalls
• Part 29: Decision Guide & Quick Reference