Почему бакет в хэшмапе перерастает в красно-черное дерево

Что проверяют

Заглядывали ли вы в исходники HashMap, а не только в пересказ про «массив списков». На Android-собеседованиях этим вопросом проверяют, отличаете ли вы средний случай от худшего.

Как отвечать

Бакет это ячейка внутреннего массива. Ключи с разными хэшами попадают в одну ячейку, потому что индекс берётся по младшим битам хэша, и такие ключи выстраиваются в односвязный список. Поиск по списку линейный, и при плохой хэш-функции карта из почти константной превращается в O(n).

Начиная с Java 8 длинный бакет перестраивается в красно-чёрное дерево, и поиск становится O(log n) в худшем случае. Пороги заданы константами:

• TREEIFY_THRESHOLD равен 8: столько узлов должно накопиться в одном бакете;
• MIN_TREEIFY_CAPACITY равен 64: если таблица меньше, вместо дерева выполняется расширение, потому что в тесной таблице длинные бакеты это следствие нехватки ячеек, а не плохих хэшей;
• UNTREEIFY_THRESHOLD равен 6: при перехэшировании дерево разворачивается обратно в список. Пороги на вход и выход различаются, чтобы структура не переключалась туда-сюда возле границы.

Полезно назвать настоящую причину: это защита от деградации на враждебных данных. Ключи, приходящие снаружи (параметры запроса, поля JSON), подбираются так, чтобы все легли в один бакет, и линейный поиск превращается в отказ в обслуживании. Внутри дерева узлы сравниваются по хэшу, затем через compareTo, если ключ реализует Comparable, а иначе применяется запасной порядок по имени класса и системному хэшу.

Где спотыкаются

Называют один порог 8 и забывают про ёмкость 64. Из-за этого уверены, что дерево появляется в любой маленькой карте, хотя там сначала произойдёт расширение массива.

Второе: говорят «O(log n) в среднем». У красно-чёрного дерева это оценка худшего случая, в том и смысл балансировки, а в среднем карта по-прежнему работает за константу.

Третье: считают перестроение поводом не писать hashCode. Дерево спасает от катастрофы, но хороший хэш не заменяет: сравнения объектов остаются дорогими, а узел дерева занимает больше памяти, чем элемент списка.