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 experience, monitoring
- 🎯 Шпаргалка для интервью — ключевые тезисы, частые вопросы, красные флаги, связанные темы