Что происходит при переполнении корзин в HashMap и как расширяется количество бакетов
Что проверяют
Читали ли вы HashMap изнутри или знаете по пересказу. Вопрос про рост таблицы отсеивает тех, кто помнит слова «коэффициент загрузки» и «удваивается», но не может сказать, когда именно происходит расширение и что случается с уже лежащими элементами.
Как отвечать
Главное разделение: коллизии складываются внутри одного бакета, а размер таблицы растёт не от длины цепочки, а от общего числа записей.
- таблица это массив, его длина всегда степень двойки, индекс вычисляется как
(n - 1) & hash; - порог равен длине массива, умноженной на коэффициент загрузки 0.75;
- как только число записей превышает порог, вызывается
resize: новый массив вдвое длиннее, порог тоже удваивается; - элементы переносятся без пересчёта хеша, он сохранён в поле узла;
- при удвоении значим ровно один новый бит, поэтому цепочка делится на две: часть остаётся на прежнем индексе, часть уезжает на индекс плюс старая длина, относительный порядок узлов сохраняется.
Добавьте про цену: resize проходит всю таблицу, поэтому вставка дешёвая амортизированно, но отдельная вставка может стоить линейного времени. Если объём известен заранее, задавайте начальную ёмкость от ожидаемого числа записей, делённого на коэффициент загрузки, иначе карта успеет перестроиться несколько раз.
Где спотыкаются
Говорят, что при расширении заново считается hashCode. Хеш кэшируется в узле, пересчитывается только индекс. Дорогой hashCode бьёт по вставке и поиску, а не по перестройке таблицы.
Второе: путают порог с длиной цепочки. Восемь элементов в одном бакете таблицу не расширяют, они превращают список в дерево. Расширение считает записи по всей карте, независимо от того, как они разложены.
Третье: думают, что new HashMap<>(2) вытерпит два элемента. После создания таблицы порог там равен единице, и перестройка случится уже на втором вызове put. Та же ошибка в общем виде: в конструктор передают ожидаемое число записей как есть, забыв поделить его на коэффициент загрузки.