Что происходит при коллизиях в HashMap и почему используется красно-черное дерево
Что проверяют
Знаете ли вы устройство HashMap глубже, чем «ключ, значение, O(1)», и понимаете ли, от какой проблемы защищает дерево и почему оно включается не сразу. Следом часто спрашивают про контракт equals и hashCode или про порог 8.
Как отвечать
Индекс корзины считается так: старшие 16 бит hashCode() смешиваются с младшими (h ^ (h >>> 16)), затем берётся (n - 1) & hash, где n это размер таблицы, всегда степень двойки. Коллизия это два ключа в одной корзине. Узлы выстраиваются в односвязный список, новый добавляется в хвост, поиск идёт по списку со сравнением хэша и equals().
С Java 8 (JEP 180) список может превратиться в красно-чёрное дерево:
TREEIFY_THRESHOLD = 8: преобразование срабатывает, когда цепочка перерастает 8 узлов;MIN_TREEIFY_CAPACITY = 64: но только если в таблице не меньше 64 корзин. Иначе таблица просто увеличивается вдвое, и элементы разъезжаются;UNTREEIFY_THRESHOLD = 6: при расширении таблицы дерево, где осталось 6 узлов или меньше, снова становится списком.
Зачем дерево: при нормальном хэше и loadFactor 0.75 длина цепочки подчиняется распределению Пуассона, и 8 элементов в одной корзине почти невероятны. Если это случилось, хэш плохой или кто-то специально подбирает ключи с одинаковым хэшем (hash flooding через параметры запроса). Список даёт O(n) на операцию, дерево O(log n).
Почему красно-чёрное: баланс слабее, чем у AVL, зато вставка и удаление требуют меньше поворотов. Узлы упорядочены по хэшу, а при равенстве по compareTo(), если ключи Comparable.
Где спотыкаются
Путают порог 64 с количеством элементов. Это число корзин, то есть ёмкость таблицы, а не size().
Утверждают, что дерево экономит память. Наоборот, TreeNode примерно вдвое тяжелее Node, поэтому дерево и включается только в крайнем случае.
Не знают, что для ключей без Comparable с одинаковым хэшем дерево спасает не полностью: упорядочить их не по чему, и поиск может обходить оба поддерева. Отсюда совет делать ключи Comparable.