HashMap — это одна из самых популярных структур данных в Java, которая реализует интерфейс Map и хранит данные в виде пар "ключ-значение". Она обеспечивает быстрый доступ к элементам по ключу, но для эффективной работы важно понимать, как она устроена внутри, что такое коллизии и как они разрешаются.
HashMap использует массив (обычно называемый "корзины" или "buckets") для хранения элементов. Каждый элемент (пара "ключ-значение") хранится в виде объекта Node, который содержит:
static class Node<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next; // Ссылка на следующий узел в случае коллизии
}
Когда вы добавляете элемент в HashMap, сначала вычисляется хэш-код ключа с помощью метода hashCode(). Этот хэш-код используется для определения индекса корзины (bucket), в которую будет помещен элемент.
int index = (n - 1) & hash; // n - размер массива корзин
Где:
n — размер массива корзин (всегда степень двойки).hash — хэш-код ключа.Коллизия возникает, когда два разных ключа имеют одинаковый хэш-код и, следовательно, попадают в одну и ту же корзину. В HashMap коллизии разрешаются с помощью метода цепочки (chaining).
Если в одну корзину попадает несколько элементов, они хранятся в виде связанного списка (или дерева, если список становится слишком большим). Каждый узел списка содержит ссылку на следующий узел.
if (currentNode != null) {
if (currentNode.key.equals(key)) {
// Замена значения, если ключ совпадает
currentNode.value = value;
} else {
// Добавление нового узла в конец списка
while (currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
} else {
// Если корзина пуста, добавляем новый узел
table[index] = newNode;
}
Когда количество элементов в HashMap превышает определенный порог (определяется коэффициентом загрузки, loadFactor), размер массива корзин увеличивается вдвое, и все элементы перераспределяются по новым корзинам. Это называется рехэшированием.
if (size > threshold) {
resize();
}
Коэффициент загрузки по умолчанию равен 0.75, что обеспечивает баланс между использованием памяти и производительностью.
Коллизия — это ситуация, когда два или более ключа имеют одинаковый хэш-код и попадают в одну и ту же корзину. Это может произойти, даже если хэш-коды разные, но приводят к одному индексу в массиве корзин.
HashMap<String, Integer> map = new HashMap<>();
map.put("a", 1); // Хэш "a" может быть равен 97
map.put("b", 2); // Хэш "b" может быть равен 98, но индекс корзины совпадает
Как уже упоминалось, HashMap использует метод цепочки для разрешения коллизий. Если несколько ключей попадают в одну корзину, они хранятся в виде связанного списка. В Java 8, если список становится слишком большим (обычно больше 8 элементов), он преобразуется в сбалансированное дерево (красно-черное дерево) для улучшения производительности.
if (binCount >= TREEIFY_THRESHOLD - 1) {
treeifyBin(tab, hash);
}
В Java используется дополнительное преобразование хэш-кода для уменьшения вероятности коллизий:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Этот метод "смешивает" старшие и младшие биты хэш-кода, чтобы уменьшить вероятность коллизий.
При увеличении размера массива корзин все элементы перераспределяются по новым корзинам, что также помогает уменьшить количество коллизий.
HashMap использует массив корзин для хранения элементов, где каждая корзина может содержать связанный список или дерево.HashMap и механизмов разрешения коллизий помогает писать более эффективный и надежный код.