Какая сложность добавления элемента в HashMap

А, ну это же классика, ёпта! Смотри, как тут всё просто, но с подвохом, как всегда в жизни.

Добавить что-то в HashMap — это, в принципе, операция быстрая, как удар током. В среднем, говорят, сложность O(1), то есть константная. Представь, что ты закидываешь носки в ящик — в среднем ты просто открыл и кинул. Быстро и просто.

Но, блядь, есть же нюансы, хитрая жопа! Это ж программирование, тут без подлянки никуда.

• Коллизии, сука. Это когда разные ключи по своей хэш-функции вдруг попадают в один и тот же бакет, в одну ячейку. Ну, типа, два разных носка застряли в одном углу ящика и теперь там клубок. И если так уж невезёт, что ВСЕ элементы попадут в один бакет, то твоя красивая O(1) накрывается медным тазом и превращается в O(n). Придётся по цепочке в этом бакете всё перебирать. Удивление пиздец, но такое бывает.
• Рехеширование. Ещё один весёлый момент. У HashMap есть такой параметр — loadFactor (по умолчанию 0.75). Это как степень заполненности того самого ящика с носками. Когда он заполняется на 75%, системе терпения ноль ебать, и она говорит: "Всё, ящик мал, ёб твою мать!". Начинается рехеширование — создаётся новый, побольше ящик, и все старые носки-записи перекладываются туда заново. Эта операция уже O(n), потому что каждый элемент надо перенести. Нечасто, но когда случается — может подтормаживать.

Короче, суть: В 95% случаев ты просто кидаешь и забываешь — O(1). Но иногда эта структура данных может тебе такую хиросиму устроить, если ключи криво выбрал или данных овердохуища.

Вот, смотри, как это выглядит в коде, тут всё честно:

val map = HashMap<String, Int>()
map.put("key", 42)  // O(1) в среднем, но помни про коллизии и рехеш, чувак!

Вот и вся магия. Быстро, но не без сюрпризов, как в жизни.