HashMap equals hashCode
29 питань і відповідей у розділі HashMap equals hashCode.
Питання цього розділу
- Як влаштований HashMap всередині?
- Що таке bucket (корзина) в HashMap?
- Як HashMap визначає, в який bucket покласти елемент?
- Що таке колізія в HashMap?
- Як HashMap обробляє колізії?
- Що відбувається при досягненні 8 елементів в одному bucket?
- Що таке контракт equals() і hashCode()?
- Якщо два об’єкти рівні за equals(), що можна сказати про їх hashCode()?
- Якщо два об’єкти мають однаковий hashCode(), чи обов’язково вони рівні за equals()?
- Що станеться, якщо перевизначити equals(), але не перевизначити hashCode()?
- Що станеться, якщо перевизначити hashCode(), але не перевизначити equals()?
- Чи можна використовувати змінюваний об’єкт як ключ в HashMap?
- Що станеться, якщо змінити ключ після додавання в HashMap?
- Які вимоги пред’являються до ключа HashMap?
- Чому String часто використовують як ключ в HashMap?
- Що таке load factor в HashMap?
- Що таке capacity в HashMap?
- Коли відбувається rehashing (resize) в HashMap?
- Що відбувається під час rehashing (resize)?
- Яка часова складність операцій get() та put() в HashMap?
- Коли часова складність може стати O(n)?
- Як HashMap працює в багатопотоковому середовищі?
- Що таке ConcurrentHashMap і чим він відрізняється від HashMap?
- Чи можна зберігати null ключ в HashMap?
- Чи можна зберігати null значення в HashMap?
- В чому різниця між HashMap та Hashtable?
- Що таке WeakHashMap?
- Як правильно підібрати початкову capacity для HashMap?
- Яку реалізацію Map обрати? (Порівняння)
Навігатор по розділу
29 питань для підготовки до співбесіди на Middle Java Developer.
📋 Усі питання
🗺️ Карта залежностей тем
┌──────────────────────────────────────────┐
│ 1. HashMap всередині (Огляд) │
│ структура, put/get, treeification │
└──┬──────────┬──────────┬─────────────────┘
│ │ │
┌──────────┘ │ └──────────┐
▼ ▼ ▼
┌───────────────┐ ┌───────────────┐ ┌────────────────────┐
│ BUCKET і │ │ КОЛІЗІЇ │ │ КОНТРАКТ │
│ ІНДЕКСАЦІЯ │ │ (4-6) │ │ equals/hashCode │
│ (2-3) │ │ 4. Що таке │ │ (7-11) │
│ 2. Bucket │ │ колізія │ │ 7. Контракт │
│ 3. Індексація │ │ 5. Обробка │ │ 8. equals→hashCode │
│ │ │ колізій │ │ 9. hashCode→equals │
│ │ │ 6. 8 елементів │ │ 10. equals без hashCode
│ │ │ → treeify │ │ 11. hashCode без equals
└───────┬────────┘ └───────┬───────┘ └────────┬───────────┘
│ │ │
└─────────────────────┼─────────────────────┘
▼
┌──────────────────────────────────────────┐
│ ПРОБЛЕМИ З КЛЮЧАМИ (12-15) │
│ 12. Змінюваний ключ │
│ 13. Зміна після додавання │
│ 14. Вимоги до ключа │
│ 15. Чому String — найкращий ключ │
└──────────────────────────────────────────┘
┌──────────────────────────────────────────┐
│ ПАРАМЕТРИ І RESIZE (16-21) │
│ 16. Load Factor │
│ 17. Capacity │
│ 18-19. Rehashing │
│ 20-21. Big O і деградація │
└──────────────────────────────────────────┘
┌──────────────────────────────────────────┐
│ MULTI-THREADING і NULL (22-27) │
│ 22. HashMap в багатопотоковому сер-щі │
│ 23. ConcurrentHashMap │
│ 24-25. null ключі/значення │
│ 26. HashMap vs Hashtable │
│ 27. WeakHashMap │
└──────────────────────────────────────────┘
┌──────────────────────────────────────────┐
│ ПРАКТИКА (28-29) │
│ 28. Вибір capacity │
│ 29. Що краще (порівняння Map) │
└──────────────────────────────────────────┘
🎯 Рекомендований порядок вивчення
🟢 Рівень Junior (тижні 1-2)
| Крок | Тема | Файли | Мета |
|---|---|---|---|
| 1 | Контракт equals/hashCode | Q7, Q8, Q9 | Рефлексивність, симетричність, транзитивність |
| 2 | Структура HashMap | Q1, Q2, Q3 | Хеш-таблиця, бакети, індексація |
| 3 | Колізії | Q4, Q5 | Що таке, як обробляються |
| 4 | Помилки equals/hashCode | Q10, Q11 | Що буде якщо перевизначити тільки один |
| 5 | null ключі/значення | Q24, Q25 | Чому HashMap допускає, Hashtable — ні |
| 6 | HashMap vs Hashtable | Q26 | Legacy vs сучасний підхід |
🟡 Рівень Middle (тижні 3-4)
| Крок | Тема | Файли | Мета |
|---|---|---|---|
| 1 | Treeification | Q6 | 8 елементів, capacity >= 64, червоно-чорне дерево |
| 2 | Змінювані ключі | Q12, Q13 | Чому не можна, що станеться |
| 3 | Вимоги до ключа | Q14, Q15 | Immutable, hashCode контракт, String, Enum |
| 4 | Load Factor і Capacity | Q16, Q17, Q28 | Trade-offs, формула розрахунку |
| 5 | Rehashing | Q18, Q19 | Коли відбувається, алгоритм resize |
| 6 | Big O | Q20, Q21 | O(1) → O(log n) → O(n), коли деградує |
| 7 | HashMap в багатопотоковому сер-щі | Q22 | Race conditions, corruption |
🔴 Рівень Senior (тижні 5-6)
| Крок | Тема | Файли | Мета |
|---|---|---|---|
| 1 | HashMap internals | Q1 (Senior) | spread-функція, XOR, treeification, churn |
| 2 | Rehashing internals | Q19 (Senior) | Lo/Hi split, один біт, transfer |
| 3 | ConcurrentHashMap | Q23 | CAS, CounterCell, ForwardingNode, Weakly Consistent |
| 4 | WeakHashMap | Q27 | WeakReference, ReferenceQueue, GC, реальні use cases |
| 5 | O(n) деградація | Q21 (Senior) | Hash Flooding Attack, capacity < 64 |
| 6 | Multi-threading | Q22 (Senior) | safe publication, CAS vs volatile, infinite loop Java 7 |
| 7 | Порівняння Map | Q29 | Memory footprint, trade-offs, коли що обрати |
🔗 Ключові зв’язки між темами
Тема: Контракт equals/hashCode
Q7 (Контракт) → Q8 (equals→hashCode) → Q9 (hashCode≠equals)
↓ ↓
Q10 (equals без hashCode) Q11 (hashCode без equals)
Ключові зв’язки:
- Q7 ↔ Q14: Вимоги до ключа = розширений контракт equals/hashCode
- Q10 ↔ Q12-Q13: Порушення контракту = проблеми зі змінюваними ключами
- Q8 ↔ Q15: String як ідеальний ключ — immutable + cached hashCode
Тема: Нутрощі HashMap
Q1 (Структура) → Q2 (Bucket) → Q3 (Індексація)
↓ ↓ ↓
Q4 (Колізія) → Q5 (Обробка) → Q6 (Treeification)
↓
Q18-19 (Rehashing)
Ключові зв’язки:
- Q3 ↔ Q4:
(n-1) & hash— причина колізій індексу - Q5 ↔ Q6: Обробка колізій → treeification при 8 елементах
- Q6 ↔ Q18: При capacity < 64 — resize замість treeification
- Q19 ↔ Q22: Resize — головна точка corruption в багатопотоковому середовищі
Тема: Параметри і продуктивність
Q16 (Load Factor) → Q17 (Capacity) → Q18 (Rehashing)
↓ ↓
Q20 (Big O) ←────────────────────── Q19 (Resize internals)
↓
Q21 (Деградація O(n))
Ключові зв’язки:
- Q16 ↔ Q17: Load Factor × Capacity = threshold для resize
- Q17 ↔ Q28: Формула
capacity = expectedSize / loadFactor + 1 - Q18 ↔ Q19: Коли resize → як resize (Lo/Hi split)
- Q20 ↔ Q21: Нормальний O(1) → деградація до O(log n) або O(n)
Тема: Multi-threading та спеціальні Map
Q22 (HashMap в MT) → Q23 (ConcurrentHashMap)
↓ ↓
Q24-25 (null) Q26 (vs Hashtable)
↓ ↓
Q27 (WeakHashMap) ←─── Q29 (Що краще)
Ключові зв’язки:
- Q22 ↔ Q23: Проблеми HashMap → рішення ConcurrentHashMap
- Q24-25 ↔ Q23: CHM забороняє null — чому це важливо для потокобезпеки
- Q26 ↔ Q23: Hashtable (legacy, synchronized) → CHM (сучасний, CAS)
- Q27 ↔ Q12: WeakHashMap = змінювані ключі під контролем GC
🎯 Шпаргалка: що знати для кожного рівня
🟢 Junior
- HashMap = хеш-таблиця: масив бакетів, кожен бакет = linked list
- put/get: hashCode() → spread →
(n-1) & hash→ індекс бакета - equals() і hashCode() — ОБОВ’ЯЗАНІ перевизначатися разом
- Рівні об’єкти → однаковий hashCode. Однаковий hashCode ≠ рівні об’єкти
- HashMap допускає null ключ (один) і null значення
- Hashtable — legacy, не використовуйте
🟡 Middle
- Колізія — норма, не баг. HashMap обробляє через linked list
- Treeification (Java 8+): при 8 елементах в бакеті і capacity >= 64 → червоно-чорне дерево O(log n)
- Load Factor 0.75 — trade-off між пам’яттю і колізіями
- Capacity завжди степінь двійки. Формула:
expectedSize / 0.75 + 1 - Rehashing = подвоєння масиву, Lo/Hi split по одному біту hash
- Змінюваний ключ = баг: після зміни hashCode пошук йде не в тому бакеті
- String — ідеальний ключ: immutable + cached hashCode
🔴 Senior
- spread-функція: XOR старших і молодших 16 біт для рівномірного розподілу
- Resize в Java 8+: Tail Insertion (запобігає infinite loop Java 7), але HashMap все ще NOT thread-safe
- ConcurrentHashMap: CAS + CounterCell (O(1) size), ForwardingNode при resize, Weakly Consistent ітератор
- WeakHashMap: ключі = WeakReference, видаляються при GC. НЕ для кешів!
- Hash Flooding Attack: зловмисник створює колізії → O(n). Рішення: рандомізація хешування
- Пам’ять: HashMap ~48MB на 1M entries, ConcurrentHashMap ~56MB, TreeMap ~80MB
- При capacity < 64 і колізіях — resize замість treeification → O(n) зберігається
📝 Формат кожного файлу
Кожен файл містить:
- 🟢 Junior Level — базове розуміння, прості аналогії, приклади
- 🟡 Middle Level — нутрощі, типові помилки, практичні приклади
- 🔴 Senior Level — deep dive, edge cases, production досвід, моніторинг
- 🎯 Шпаргалка для співбесіди — ключові тези, часті питання, червоні прапорці, пов’язані теми