Как в HashMap хранятся элементы с одинаковым hashcode

Хранение элементов с одинаковым hashcode в HashMap

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

Принцип работы при коллизиях

Когда два или более ключа имеют одинаковый hashCode(), они размещаются в одной и той же корзине (bucket) — ячейке внутреннего массива Node<K,V>[] table. Каждая корзина реализуется как связный список (в Java 8 и выше — с возможностью преобразования в сбалансированное дерево при определённых условиях).

Вот упрощённое представление структуры:

// Упрощённая структура Node внутри HashMap
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // Ссылка на следующий узел в цепочке
}

Процесс добавления элемента (put)

При вызове put(key, value):

1. Вычисляется хэш ключа: hash = hash(key) (дополнительное распространение хэша для уменьшения коллизий).
2. Определяется индекс корзины: index = (n - 1) & hash, где n — размер массива.
3. Если в корзине index уже есть элементы:
   • Происходит итерация по цепочке узлов.
   • Для каждого узла проверяется:

     - Совпадение хэша (`node.hash == hash`)
     - Совпадение ключа через `Objects.equals(node.key, key)`

• Если ключ найден — значение обновляется.
• Если ключ не найден — новый узел добавляется в начало цепочки (O(1) вставка).

Пример кода с коллизией:

HashMap<String, Integer> map = new HashMap<>();
// Два разных ключа с одинаковым хэш-кодом
map.put("Aa", 1);  // Хэш "Aa" = 2112
map.put("BB", 2);  // Хэш "BB" = 2112 (коллизия!)

// Внутри HashMap они попадут в одну корзину
// и будут связаны как цепочка: bucket[index] -> Node("BB",2) -> Node("Aa",1)

Поиск элемента (get)

При поиске по ключу с коллизирующим хэшем:

Integer value = map.get("BB");
// 1. Вычисляется hash("BB") = 2112
// 2. Определяется индекс корзины
// 3. Происходит линейный поиск по цепочке с проверкой equals() для каждого ключа
// 4. Найдя Node("BB",2), возвращается значение 2

Оптимизация в Java 8: преобразование в дерево

В Java 8 была введена важная оптимизация для борьбы с деградацией производительности при множественных коллизиях:

• Когда длина цепочки в корзине превышает TREEIFY_THRESHOLD (по умолчанию 8)
• И общее количество элементов в HashMap превышает MIN_TREEIFY_CAPACITY (64)
• Цепочка преобразуется в красно-чёрное дерево с балансировкой

// Преобразование происходит в TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // Красное дерево
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
}

Это преобразование снижает сложность поиска в корзине с коллизиями с O(n) до O(log n).

Ключевые моменты реализации

1. Равенство хэшей ≠ равенство объектов — коллизия хэш-кодов не означает, что ключи равны.
2. Определяющая роль equals() — окончательное сравнение ключей всегда через equals().
3. Инвариант: key1.equals(key2) → key1.hashCode() == key2.hashCode() (обратное не всегда верно).
4. Производительность сильно зависит от качества хэш-функции:
   • Идеальный случай: O(1) для всех операций
   • Худший случай (все ключи в одной корзине): O(n) или O(log n) с деревом

Пример плохого hashCode()

// Пример класса с ужасной хэш-функцией
class BadKey {
    private String value;
    
    @Override
    public int hashCode() {
        return 42; // Все экземпляры имеют одинаковый хэш!
    }
    
    @Override
    public boolean equals(Object o) {
        // Правильная реализация equals
    }
}

// Использование приведёт к вырождению HashMap в связный список
HashMap<BadKey, String> badMap = new HashMap<>();
for (int i = 0; i < 100; i++) {
    badMap.put(new BadKey("key" + i), "value" + i);
}
// Все 100 элементов окажутся в одной корзине

Рекомендации для разработчиков

• Всегда переопределяйте hashCode() вместе с equals().
• Стремитесь к равномерному распределению хэш-кодов.
• Избегайте мутабельных ключей в HashMap — изменение ключа после добавления нарушит работу.
• Имейте в виду capacity и load factor при создании HashMap для минимизации рехеширований.

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