Древовидные бункеры: использование identityHashCode для заказа несопоставимых компонентов делает эти усилия бесполезными?

Question

Почти расширение IdentityHashCode в корзине HashMap :

Я понимаю, что бины дерева в реализации Java 8 HashMap рекламируются, чтобы уменьшить сложность поиска в худшем случае до O (lg (n)) вместо O (n), например, для больших бункеров. Но для несопоставимых классов они используют identityHashCode для упорядочения вставки. Следовательно, когда find ing, нам нужно искать в обоих поддеревьях.

Теперь поиск в обоих поддеревах мгновенно преобразует сложность наихудшего случая: O (n) вместо O (lg (n)). Таким образом, вся тяжелая работа по преобразованию в деревья и возвращению без дерева при UNTREEIFY_THRESHOLD напрасна, и мы не получаем никакого преимущества?

Чего мне не хватает?

Answer 1

Для несопоставимых деревьев за корзиной используется преимущество более быстрого поиска объектов с различными hashCode() значениями, которые сопоставлены с одной и той же корзиной.

Для объектов с то же самое значение hashCode(), с этим ничего нельзя поделать, поскольку нет отличительных характеристик c. Система должна выполнить полный поиск всех ключей с одинаковым значением hashCode().

Как сказано в связанном вопросе, identityHashCodes используются только как t ie -разрушители во время вставки. Его нельзя использовать во время поиска, потому что поиск с помощью другого объекта (т. Е. Разные identityHashCodes) с одинаковым содержимым должен найти совпадение, как определено hashCode() и equals().