Как вычисляется номер корзины (бакета) в HashMap при вставке элемента

Что проверяют

Знаете ли вы реализацию HashMap глубже формулы «hashCode по модулю размера». Хотят услышать про перемешивание битов и про то, почему ёмкость всегда степень двойки. Следом обычно спрашивают, что происходит при расширении таблицы и когда бакет превращается в дерево.

Как отвечать

Начиная с Java 8, индекс считается в три шага:

• hashCode ключа: вызывается key.hashCode(). Для ключа null хеш равен 0, поэтому такой ключ всегда лежит в нулевом бакете;
• перемешивание: метод hash() делает h ^ (h >>> 16), то есть смешивает старшие 16 бит с младшими. Без этого ключи, чьи хеши отличаются только старшими битами, падали бы в один бакет;
• индекс: (n - 1) & hash, где n это длина массива. Так как n степень двойки, операция равна остатку от деления, но дешевле и не даёт отрицательных чисел.

Ёмкость по умолчанию 16, массив создаётся лениво при первом put. Если передать в конструктор 100, tableSizeFor округлит до 128. Порог расширения равен ёмкость × loadFactor (0.75), для 16 это 12 элементов. При удвоении таблицы хеши не пересчитываются: по биту hash & oldCap каждый элемент либо остаётся на своём индексе, либо уезжает на index + oldCap.

Внутри бакета элементы лежат списком. Когда элемент добавляется в бакет, где уже 8 узлов (TREEIFY_THRESHOLD), а таблица не меньше 64 (MIN_TREEIFY_CAPACITY), список превращается в красно-чёрное дерево. При таблице меньше 64 вместо этого происходит расширение. Если после расширения в дереве осталось 6 узлов или меньше, оно сворачивается обратно в список.

Где спотыкаются

Пропускают шаг перемешивания. Пример «хеш -1 при ёмкости 16 даёт индекс 15» неверен: после h ^ (h >>> 16) младшие биты обнуляются, и ключ Integer со значением -1 попадает в бакет 0.

Говорят, что коллизия бывает только при одинаковых hashCode. В один бакет попадают и разные хеши с совпадающими младшими битами, а таких случаев гораздо больше.

Путают порог дерева: называют 8 без условия про ёмкость 64 или считают, что деревом становится вся таблица, а не отдельный бакет.