Встречается на 2% собеседований по Java

Какая сложность доступа к элементу в HashMap в случае красно-черного дерева

В худшем случае O(log n), так как при коллизиях (когда несколько ключей попадают в одну корзину) HashMap в Java 8+ использует сбалансированное красно-черное дерево вместо связного списка. В среднем случае доступ остается O(1), если коллизий мало.

Пример:

java
Map<Integer, String> map = new HashMap<>();
map.put(1, "a"); 
map.put(2, "b"); // Обычный доступ O(1)

// При коллизиях (ключи с одинаковым хэшем):
for(int i = 0; i < 10000; i++) {
    map.put(i, "val"+i); 
}
// В этом случае доступ к элементу потребует O(log n) операций
Sophi
Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
Попробовать бесплатноArrow

Следующий вопрос

Это единственный вопрос по вашему фильтру

как отвечать на вопрос
пример собеседования
фреймворки на собеседовании
типичные вопросы junior
интервью вопросы и ответы