Представим 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)