IdentityHashCode в корзине HashMap

Question

В деталях реализации HashMap я могу прочитать:

When using comparators on insertion, to keep a
 * total ordering (or as close as is required here) across
 * rebalancings, we compare classes and identityHashCodes as
 * tie-breakers.

Если у меня есть константа hashCode и штраф equals, и мой класс не реализует Comparable, как именно эторазорвет связи и как будет построено дерево?

Я имею в виду - ведро преобразуется в дерево и будет использовать System.identityHashCode, чтобы разорвать связь.Затем я попытаюсь вызвать метод containsKey с другим экземпляром (который будет иметь те же hashCode и a.equals(b) == true), он будет иметь другой identityHashCode, поэтому возможно, что дерево будет пройдено не тем узлом (слева)вместо права) и он не найдет ключ?

Я что-то упустил или это нормальное поведение?

Answer 1

Мотивация разрыва связи базового хэш-кода идентифицируется прямо перед цитируемой частью:

HashMap.java, строка 212 :

* When bin lists are treeified, split, or untreeified, we keep 
* them in the same relative access/traversal order (i.e., field 
* Node.next) to better preserve locality, and to slightly 
* simplify handling of splits and traversals that invoke 
* iterator.remove. When using comparators on insertion, to keep a 
* total ordering (or as close as is required here) across 
* rebalancings, we compare classes and identityHashCodes as 
* tie-breakers. 

Итак, упорядочение по хэш-коду идентичности обеспечивает стабильное упорядочение, помогающее реализовать разбиение и операцию Iterator.remove() (которая должна поддерживать последовательное продолжение прохождения).

Как объяснено в этого ответа, он не используется для операций поиска, как вы уже сказали в своем вопросе, два одинаковых объекта могут иметь разные идентификационные коды.Поэтому для неравных объектов, имеющих одинаковый хэш-код и не реализующих Comparable, невозможно обойти их все и исследовать с помощью equals.

Answer 2

Нет, вы действительно перемещаете записи влево или вправо на основе System::identityHashCode, но в этом сегменте есть записи все еще , которые имеют одинаковый hashCode (ну, не то же самое, только часть, которая имеет значение).

Так что, когда вы ищете что-то, иногда нужно взглянуть и на left, и на right, так как это просто невозможно.

Answer 3

Во время вставки контейнер будет использовать identityHashCode, но при поиске используются только хэш-коды и вызовы compare() (если доступны).Это означает, что иногда требуется сканировать оба поддерева узла.

Логика поиска выглядит так:

do {
  if (... keys are equal or can be compared ...) {
    // Go left, right or return the current node
    ...
  } else if ((q = pr.find(h, k, kc)) != null)
    // Search the right subtree recursively
    return q;
  else
   // Go to the left subtree
   p = pl;
} while (p != null);

См. http://hg.openjdk.java.net/jdk10/jdk10/jdk/file/ffa11326afd5/src/java.base/share/classes/java/util/HashMap.java#l1901 и обратите внимание, что tieBreakOrder() (методответственный за сравнение identityHashCode s нигде не вызывается в find().