Каково наихудшее (worst-case) время выполнения операции get() в HashMap?

В наихудшем случае время выполнения операции get() (или put()) в HashMap деградирует до O(n), где n — количество элементов в мапе.

Причина: Это происходит при сильных коллизиях хэш-кодов, когда все или большинство ключей попадают в одну и ту же корзину (bucket). Внутри корзины элементы хранятся либо как связный список (до Java 8), либо как сбалансированное дерево (начиная с Java 8 при превышении порога).

Сценарий worst-case:

1. Плохая хэш-функция: Возвращает одинаковый или сводящийся к одному индексу хэш для всех ключей.
2. Атака HashDoS: Злоумышленник может специально подобрать ключи, вызывающие коллизии, чтобы замедлить работу структуры данных.

Пример плохого ключа (упрощенно):

class BadKey {
    @Override
    public int hashCode() {
        return 1; // Все экземпляры имеют одинаковый хэш
    }
}

HashMap<BadKey, String> map = new HashMap<>();
map.put(new BadKey(), "a");
map.put(new BadKey(), "b");
// Все элементы попадут в одну корзину.
// Операция get() будет выполнять линейный поиск по списку/дереву.

Как Java 8+ смягчает проблему: При большом количестве коллизий в одной корзине (превышение TREEIFY_THRESHOLD = 8) связный список преобразуется в красно-черное дерево. Это улучшает worst-case производительность с O(n) до O(log n) для операций поиска в этой корзине.

Вывод: Теоретический worst-case — O(n), но на практике, с качественной hashCode() и после Java 8, вероятность и влияние такого сценария значительно снижены.