Колекції
30 питань і відповідей у розділі Колекції.
Питання цього розділу
- Які основні інтерфейси Collection Framework?
- В чому різниця між List, Set та Queue?
- В чому різниця між ArrayList та LinkedList?
- Коли використовувати ArrayList, а коли LinkedList?
- Яка часова складність операцій в ArrayList?
- Яка часова складність операцій в LinkedList?
- Що таке Vector і чим він відрізняється від ArrayList?
- Що таке Stack?
- Що таке Queue і які реалізації існують?
- Що таке Deque?
- В чому різниця між HashSet, LinkedHashSet та TreeSet?
- Як працює HashSet всередині?
- Що таке TreeSet і як він працює?
- Що таке Map і які реалізації існують?
- В чому різниця між HashMap, LinkedHashMap та TreeMap?
- Коли використовувати TreeMap?
- Що таке WeakHashMap?
- Що таке ConcurrentHashMap?
- Як ConcurrentHashMap забезпечує thread-safety?
- Що таке CopyOnWriteArrayList?
- Коли використовувати synchronized collections?
- Як отримати synchronized колекцію?
- Що таке Collections.unmodifiableList()?
- Як працює Collections.unmodifiableList() всередині
- В чому різниця між Iterator та ListIterator?
- Що таке fail-fast та fail-safe ітератори?
- Що таке ConcurrentModificationException?
- Як правильно видаляти елементи під час ітерації?
- Що таке Comparable та Comparator?
- Які операції підтримує інтерфейс Collection?
Навігатор по розділу
30 запитань для підготовки до співбесіди на Middle Java Developer.
📋 Усі запитання
🗺️ Карта залежностей тем
┌──────────────────────────────────────────┐
│ 1. Collection Framework (Огляд) │
│ Collection, List, Set, Queue, Map │
└──┬──────────┬──────────┬─────────────────┘
│ │ │
┌──────────┘ │ └──────────┐
▼ ▼ ▼
┌───────────────┐ ┌───────────────┐ ┌────────────────────┐
│ LIST (3-10) │ │ SET (11-13) │ │ MAP (14-20) │
│ 3. ArrayList │ │ 11. HashSet │ │ 14. Map огляд │
│ vs Linked │ │ vs Linked │ │ 15. HashMap vs │
│ 4. Коли що │ │ vs Tree │ │ LinkedHashMap │
│ 5-6. Big O │ │ 12. HashSet │ │ vs TreeMap │
│ 7. Vector │ │ всередині │ │ 16. Коли TreeMap │
│ 8. Stack │ │ 13. TreeSet │ │ 17. WeakHashMap │
│ 9. Queue │ │ │ │ 18-19. CHM │
│ 10. Deque │ │ │ │ 20. CopyOnWrite │
└───────┬───────┘ └───────┬───────┘ └────────┬───────────┘
│ │ │
└────────────────────┼─────────────────────┘
▼
┌──────────────────────────────────────────┐
│ THREAD-SAFETY (18-22) │
│ 18-19. ConcurrentHashMap │
│ 20. CopyOnWriteArrayList │
│ 21-22. synchronized collections │
└──────────────────────────────────────────┘
┌──────────────────────────────────────────┐
│ ITERATORS та ВИДАЛЕННЯ (23-28) │
│ 23-24. unmodifiableList │
│ 25. Iterator vs ListIterator │
│ 26. fail-fast vs fail-safe │
│ 27. ConcurrentModificationException │
│ 28. Правильне видалення │
└──────────────────────────────────────────┘
┌──────────────────────────────────────────┐
│ ПОРІВНЯННЯ та ЗАГАЛЬНІ ОПЕРАЦІЇ (29, 31) │
│ 29. Comparable vs Comparator │
│ 31. Операції Collection │
└──────────────────────────────────────────┘
🎯 Рекомендований порядок вивчення
🟢 Рівень Junior (тижні 1-2)
| Крок | Тема | Файли | Мета |
|---|---|---|---|
| 1 | Огляд Collection Framework | Q1, Q2 | Ієрархія інтерфейсів, List vs Set vs Queue |
| 2 | List: ArrayList vs LinkedList | Q3, Q4 | Коли що використовувати |
| 3 | Vector, Stack, Queue, Deque | Q7, Q8, Q9, Q10 | Legacy та сучасні аналоги |
| 4 | Set: HashSet vs TreeSet | Q11, Q13 | Унікальність та сортування |
| 5 | Map: HashMap vs TreeMap | Q14, Q15, Q16 | Коли що використовувати |
| 6 | unmodifiableList | Q23, Q24 | Захисне копіювання |
| 7 | Iterator vs ListIterator | Q25 | Ітерація та видалення |
🟡 Рівень Middle (тижні 3-4)
| Крок | Тема | Файли | Мета |
|---|---|---|---|
| 1 | Big O ArrayList | Q5 | Амортизація, ресайз, System.arraycopy |
| 2 | Big O LinkedList | Q6 | Cache miss, GC pressure |
| 3 | HashSet всередині | Q12 | hashCode, equals, treeification |
| 4 | WeakHashMap | Q17 | WeakReference, GC, ReferenceQueue |
| 5 | synchronized collections | Q21, Q22 | Decorator, mutex, check-then-act |
| 6 | fail-fast/fail-safe | Q26 | modCount, CME, snapshot |
| 7 | CME | Q27 | Причини, subList trap, views |
| 8 | Видалення при ітерації | Q28 | removeIf, Iterator.remove |
| 9 | Comparable vs Comparator | Q29 | Timsort, overflow, транзитивність |
| 10 | Операції Collection | Q31 | bulk ops, parallelStream, Spliterator |
🔴 Рівень Senior (тижні 5-6)
| Крок | Тема | Файли | Мета |
|---|---|---|---|
| 1 | ArrayList internals | Q5 (Senior) | SIMD, branch prediction, CPU pipeline |
| 2 | LinkedList internals | Q6 (Senior) | Cache locality catastrophe, pipeline stall |
| 3 | CHM thread-safety | Q18, Q19 | CAS, volatile, synchronized, LongAdder |
| 4 | CopyOnWriteArrayList | Q20 | Fail-safe, stale data, eventual consistency |
| 5 | HashSet internals | Q12 (Senior) | Treeification, transient, hash collisions |
| 6 | TreeMap internals | Q13, Q16 | Red-black tree, rebalancing, Skip List |
| 7 | unmodifiableList internals | Q24 | Defensive copy, RandomAccess, GC pressure |
| 8 | Concurrent collections | Q21 (Senior) | High contention, compound operations |
🔗 Ключові зв’язки між темами
Тема: List
Q3 (ArrayList vs LinkedList) → Q4 (Коли що) → Q5-Q6 (Big O)
↓
Q7 (Vector) → Q8 (Stack) → Q9 (Queue) → Q10 (Deque)
Ключові зв’язки:
- Q3 ↔ Q5-Q6: Big O пояснює, чому ArrayList швидший за LinkedList на практиці
- Q4 ↔ Q28: removeIf() вирішує проблему видалення в циклі
- Q7 ↔ Q18: Vector → ConcurrentHashMap (еволюція thread-safety)
- Q9-Q10 ↔ Q18: BlockingQueue, ConcurrentLinkedQueue як альтернативи
Тема: Set
Q11 (HashSet vs LinkedHashSet vs TreeSet) → Q12 (HashSet всередині) → Q13 (TreeSet)
Ключові зв’язки:
- Q11 ↔ Q14: Set використовує Map всередині (HashSet = HashMap<E, Object>)
- Q12 ↔ Q15: Внутрішня будова HashSet = internals HashMap
- Q13 ↔ Q16: TreeSet = TreeMap.keySet(), коли потрібен TreeMap
Тема: Map
Q14 (Map огляд) → Q15 (HashMap vs LinkedHashMap vs TreeMap) → Q16 (TreeMap)
↓ ↓ ↓
Q17 (WeakHashMap) Q12 (HashSet всередині) Q18-19 (ConcurrentHashMap)
↓
Q20 (CopyOnWriteArrayList)
Ключові зв’язки:
- Q14 ↔ Q1: Map технічно НЕ Collection, але частина Framework
- Q15 ↔ Q12: HashMap internals = HashSet internals
- Q17 ↔ Q3 (Пам’ять та GC): WeakReference, GC, SoftReference
- Q18-19 ↔ Q21: CHM vs synchronizedList — різні підходи до thread-safety
- Q18 ↔ Q20: CHM для mixed навантаження, COWAL для read-heavy
Тема: Thread-Safety
Q7 (Vector) → Q21 (synchronized collections) → Q22 (Як отримати)
↓ ↓ ↓
Q18 (CHM) ←────────── Q19 (CHM thread-safety) Q20 (CopyOnWriteArrayList)
Ключові зв’язки:
- Q7 ↔ Q21: Vector — legacy підхід, synchronizedList — сучасний
- Q18 ↔ Q20: CHM = granular locks, COWAL = snapshot
- Q21 ↔ Q26: synchronizedList = fail-fast, CHM = weakly consistent
Тема: Iterators та видалення
Q25 (Iterator vs ListIterator) → Q26 (fail-fast vs fail-safe)
↓ ↓
Q27 (CME) ←─────────────────────── Q28 (Правильне видалення)
↑
Q23-24 (unmodifiableList)
Ключові зв’язки:
- Q25 ↔ Q28: Iterator.remove() — правильний спосіб видалення
- Q26 ↔ Q27: fail-fast кидає CME, fail-safe — ні
- Q23-24 ↔ Q27: unmodifiableList не захищає від CME через view
🎯 Шпаргалка: що знати для кожного рівня
🟢 Junior
- Ієрархія: Collection → List/Set/Queue, Map — паралельно
- ArrayList vs LinkedList: ArrayList для більшості випадків
- HashSet = унікальність, TreeSet = сортування
- HashMap = ключ-значення, TreeMap = сортування за ключем
- Vector/Stack — legacy, використовуйте ArrayList/ArrayDeque
- Iterator для перебору, не можна видаляти в for-each
- unmodifiableList = захисна обгортка, не глибока імутабельність
🟡 Middle
- Big O: ArrayList add = амортиз. O(1), get = O(1); LinkedList get = O(n)
- Cache locality: ArrayList > LinkedList у 10-100 разів при ітерації
- HashSet = HashMap всередині, treeification при > 8 елементів у корзині
- ConcurrentHashMap: CAS + volatile + synchronized, НЕ блокує читання
- CopyOnWriteArrayList: snapshot, fail-safe, O(n) копіювання при запису
- fail-fast = modCount, CME = детектор багів (не синхронізація!)
- removeIf() = O(n) для ArrayList, Iterator.remove() = O(n²)
- Comparable = natural order, Comparator = зовнішнє сортування
🔴 Senior
- System.arraycopy: JVM intrinsic, SIMD, branch prediction
- LinkedList cache miss: кожен вузол — окремий об’єкт у купі
- CHM: CounterCells (LongAdder), ForwardingNode, ReservationNode
- WeakHashMap: ReferenceQueue, expungeStaleEntries, Minor GC
- ConcurrentHashMap size(): не блокування, а лічильник через CAS
- Timsort: стабільне сортування, транзитивність, overflow
- Spliterator: характеристики (SIZED, DISTINCT, SORTED) для Stream оптимізації
- Java 21: SequencedCollection/SequencedSet/SequencedMap
📝 Формат кожного файлу
Кожен файл містить:
- 🟢 Junior Level — базове розуміння, прості аналогії, приклади
- 🟡 Middle Level — внутрішня будова, типові помилки, практичні приклади
- 🔴 Senior Level — deep dive, edge cases, production experience, monitoring
- 🎯 Шпаргалка для інтерв’ю — ключові тези, часті запитання, червоні прапорці, пов’язані теми