Какой самый худший случай работы HashMap с точки зрения вычислительной сложности?

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

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

Пример:

Map<Integer, String> map = new HashMap<>();
// Если все ключи имеют одинаковый hashCode, например, объекты с переопределённым hashCode
class BadKey {
    int value;
    BadKey(int v) { value = v; }
    @Override
    public int hashCode() { return 1; } // все ключи попадают в одну корзину
    @Override
    public boolean equals(Object o) { return o instanceof BadKey && ((BadKey)o).value == this.value; }
}

for (int i = 0; i < 1000; i++) {
    map.put(new BadKey(i), "Value" + i);
}
// Поиск будет работать медленно, так как все элементы в одной корзине

Таким образом, важно выбирать хорошую функцию хэширования и избегать коллизий.