Вопрос с собеседования · Java

Что верно про ёмкость и load factor в HashMap?

MiddleКоллекции
Коротко

Ёмкость — степень двойки (индекс через hash & (n-1) вместо остатка), при превышении ёмкость × 0.75 таблица удваивается, а цепочка становится деревом только при длине ≥ 8 и ёмкости ≥ 64.

  • Меньше load factor — больше памяти, меньше коллизий
  • Известное число элементов — задать ёмкость: n / 0.75 + 1 (или HashMap.newHashMap(n) в Java 19)
  • При удвоении элемент остаётся на месте или переезжает на +old

А ещё До 64 вместо дерева — расширение таблицы

Попробуйте сами

HashMap: put, коллизия и resize

Подробно

Load factor задаёт компромисс между памятью и скоростью в обратную сторону, чем кажется: чем он меньше, тем раньше происходит расширение, тем больше памяти расходуется и тем реже коллизии. Значение 0.75 выбрано как удачный баланс. Ёмкость как степень двойки позволяет заменить дорогое взятие остатка побитовой операцией, но при этом в индекс попадали бы только младшие биты хеша — поэтому HashMap дополнительно подмешивает старшие биты в младшие. Про деревья важна деталь, которую часто упускают: перехода к дереву не происходит, пока таблица мала, — вместо этого выполняется расширение, потому что при маленькой таблице длинные цепочки чаще означают тесноту, а не плохой хеш.

Что хотят услышать

  • Степень двойки и маска.
  • Порог расширения и treeify.
  • Начальная ёмкость.

Частые ошибки

  • Считать, что уменьшение load factor экономит память.
  • Думать, что цепочка превращается в дерево всегда при достижении порога длины.

Проверьте себя

Несколько верных вариантов. Подумайте, потом откройте ответ.

Показать варианты и ответ
  • ✓Ёмкость — степень двойки, и индекс бакета считается побитовым И
  • ✓При превышении ёмкость × load factor (0.75) таблица удваивается
  • ✓Цепочка становится деревом только при достаточном размере таблицы
  • ✗Уменьшение load factor снижает потребление памяти, потому что таблица реже расширяется

Что спросят дальше

  • Зачем HashMap подмешивает старшие биты хеша в младшие?
  • Почему resize — дорогая операция и как её избежать?

Разбор темы

Связанные вопросы

Партнёр платформы

Разбор собеседования с sotto

После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.

Разбор собеседования