Как работает HashMap в Java при добавлении элемента (put)?

О, так, слушай, вот это я понимаю — тема! Ну что, разберём, как эта штука, HashMap, там внутри всё ебёт-переебёт, когда ты туда что-то суёшь.

Представь себе, у тебя есть этакая умная шкатулка с ящичками. Ты кричишь: «Эй, шкатулка, положи мне значение 30 под ключ "key1"!» И она, эта сука, не тупо в первый попавшийся ящик его пихает. Нет, она начинает свою магию.

Шаг первый, хеширование, ёпта. Она берёт твой ключ, этот "key1", и орёт ему: «А ну-ка, hashCode(), давай сюда!» Получает какую-то большую цифру. Но на этом всё не заканчивается, о нет! Внутри у неё есть своя хитрая функция hash(), которая эту цифру ещё так перемешает, так перетрёт, чтобы, блядь, разные ключи, но с похожими хешами, не сгрудились в одном месте. Это как если бы ты взял горсть гречки и просеял через сито — распределяется равномернее, нахуй.

Шаг второй, ищем ящик (bucket). У шкатулки есть массив этих самых ящичков. Длина массива — всегда степень двойки (16, 32, 64...), это не просто так, это для красоты и скорости. Она делает финт ушами: индекс = (размер_массива - 1) И хеш. Эта битовая операция & — быстрее деления и даёт индекс в пределах массива. Вуаля! Ящик найден.

Шаг третий, драма в ящике. Тут возможно три сценария, блядь:

1. Ящик пустой. Ура! Делов-то. Создаётся новый узелок (Node), туда кладётся твой ключ и значение, и всё — счастливый конец.
2. Ящик занят, но ключ совпал. Заходишь ты в ящик, а там уже сидит узел с ключом "key1" и старым значением 10. Ты такой: «Бро, подвинься, я тебя заменю». Проверяется: хеши равны? Да. И ключи либо один и тот же объект (==), либо равны по equals()? Тоже да. Всё, пидор, вынос мозга — старое значение 10 выкидывается нахуй, на его место записывается твоё 30. И никаких новых узлов.
3. Ящик занят, и это чужой парень (коллизия). Вот тут начинается самое интересное. Твой вычисленный индекс привёл тебя в ящик, где уже тусуется узел с другим ключом (скажем, "key2"), но хеш (после & (n-1)) у них совпал. Коллизия, сука! Что делает наш HashMap? Он не паникует. Он цепляет новый узел к старому, образуя связный список. «Стой тут в очереди, братан».

Шаг четвёртый, эволюция списка в дерево (Java 8+). А теперь представь, что в один ящик набилось, блядь, человек восемь. Итерировать по списку из восьми элементов — уже не O(1), а почти O(n), производительность проседает. Наш HashMap — не лох. Если список вырастает до порога (TREEIFY_THRESHOLD = 8) И при этом общий массив ящиков уже не мелкий (больше MIN_TREEIFY_CAPACITY = 64), то происходит магия. Связный список превращается в сбалансированное красно-чёрное дерево! Это уже не цепочка, а древовидная структура, где поиск не O(n), а O(log n). Роскошь, блядь! Но это только если ключи хорошо сравнимы. Иначе останется большим списком.

Шаг пятый, расширение (resize) — момент истины. Допустим, ты продолжаешь пихать в мапу элементы. Есть у неё такой параметр — loadFactor (коэффициент загрузки), по умолчанию 0.75. Когда количество элементов превышает ёмкость * коэффициент (например, 16 * 0.75 = 12), наступает resize. Массив ящиков увеличивается в два раза (становится 32). И вот тут, охуеть, происходит переезд! Все элементы вытаскиваются, для каждого заново вычисляется индекс уже относительно нового размера массива, и они раскидываются по новым ящикам. Операция дорогая, поэтому если знаешь примерное количество элементов, лучше указать начальную ёмкость конструктором, чтобы resize реже случался.

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 10); // 1. hash("key1") -> index, 2. Создание Node.
map.put("key2", 20); // Возможная коллизия, если index совпал с key1.
map.put("key1", 30); // Ключ совпал -> значение перезаписано с 10 на 30.

// Критически важно для ключей-объектов:
// - Корректно переопределять equals() и hashCode().
// - Хеш-функция должна давать равномерное распределение.

Вот и вся философия, блядь. Положил ключ — он прошёл через хеш-мясорубку, нашёл свой ящик, там либо всех победил и перезаписался, либо встал в очередь, а если очередь огромная — так там ещё и дерево может вырасти. А если всех слишком много — весь этот цирк переезжает в зал побольше. Красота, ёпта!