Какая сложность доступа к элементу по ключу в HashMap

В среднем случае - O(1), но в худшем (при коллизиях) - O(n).

HashMap использует хеш-функцию для определения индекса корзины (bucket). При идеальном хешировании доступ к элементу происходит за константное время. Однако если много ключей попадают в одну корзину (коллизии), элементы хранятся как связный список (или дерево в Java 8+), и поиск становится линейным.

Пример:

val map = HashMap<String, Int>()
map["key"] = 42 // Вставка ~O(1)
val value = map["key"] // Получение ~O(1)

Для хорошей производительности важно:

1. Качественная хеш-функция
2. Равномерное распределение ключей
3. Подходящий capacity/loadFactor