Как работает HashMap внутри и что такое bucket

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

Знаете ли вы HashMap на уровне исходников, а не на уровне «ключ-значение за O(1)». Следом почти всегда спрашивают, что будет, если изменить ключ после вставки, и почему HashMap нельзя делить между потоками.

Как отвечать

Внутри лежит массив Node<K,V>[] table, каждая его ячейка и есть bucket. Узел хранит hash, key, value и ссылку next на следующий узел той же корзины. Массив создаётся лениво, при первом put.

• индекс корзины: берётся hashCode() ключа, старшие 16 бит подмешиваются к младшим (h ^ (h >>> 16)), затем считается (n-1) & hash. Поэтому размер таблицы всегда степень двойки;
• коллизии: узлы одной корзины образуют связный список, с Java 8 новый узел добавляется в хвост. Когда в корзине больше 8 элементов и в таблице не меньше 64 ячеек, список превращается в красно-чёрное дерево из TreeNode, при уменьшении до 6 обратно в список;
• поиск: сначала сравниваются хэши, потом ссылки или equals(). Поэтому ключу нужны согласованные equals() и hashCode();
• рост: ёмкость по умолчанию 16, loadFactor 0.75, порог 12 элементов. При превышении таблица удваивается, и каждый узел либо остаётся на своём индексе, либо сдвигается ровно на старую длину, полный пересчёт хэшей не нужен.

Итог по сложности: в среднем O(1), в худшем случае O(n) для списка и O(log n) для дерева. Ключ null допустим один, он всегда лежит в корзине 0.

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

Говорят, что hashCode() переопределяют, «чтобы не было коллизий». Коллизии неизбежны, переопределяют ради контракта с equals(): без него два равных ключа окажутся в разных корзинах, и get вернёт null.

Называют порог в 8 элементов, но не знают про MIN_TREEIFY_CAPACITY: пока таблица меньше 64 ячеек, переполненная корзина не превращается в дерево, вместо этого вся таблица расширяется.

Предлагают «следить за заполненностью и вручную увеличивать массив». HashMap расширяется сам, а вручную разумно только задать начальную ёмкость, если число элементов известно заранее, и сэкономить на перестройках.