Что такое коллизия в HashMap? Какова оптимистичная и пессимистичная сложность доступа?

Коллизия в HashMap — это ситуация, когда два разных ключа при хешировании дают одинаковый индекс (хеш-код), и оба пытаются занять одно и то же место в массиве.

В Java HashMap при коллизии элементы с одинаковым индексом хранятся в связном списке или, начиная с определённого размера, в сбалансированном дереве (TreeNode), чтобы ускорить поиск.

Сложность доступа:

• Оптимистичная (средняя) сложность: O(1) — при равномерном распределении хешей и небольшом количестве коллизий доступ к элементу происходит за константное время.

• Пессимистичная сложность: O(n) — в худшем случае, когда все ключи попадают в одну корзину (например, одинаковый хеш), поиск становится линейным по количеству элементов в этой корзине.

Современные реализации HashMap (начиная с Java 8) используют деревья для корзин с большим числом элементов, что снижает худший случай до O(log n).