Какая сложность операций в HashMap при использовании дерева

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

Сложность операций:

• В среднем случае (без коллизий): O(1)
• В худшем случае (все элементы в одном бакете):
  • До Java 8: O(n) (список)
  • Java 8+: O(log n) (дерево)

Пример:

Map<Integer, String> map = new HashMap<>();
// Вставка: O(1) в среднем, O(log n) при коллизиях
map.put(1, "a"); 
// Поиск: O(1) в среднем, O(log n) при коллизиях
String value = map.get(1);