Как Java 8 HashMap вырождается в сбалансированные деревья, когда многие ключи имеют один и тот же хэш-код?

Ответ 1

Комментарий примечания по реализации в HashMap - лучшее описание операции HashMap, чем я мог написать сам. Соответствующие части для понимания узлов дерева и их упорядочения:

Эта карта обычно выступает как хэш-таблица с биндером (bucketed), но когда ячейки становятся слишком большими, они преобразуются в бункеры TreeNodes, каждый из которых структурирован аналогично таковым в java.util.TreeMap. [...] Буферы TreeNodes могут проходить и использоваться как любые другие, но дополнительно поддерживать быстрый поиск при перенаселении. [...]

Ячейки деревьев (т.е. бины, чьи элементы представляют собой все TreeNodes) упорядочиваются в основном с помощью hashCode, но в случае связей, если два элемента имеют один и тот же тип класса C реализует Comparable, тогда их метод compareTo используется для упорядочения, (Мы консервативно проверяем общие типы посредством отражения, чтобы проверить это - см. Метод compareClassFor). Добавленная сложность древовидных дворов имеет смысл при обеспечении операций O (log n) в худшем случае, когда ключи либо имеют разные хэши, либо упорядочиваются. Таким образом, производительность изящно снижается при случайных или злонамеренных использованиях, в которых методы hashCode() возвращают значения, которые плохо распределенные, а также те, в которых многие ключи используют хэш-код, если они также являются сопоставимыми. (Если ни одно из них не применимо, мы можем потерять около двух раз во времени и пространстве по сравнению с принятием каких-либо мер предосторожности. Но единственные известные случаи связаны с плохими практиками программирования пользователей, которые уже настолько медленны, что это мало чем отличается.)

Если два объекта имеют одинаковые хеш-коды, но не взаимно сопоставимы, метод tieBreakOrder вызывается для разрыва связи, сначала путем сравнения строк на getClass().getName() (!), то, сравнивая System.identityHashCode.

Фактическое построение дерева начинается в treeifyBin, начиная с того момента, когда бит достигает TREEIFY_THRESHOLD ( в настоящее время 8), если хэш-таблица имеет как минимум MIN_TREEIFY_CAPACITY емкость (в настоящее время 64). Это обычная реализация красно-черного дерева (CLR кредитования), с некоторыми осложнениями для поддержки обхода так же, как и хэш-бины (например, removeTreeNode).

Ответ 2

Прочитайте code. Это главным образом красно-черное дерево.

Это фактически не требует реализации Comparable, но может использовать его, если доступно (см., например, метод )

Ответ 3

HashMap имеет собственный хэш-метод, который применяет дополнительный 2-х битный хэш к объектам внутри, чтобы избежать этих проблем:

Применяет дополнительную хэш-функцию к заданному хэш-коду, который защищает от хеш-функций низкого качества. Это важно, потому что HashMap использует хэш-таблицы с длиной в две строки, которые в противном случае сталкиваются с конфликтами для хэш-кодов, которые не отличаются в младших битах. Примечание. Нулевые ключи всегда отображают хэш 0, таким образом, индекс 0.

Если вы хотите посмотреть, как это сделать, посмотрите в источник класса HashMap.

static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}