Почему двусвязный список в HashMap всегда удается преобразовать в красно-черное дерево, даже если ключ не реализует Comparable

Красно-черное дерево — это самобалансирующееся бинарное дерево поиска, требующее возможности сравнивать элементы. HashMap решает эту задачу без требования Comparable через многоступенчатый алгоритм сравнения:

1. Сравниваются хэш-коды ключей. Если хэши разные — результат определен.
2. Если хэши равны и оба ключа реализуют Comparable — вызывается compareTo().
3. Если ключи не реализуют Comparable — используется метод tieBreakOrder():
   • Сравниваются имена классов ключей через getClass().getName().
   • Если классы одинаковые — сравниваются результаты System.identityHashCode().

System.identityHashCode() гарантирует уникальное (с высокой вероятностью) значение для каждого объекта, что обеспечивает детерминированный порядок в дереве, даже если ключи не реализуют Comparable.

На собеседовании: перечислите три шага алгоритма: сравнение хэшей -> compareTo() (если Comparable) -> tieBreakOrder() (имя класса, затем identityHashCode).