Что происходит внутри HashMap при вставке пары ключ-значение

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

Заглядывали ли вы внутрь стандартной библиотеки или только пользуетесь ей. По ответу видно, понимаете ли вы связь hashCode и equals, стоимость вставки и почему у HashMap бывает деградация до дерева.

Как отвечать

По шагам, как работает put:

• берётся key.hashCode(), затем перемешивание h ^ (h >>> 16). Оно нужно потому, что индекс вычисляется по младшим битам, а старшие иначе не участвовали бы вовсе;
• индекс корзины это (n - 1) & hash, где n это длина таблицы, всегда степень двойки. Ключ null кладётся в нулевую корзину;
• если корзина пуста, создаётся узел. Если нет, идёт сравнение: сначала хеши, потом ==, потом equals. Совпал ключ, значение перезаписывается и старое возвращается из put;
• новый ключ добавляется в конец списка корзины;
• если список в корзине дорастает до восьми узлов, он превращается в красно-чёрное дерево, но только когда таблица не меньше 64 ячеек. Иначе вместо дерева просто выполняется расширение;
• когда число элементов превышает capacity * loadFactor (по умолчанию 0.75), таблица удваивается. Хеши при этом не пересчитываются: узел либо остаётся на месте, либо уезжает на index + oldCap, и решает это один бит hash & oldCap.

Полезно добавить вывод: вставка амортизированно O(1), но отдельная вставка может стоить дорого, потому что попала на расширение.

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

Говорят «после восьми коллизий список становится деревом» и забывают про порог по размеру таблицы. На маленькой карте дерева не будет, будет расширение.

Переопределяют equals и не трогают hashCode. Объекты равны, а лежат в разных корзинах, и карта спокойно хранит два ключа, которые по коду одинаковы.

Считают, что HashMap можно использовать из нескольких потоков, раз «вставка атомарна». Она не атомарна: параллельные put теряют записи и ломают счётчик размера, для конкурентного доступа есть ConcurrentHashMap.