DEV Community

Cover image for HashMap: тайные комнаты, магия и коллизии
Olga Lugacheva
Olga Lugacheva

Posted on

HashMap: тайные комнаты, магия и коллизии

Представим HashMap как замок с тайными комнатами (бакетами), где каждую комнату предворяют волшебные двери - хэш-функции. Как же работает этот механизм и что происходит, когда две магические сущности сталкиваются в одном месте? Давайте погрузимся в тайный мир HashMap. Для начала рассмотрим, из чего HashMap состоит.

Основные Компоненты HashMap

Массив table: Этот массив является основным хранилищем данных. Каждая ячейка массива (или бакет) содержит уникальный индекс, где могут храниться цепочки значений или даже двоичное дерево в случае большого количества элементов.

Коэффициент загрузки (loadFactor): LoadFactor указывает, насколько можно заполнить HashMap до его расширения. По умолчанию коэффициент загрузки составляет 0.75, что обеспечивает баланс между экономией памяти и скоростью доступа. Когда HashMap заполняется на 75%, он удваивает размер table и перераспределяет элементы для поддержания эффективности.

Пороговое значение (threshold): Порог — это точка, при достижении которой HashMap решает расширить table. Рассчитывается как(capacity * loadFactor). Например, если capacityравно 16 и loadFactor— 0.75, то thresholdбудет 12. Когда HashMap достигает 12 элементов, он увеличивает свой размер.

Размер size отслеживает текущее количество пар ключ-значение в HashMap.

Каждая пара "ключ-значение" в HashMap хранится в структуре, называемой Node, содержащей:

key — ключ пары,
value— значение пары,
hash — хэш, рассчитанный на основе hashCode() ключа,
next — ссылка на следующий элемент в цепочке при коллизиях.

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;

    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    ....
}
Enter fullscreen mode Exit fullscreen mode

Хэш-функция: Как ключи находят свои комнаты

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

diag 3
Когда мы добавляем ключ, метод putVal, вызываемый внтури метода put вызывает метод hashCode() ключа, чтобы создать хэш, который затем дорабатывается для равномерного распределения по бакетам.
Вычисление индекса: Используя формулу int index = hashCode & (length- 1) , HashMap рассчитывает индекс, который указывает на бакет в массиве table.

Здесь hashCode— это уникальный код, который ключ получает через хэш-функцию. После этого мы выполняем операцию побитового И с числом length - 1. Это эквивалентно вычислению остатка от деления хэш-кода на количество бакетов, и таким образом мы определяем индекс в массиве бакетов.

import java.util.HashMap;

public class MagicalHashMap {
    public static void main(String[] args) {
        // Создаем новый HashMap
        HashMap<String, String> rooms = new HashMap<>();

        // Добавляем элементы в HashMap
        rooms.put("apple", "A room full of apples");
        rooms.put("banana", "A room full of bananas");

        // Поиск по ключу
        System.out.println("Room for 'apple': " + rooms.get("apple"));
        System.out.println("Room for 'banana': " + rooms.get("banana"));
    }
}
Enter fullscreen mode Exit fullscreen mode

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

diag1
Проверка на коллизии: Если бакет пуст, добавляется новая пара "ключ-значение". Если нет, putVal проверяет, совпадает ли ключ:

Совпадает — обновляется значение.
Не совпадает — возникает коллизия - про них дальше.

Коллизии: Тайные комнаты, открывающиеся одна в другую

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

class KeyWithSameHash {
    private String key;

    public KeyWithSameHash(String key) {
        this.key = key;
    }

    @Override
    public int hashCode() {
        return 42; // Возвращаем одинаковое значение для всех ключей
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        KeyWithSameHash other = (KeyWithSameHash) obj;
        return Objects.equals(key, other.key);
    }
}

Enter fullscreen mode Exit fullscreen mode

В этом примере класс KeyWithSameHashимеет переопределённый метод hashCode(), возвращающий одинаковое значение для всех экземпляров, что заставляет все ключи попадать в одну и ту же ячейку массива table:

Map<KeyWithSameHash, Integer> map = new HashMap<>();
map.put(new KeyWithSameHash("key1"), 1);
map.put(new KeyWithSameHash("key2"), 2);
map.put(new KeyWithSameHash("key3"), 3);
Enter fullscreen mode Exit fullscreen mode

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

Но вместо того чтобы столкнуться лбами, ключи открывают дополнительные двери, превращая комнату в магический коридор, который ведет к новым комнатам. Эти новые комнаты — это, по сути, способы решения коллизий .

Infinite cor
Связанные списки: Когда два ключа с одинаковыми хэш-кодами попадают в один бакет, HashMap создает в этом бакете связанный список. Каждая Node соединена со следующей в одном бакете .Ключи продолжают храниться в этом списке, и если нужно, то проводится проверка с помощью метода equals(), чтобы удостовериться, что ключи действительно одинаковы.

diag2
Эти списки автоматически превращаются в сбалансированное двоичное дерево, если в бакете накапливается более восьми элементов.

Красно-черные деревья: Когда количество коллизий в одном бакете становится слишком высоким (коридор становится слишком длинным), HashMap преобразует его в красно-черное дерево. Это помогает ускорить поиск и предотвратить замедление работы с большой нагрузкой.

RBT

Как работает equals() и hashCode()

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

keys

hashCode(): Каждый объект должен иметь свой уникальный хэш-код. Это позволяет HashMap эффективно находить бакет, куда нужно поместить ключ.
equals(): Если два объекта имеют одинаковый хэш-код, метод equals() проверяет, действительно ли эти объекты одинаковы.
Если бы не было этой проверки, HashMap мог бы перепутать два разных ключа, что привело бы к некорректному поведению программы.

Заключение

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

Таким образом, благодаря hashCode(), equals() и магическим коридорам коллизий, HashMap продолжает оставаться одним из самых мощных инструментов в арсенале Java-разработчиков, гарантируя эффективность и точность даже в самых запутанных ситуациях.

Top comments (0)