Как сравниваются ключи в HashMap при одинаковом hashCode

В HashMap в Java ключи сравниваются следующим образом, даже если у них одинаковый hashCode:

  1. Использование equals для проверки эквивалентности: В HashMap ключи с одинаковым hashCode группируются в одно "ведро" (bucket). Когда два или более ключа имеют одинаковый hashCode, HashMap использует метод equals для проверки, являются ли ключи эквивалентными.

  2. Список или дерево в ведре: Если в ведре находятся несколько элементов с одинаковым hashCode, они хранятся в виде связного списка или, начиная с Java 8, в виде сбалансированного дерева (если количество элементов в ведре превышает определённый порог).

    • До Java 8: Ведро представляет собой связный список. Если два ключа имеют одинаковый hashCode, то они будут размещены в этом списке, и метод equals используется для нахождения нужного ключа.

    • Java 8 и позже: Если количество элементов в ведре превышает определённый порог (обычно 8), связный список преобразуется в сбалансированное дерево (TreeNode). В этом случае поиск по ключу также выполняется с использованием equals, но дерево обеспечивает логарифмическое время поиска по сравнению с линейным временем для списка.

Map<MyKey, String> map = new HashMap<>();
MyKey key1 = new MyKey(1); // hashCode = 42
MyKey key2 = new MyKey(2); // hashCode = 42

map.put(key1, "Value1");
map.put(key2, "Value2");

// Здесь метод `equals` используется для определения, является ли key2 тем же ключом, что и key1.

В этом примере key1 и key2 имеют одинаковый hashCode, поэтому они попадают в одно и то же ведро в HashMap. Метод equals будет вызван для сравнения key1 и key2, чтобы определить, нужно ли обновить существующую запись или добавить новую.