Что верно про ёмкость и load factor в HashMap?
Ёмкость — степень двойки (индекс через hash & (n-1) вместо остатка), при превышении ёмкость × 0.75 таблица удваивается, а цепочка становится деревом только при длине ≥ 8 и ёмкости ≥ 64.
- Меньше load factor — больше памяти, меньше коллизий
- Известное число элементов — задать ёмкость: n / 0.75 + 1 (или HashMap.newHashMap(n) в Java 19)
- При удвоении элемент остаётся на месте или переезжает на +old
А ещё До 64 вместо дерева — расширение таблицы
Подробно
Load factor задаёт компромисс между памятью и скоростью в обратную сторону, чем кажется: чем он меньше, тем раньше происходит расширение, тем больше памяти расходуется и тем реже коллизии. Значение 0.75 выбрано как удачный баланс. Ёмкость как степень двойки позволяет заменить дорогое взятие остатка побитовой операцией, но при этом в индекс попадали бы только младшие биты хеша — поэтому HashMap дополнительно подмешивает старшие биты в младшие. Про деревья важна деталь, которую часто упускают: перехода к дереву не происходит, пока таблица мала, — вместо этого выполняется расширение, потому что при маленькой таблице длинные цепочки чаще означают тесноту, а не плохой хеш.
Что хотят услышать
- Степень двойки и маска.
- Порог расширения и treeify.
- Начальная ёмкость.
Частые ошибки
- Считать, что уменьшение load factor экономит память.
- Думать, что цепочка превращается в дерево всегда при достижении порога длины.
Проверьте себя
Несколько верных вариантов. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✓Ёмкость — степень двойки, и индекс бакета считается побитовым И
- ✓При превышении ёмкость × load factor (0.75) таблица удваивается
- ✓Цепочка становится деревом только при достаточном размере таблицы
- ✗Уменьшение load factor снижает потребление памяти, потому что таблица реже расширяется
Что спросят дальше
- Зачем HashMap подмешивает старшие биты хеша в младшие?
- Почему resize — дорогая операция и как её избежать?
Разбор темы
- HashMap изнутри: бакеты, treeify, resize
Таблица бакетов, перемешивание хеша и индекс, превращение цепочки в дерево, ресайз и load factor, контракт ключа.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.