HashMap: почему get() — не всегда O(1)

Какая сложность HashMap.get()

?
Обычный ответ:
O(1).

Но это немного упрощённая версия.
Посмотрим, что происходит внутри:

Map<String, Integer> map = new HashMap<>();

map.put("Java", 10);
map.put("Kafka", 20);

Integer value = map.get("Java");
Упрощённо:

key
↓
hashCode()
↓
hash
↓
bucket
↓
поиск элемента
И вот последний шаг важен.

В одном bucket может оказаться несколько ключей:
bucket[5]

├── Entry("Java", 10)
├── Entry("Kafka", 20)
└── Entry("Spring", 30)
Поэтому HashMap сначала определяет bucket, а потом ищет нужный ключ внутри него. Если ключи распределены хорошо — элементов в bucket мало и поиск близок к O(1).

Но если много ключей попало в один bucket: bucket[5]

├── key1
├── key2
├── key3
├── key4
├── key5
└── ...
поиск становится дороже. А что будет при плохом hashCode?

Например:

class UserKey {

private final Long id;

@Override
public int hashCode() {
return 1;
}

@Override
public boolean equals(Object o) {
// ...
}
}

Все объекты получают одинаковый hash.
В результате:
UserKey #1 ─┐
UserKey #2 ─┤
UserKey #3 ─┼──→ один bucket
UserKey #4 ─┤
UserKey #5 ─┘
То есть HashMap теряет главное преимущество хорошего распределения хэшей.

Но Java здесь предусмотрела защиту
В современных реализациях HashMap, когда в одном bucket становится слишком много элементов, структура bucket при определённых условиях может преобразоваться из связного списка в красно-чёрное дерево.
Получаем: мало коллизий

bucket
↓
список


много коллизий

bucket
↓
красно-чёрное дерево
Поэтому при большом количестве коллизий поиск может быть не O(n), а порядка O(log n) после treeification.

Но есть важный нюанс:
это не означает, что HashMap.get() всегда O(log n).

В среднем при нормальном распределении хэшей ожидаемая сложность остаётся близкой к O(1).


И ещё один вопрос: почему нельзя переопределить только equals()?
Потому что контракт требует:

a.equals(b) == true
↓
a.hashCode() == b.hashCode()
Если это нарушить:

Map<UserKey, String> map = new HashMap<>();

map.put(key1, "User");

map.get(key2);
даже если: key1.equals(key2) == true
HashMap может искать key2 в другом bucket.
И получим:

put(key1)
↓
hashCode(key1)
↓
bucket #5


get(key2)
↓
hashCode(key2)
↓
bucket #17
Ключи логически равны, а значение не находится.


Что стоит запомнить:
HashMap.get() — это не магический O(1).
Сначала вычисляется hash и определяется bucket, затем внутри bucket ищется ключ через equals().
Поэтому корректный ответ Senior

:
В среднем get() — O(1) при хорошем распределении хэшей. При коллизиях поиск внутри bucket усложняется; в современных Java при treeification длинный bucket может быть преобразован в красно-чёрное дерево