Какая сложность операций в HashMap, если hashCode ключа всегда возвращает одно и то же значение?

Сложность HashMap при плохом hashCode

Это важный вопрос о деградации производительности. Давайте разберёмся подробно.

Коротко: ответ O(n) или O(log n)

До Java 8: O(n) в худшем случае Java 8+: O(log n) в худшем случае

Пример проблемы

public class BadKey {
    private String value;
    
    @Override
    public int hashCode() {
        return 42;  // Всегда одно число!
    }
}

HashMap<BadKey, String> map = new HashMap<>();
for (int i = 0; i < 10000; i++) {
    map.put(new BadKey("key" + i), "value" + i);
}

// Поиск: нужно сравнить почти все 10000 элементов!
map.get(new BadKey("key5000"));  // O(5000) — медленно

Почему O(n)?

Все элементы с одинаковым hashCode попадают в один bucket:

До Java 8: bucket[42] → node1 → node2 → ... → node10000
Поиск = перебор LinkedList = O(n)

Java 8+ оптимизация

На Java 8+ это преобразуется в красно-чёрное дерево:

Java 8: bucket[42] → Red-Black Tree
        поиск в дереве = O(log n)

Нормальный случай

С хорошим hashCode: O(1) amortized

public class GoodKey {
    @Override
    public int hashCode() {
        return Objects.hash(value);  // Разные значения
    }
}

// Элементы распределяются по разным bucket'ам
// bucket[1] → node1
// bucket[5] → node2
// bucket[9] → node3
// поиск = O(1)

Таблица сложностей

Это главное улучшение в HashMap на Java 8!