Какая сложность поиска в хэшмапе при использовании сбалансированного дерева вместо связного списка
Что проверяют
Понимаете ли вы, что происходит внутри бакета, и различаете ли среднюю и худшую сложность. Здесь легко ответить формально и провалиться на уточнении. Следом спрашивают, при каких условиях реализация вообще переходит на дерево, что она требует от ключей и зачем это было сделано.
Как отвечать
Главное сразу: средняя сложность поиска в хэш-таблице это O(1), и от способа разрешения коллизий она не зависит. Разница видна только в вырожденном случае, когда все ключи попали в один бакет:
- связный список в бакете: обход O(k), в худшем случае O(n);
- красно-чёрное дерево: O(log k), в худшем случае O(log n).
Java. С версии 8 HashMap превращает бакет в красно-чёрное дерево при TREEIFY_THRESHOLD = 8, но только когда таблица не меньше MIN_TREEIFY_CAPACITY = 64, иначе вместо дерева выполняется расширение таблицы. Обратно в список бакет разворачивается по UNTREEIFY_THRESHOLD = 6. Ключи внутри дерева сравниваются через Comparable, если тип его реализует, иначе по хэшу с запасным сравнением по System.identityHashCode. Смысл механизма не в ускорении обычной работы, а в защите от атаки подобранными коллизиями (HashDoS).
Go. В map ничего подобного нет: это открытая адресация, с версии 1.24 реализация построена на Swiss Tables. От вырождения защищает случайная затравка хэша на каждый запуск процесса, поэтому подобрать коллизии извне нельзя, а теоретический худший случай остаётся линейным.
Сильное завершение это цена решения. Узел дерева тяжелее звена списка по памяти, и на бакетах из двух-трёх элементов дерево медленнее. Пороги подобраны так, что при равномерной хэш-функции восемь элементов в одном бакете почти невероятны, то есть в норме дерево не строится никогда.
Где спотыкаются
Говорят, что дерево делает поиск O(log n) всегда. Обычная работа остаётся O(1), дерево это страховка на плохой случай.
Путают деревянизацию бакета с TreeMap. Второе это отдельная структура, где O(log n) на любой операции, зато ключи упорядочены и доступны firstKey, headMap и диапазоны.
Считают, что дерево спасёт от кривого equals/hashCode. При нарушенном контракте элемент теряется независимо от структуры бакета.