Как работает под капотом HashMap
Под капотом HashMap представляет собой структуру данных, основанных на массиве корзин и цепочках (связанных списках) для решения коллизий.
Пары ключ-значение: HashMap представляет собой коллекцию, в которой каждый элемент представлен в виде пары "ключ-значение".
Быстрый доступ к элементам по ключу: Время доступа к элементу в HashMap практически постоянное (O(1)), что делает его очень эффективным для операций поиска и доступа.
Уникальные ключи: Каждый ключ в HashMap должен быть уникальным. Если ключ уже существует в HashMap, его значение перезаписывается новым значением.
Нет гарантии порядка элементов: Порядок элементов в HashMap не гарантирован и может изменяться в зависимости от реализации и операций над ним.
Когда требуется быстрый доступ к данным по ключу: Если вам нужно быстро получать доступ к данным по их уникальному идентификатору (ключу), то HashMap будет хорошим выбором.
Когда нужно хранить данные в виде пар "ключ-значение": Когда вам нужно хранить данные в виде связей между уникальными ключами и соответствующими значениями, HashMap обеспечивает удобную структуру для этого.
Хеширование. Каждый ключ в HashMap проходит через функцию хеширования, которая преобразует его в целое число (хеш-код). Затем это число используется для вычисления индекса массива, в который будет помещено значение.
Хеш-таблица. Внутренне HashMap использует массив для хранения пар ключ-значение. Каждой паре присваивается индекс, соответствующий хеш-коду ключа (после некоторой нормализации).
Решение коллизий. Коллизии возникают, когда два разных ключа имеют одинаковый хеш-код. HashMap решает эту проблему с помощью связанных списков (раньше) или красно-чёрных деревьев (в более поздних версиях). Если несколько ключей имеют один и тот же хеш-код, они помещаются в один бакет в виде списка. Когда количество элементов в бакете превышает определённый порог, список превращается в красно-чёрное дерево для улучшения производительности.
Вставка. Для вставки пары ключ-значение:
Поиск. Для поиска элемента по ключу:
Удаление. Удаление происходит по тому же принципу: сначала вычисляется хеш-код, затем определяется бакет, и выполняется поиск в этом бакете для удаления элемента.
hashCode() у объекта ключа. Этот метод возвращает целое число (хеш-код), которое может быть как положительным, так и отрицательным. HashMap может дополнительно модифицировать хеш-код. Например, в Java 8 применяется метод сдвига и XOR, чтобы уменьшить риск возникновения коллизий:static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
AND) с размером массива минус 1 (например, если размер массива 16, то используется 15):int bucketIndex = (n - 1) & hash;
val bucketIndex = (table.size - 1) and hashCode
Операция and — это побитовое И, которое эффективно вычисляет остаток от деления на мощность двойки. Это очень эффективно, поскольку побитовые операции выполняются быстрее, чем деление.
Если рассматривать более простой пример с вычислением остатка от деления, то формула следующая
val bucketIndex = (hashCode % numberOfBuckets + numberOfBuckets) % numberOfBuckets
"apple" и её хеш-код:val key = "apple"
val hashCode = key.hashCode() // Пусть это 93029210
HashMap — 16. Тогда побитовая операция and выглядит так:val bucketIndex = (16 - 1) and hashCode // (15) and (93029210)
Побитовое И между 15 и хеш-кодом вернёт индекс в диапазоне от 0 до 15 (это размер массива бакетов):
val bucketIndex = 93029210 and 15 // bucketIndex может быть, например, 10
Полученное значение bucketIndex указывает на индекс корзины (бакета), куда будет помещён элемент.
Операция (n - 1) & hash используется вместо деления по модулю, потому что она работает быстрее и эффективнее, когда размер массива — это степень двойки (например, 16, 32, 64 и т. д.). Это даёт оптимальное распределение и минимизирует риск возникновения коллизий.
Если два разных ключа возвращают одинаковый индекс бакета (например, если их хеш-коды при выполнении операции AND дают одно и то же значение), это называется коллизией. Чтобы решить эту проблему, в одном бакете элементы хранятся либо в виде связного списка, либо, начиная с Java 8, в виде сбалансированного красно-чёрного дерева, если коллизий слишком много.
Коллизии в HashMap возникают, когда два разных ключа имеют одинаковый хеш-код (или когда их хеш-коды после вычисления индекса указывают на один и тот же бакет). Для обработки коллизий в HashMap используются различные механизмы в зависимости от версии Java. Рассмотрим их более подробно.
HashMap.HashMap, когда она заполняется до определённого порога.В ранних версиях Java (до Java 8) для обработки коллизий использовались связные списки. Если два разных ключа попадают в один и тот же бакет, HashMap хранит их в виде связного списка внутри этого бакета. Когда происходит коллизия, новый элемент добавляется в начало или конец списка. При этом структура данных для бакета выглядит как цепочка элементов, связанных друг с другом:
// Псевдокод на Kotlin, иллюстрирующий коллизии с использованием связного списка
class HashMapNode<K, V>(val key: K, var value: V, var next: HashMapNode<K, V>? = null)
class HashMap<K, V>(val size: Int) {
private val table = Array<HashMapNode<K, V>?>(size) { null }
fun put(key: K, value: V) {
val hashCode = key.hashCode()
val index = (size - 1) and hashCode
var current = table[index]
// Если бакет пуст, просто добавляем элемент
if (current == null) {
table[index] = HashMapNode(key, value)
} else {
// Если есть коллизия, проходим по связному списку
while (current != null) {
if (current.key == key) {
// Если ключ уже существует, обновляем значение
current.value = value
return
}
if (current.next == null) {
current.next = HashMapNode(key, value)
return
}
current = current.next
}
}
}
fun get(key: K): V? {
val hashCode = key.hashCode()
val index = (size - 1) and hashCode
var current = table[index]
while (current != null) {
if (current.key == key) {
return current.value
}
current = current.next
}
return null
}
}
n — это количество элементов в бакете.В Java 8 была введена новая структура для оптимизации обработки коллизий — красно-чёрное дерево. Если в одном бакете накопилось много элементов (по умолчанию более 8), то связный список преобразуется в красно-чёрное дерево. Это позволяет ускорить операции поиска, вставки и удаления до O(log n) в худшем случае.
// Внутри класса HashMap
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; // цвет узла: красный или черный
// Методы для работы с деревом
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
// Логика вставки в красно-чёрное дерево
}
final TreeNode<K,V> getTreeNode(int h, Object k) {
// Логика поиска в дереве
}
}
HashMap сам управляет тем, когда преобразовать список в дерево и наоборот, основываясь на количестве элементов в бакете.