Представим 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;
}
....
}
Хэш-функция: Как ключи находят свои комнаты
Представьте себе, что HashMap — это огромный замок с множеством комнат. Каждая комната имеет уникальный номер, но как ключи решают, в какую именно комнату им идти? Это задача хэш-функции, магического инструмента, который помогает определять, в какой бакет (комнату) будет помещен тот или иной ключ.
Когда мы добавляем ключ, метод 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"));
}
}
В результате каждый ключ проходит через хэш-функцию и попадает в свою уникальную комнату, индекс которой вычисляется с помощью побитового И.
Проверка на коллизии: Если бакет пуст, добавляется новая пара "ключ-значение". Если нет, 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);
}
}
В этом примере класс 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);
Для всех ключей значениеhashCode() будет 42, поэтому каждый раз, когда ключ добавляется, индекс бакета в table будет один и тот же.
Но вместо того чтобы столкнуться лбами, ключи открывают дополнительные двери, превращая комнату в магический коридор, который ведет к новым комнатам. Эти новые комнаты — это, по сути, способы решения коллизий .
Связанные списки: Когда два ключа с одинаковыми хэш-кодами попадают в один бакет, HashMap создает в этом бакете связанный список. Каждая Node соединена со следующей в одном бакете .Ключи продолжают храниться в этом списке, и если нужно, то проводится проверка с помощью метода equals(), чтобы удостовериться, что ключи действительно одинаковы.
Эти списки автоматически превращаются в сбалансированное двоичное дерево, если в бакете накапливается более восьми элементов.
Красно-черные деревья: Когда количество коллизий в одном бакете становится слишком высоким (коридор становится слишком длинным), HashMap преобразует его в красно-черное дерево. Это помогает ускорить поиск и предотвратить замедление работы с большой нагрузкой.
Как работает equals() и hashCode()
Для правильной работы магии HashMap важно, чтобы два одинаковых ключа с одинаковым значением возвращали одинаковые хэш-коды, а также правильно сравнивались с помощью метода equals(). Это как заклинание, которое проверяет, являются ли два объекта одинаковыми, даже если они могут быть представлены разными способами.
hashCode(): Каждый объект должен иметь свой уникальный хэш-код. Это позволяет HashMap эффективно находить бакет, куда нужно поместить ключ.
equals(): Если два объекта имеют одинаковый хэш-код, метод equals() проверяет, действительно ли эти объекты одинаковы.
Если бы не было этой проверки, HashMap мог бы перепутать два разных ключа, что привело бы к некорректному поведению программы.
Заключение
Мир HashMap — это мир магии, где хэш-функции и коллизии помогают ключам находить свои комнаты и сохранять порядок в замке. Каждый ключ имеет свой путь, ведущий к уникальному индексу, благодаря хэш-функции. И когда два ключа сталкиваются в одном бакете, магия продолжает работать, открывая новые двери в виде связанных списков или красно-черных деревьев, чтобы найти нужный путь.
Таким образом, благодаря hashCode(), equals() и магическим коридорам коллизий, HashMap продолжает оставаться одним из самых мощных инструментов в арсенале Java-разработчиков, гарантируя эффективность и точность даже в самых запутанных ситуациях.
Top comments (0)