Java Collections & Concurrency
List, Set, Map implementations, time complexity, ConcurrentHashMap, iterators, and thread-safe patterns.
Interview tip Say complexity aloud: "HashMap get/put O(1) average; ArrayList get O(1), insert middle O(n)."
① Collection hierarchy overview
Iterable → Collection → List, Set, Queue
List — ordered, allows duplicates (ArrayList, LinkedList)
Set — no duplicates (HashSet, LinkedHashSet, TreeSet)
Queue / Deque — FIFO, LIFO (ArrayDeque, PriorityQueue, BlockingQueue)
Map — key-value (separate hierarchy): HashMap, TreeMap, LinkedHashMap, ConcurrentHashMap
Prefer interfaces in API signatures:
List<T>, Map<K,V> — swap implementations without breaking callers.② List implementations
| Implementation | Backing | get | add/end | add/middle | Use when |
|---|---|---|---|---|---|
| ArrayList | Dynamic array | O(1) | O(1)* amortized | O(n) | Default list — random access |
| LinkedList | Doubly linked nodes | O(n) | O(1) | O(1)* with iterator | Deque ops, rare — ArrayDeque often better |
| CopyOnWriteArrayList | Copy on write | O(1) | O(n) copy | O(n) | Read-heavy, rare writes (listeners) |
*LinkedList rarely wins — cache-unfriendly; ArrayDeque for queue/stack.
③ Set implementations
| Implementation | Order | Complexity | Notes |
|---|---|---|---|
| HashSet | None | O(1) avg add/contains | Backed by HashMap |
| LinkedHashSet | Insertion order | O(1) avg | Predictable iteration |
| TreeSet | Sorted (natural/Comparator) | O(log n) | Red-black tree; no null |
| EnumSet | Enum declaration order | O(1) | Bit vector — very compact |
④ Map implementations
| Implementation | Order | Null key/value | Thread-safe | Use |
|---|---|---|---|---|
| HashMap | None | 1 null key, null values OK | No | Default map |
| LinkedHashMap | Insertion or access order | Same as HashMap | No | LRU cache with removeEldestEntry |
| TreeMap | Sorted keys | No null key | No | Range queries, navigableMap |
| ConcurrentHashMap | None | No nulls | Yes | Concurrent reads/writes |
| Hashtable | None | No nulls | Yes (legacy) | Avoid — use ConcurrentHashMap |
HashMap internals (Java 8+): array of buckets → linked list or tree (if bucket > 8 nodes). Load factor 0.75; resize 2× when threshold exceeded.
⑤ ConcurrentHashMap deep dive
Java 8+ ConcurrentHashMap: bucket-level locking (synchronized first node) or CAS for empty buckets — finer granularity than pre-8 segment locks. Reads generally lock-free.
No null keys/values — ambiguity in concurrent context.
Atomic operations:
No null keys/values — ambiguity in concurrent context.
Atomic operations:
putIfAbsent, compute, merge — atomic read-modify-write.| vs | Collections.synchronizedMap | ConcurrentHashMap |
|---|---|---|
| Lock scope | Entire map | Per-bucket / CAS |
| Read concurrency | One at a time | Multiple concurrent reads |
| Iteration | Must external sync | Weakly consistent iterator |
| Nulls | Allowed (HashMap) | Not allowed |
⑥ Iterators — fail-fast vs weakly consistent
Fail-fast: ArrayList, HashMap iterators throw
Fix: use iterator.remove(), copy collection, or concurrent collection.
ConcurrentModificationException if collection structurally modified during iteration (except iterator's own remove). Detected via modCount.Fix: use iterator.remove(), copy collection, or concurrent collection.
Weakly consistent: ConcurrentHashMap, CopyOnWriteArrayList — iterator reflects state at creation time; may or may not see concurrent updates; never throws CME.
⑦ Concurrency essentials
| Mechanism | Purpose | Pitfall |
|---|---|---|
| synchronized | Mutual exclusion on object monitor | Deadlock if lock order inconsistent |
| ReentrantLock | Explicit lock, tryLock, fairness | Must unlock in finally |
| volatile | Visibility across threads | Not atomic for i++ — use AtomicInteger |
| Atomic* classes | Lock-free CAS operations | ABA problem rare in Java util |
| ExecutorService | Thread pool abstraction | Unbounded queue → OOM under load |
Thread pool pattern
Producer threads
BlockingQueue
ThreadPoolExecutor
Worker tasks
⑧ BlockingQueue types
| Queue | Behavior | Use |
|---|---|---|
| ArrayBlockingQueue | Bounded array, one lock | Fixed capacity backpressure |
| LinkedBlockingQueue | Optional bounded linked nodes | Common in Executors — watch unbounded |
| SynchronousQueue | Zero capacity — handoff | CachedThreadPool direct transfer |
| PriorityBlockingQueue | Unbounded priority heap | Scheduled tasks by priority |
| DelayQueue | Elements available after delay | Scheduled execution |
Design pattern: producers
put(), worker pool take() — decouples rate; bounded queue prevents memory blowup.⑨ Interview Q&A
| Question | Answer sketch |
|---|---|
| HashMap vs Hashtable? | HashMap not sync, allows null key; Hashtable legacy synchronized — use ConcurrentHashMap |
| Comparable vs Comparator? | Comparable natural order in class; Comparator external, multiple sort orders |
| How HashSet stores elements? | HashMap with dummy PRESENT value — uniqueness via keys |
| LRU cache in Java? | LinkedHashMap(accessOrder=true) + removeEldestEntry override |
| CopyOnWriteArrayList when? | Many readers, few writers — snapshot iteration, expensive writes |
⑩ Revision checklist
- Picked List/Set/Map impl with complexity justification
- Explained HashMap bucket → list/tree structure
- Contrasted ConcurrentHashMap vs synchronizedMap
- Described fail-fast CME cause and fixes
- Designed worker pool with BlockingQueue type choice
- Named atomic classes vs volatile for counters