HashMap под микроскопом
Введение
Привет! Эта статья будет полезна новичкам в разработке или тем, кому нужно освежить знания перед собеседованием. Как ни странно, но вопросы о том, как устроен HashMap, всё ещё популярны среди интервьюеров.
Раньше, когда я готовился к собеседованиям и изучал материалы на Хабре, у меня часто возникали сомнения в актуальности некоторых статей и их слишком теоретическом подходе. По моему мнению, лучший способ разобраться в теме — это заглянуть в документацию с примерами и/или изучить исходный код. Но если вы сами пока не готовы копаться в коде, я покажу и прокомментирую основные моменты. Версия java 21.
Внутренние параметры
Начнем с компонентов класса HashMap. На следующем скрине представлены поля класса HashMap:
Поля класса HashMap
Исследуемый класс имеет следующие поля:
table — это массив корзин (бакетов), класс Node опишу ниже
size — количество пар ключ — значение, хранящиеся в мапе
threshold — критическое количество заполненных ячеек массива бакетов, после которого происходит его расширение (зависит от capacity и loadFactor)
loadFactor — критическое значение процента заполнения бакетов в массиве для его расширения
Далее представлены константы. Некоторые из переменных можно задавать при инициализации массива вместо использования дефолтных значений:
Константы
DEFAULT_INITIAL_CAPACITY— размер массива бакетов по умолчаниюDEFAULT_LOAD_FACTOR— пороговый процент заполнения массива бакетов для расширенияTREEIFY_THRESHOLD— пороговое значение длинны списка в бакете для превращения списка в дерево (об этом подробнее ниже)UNTREEIFY_THRESHOLD— пороговое значение для обратного превращенияMIN_TREEIFY_CAPACITY— минимальное значение длинны массива бакетов, при котором возможно превращение списка в дерево
Класс бакета (корзины)
HashMap содержит массив бакетов, бакеты — это внутренний класс, который содержит ключ, значение, хэш и ссылку на следующую ноду.
Ниже представлен класс корзины (бакета), который описан внутри HashMap:
Внутренний класс Node (бакет)
Бакет содержит ссылку на следующий бакет (next), поэтому каждая ячейка массива table содержит в себе связный список. (или дерево, см ниже)
При определенных обстоятельствах связный список из объектов Node трансформируется в дерево из объектов TreeNode. Полностью представить код класса TreeNode не получится, потому что он занимает около 600 строк. Ниже представлено начало класса с переменными:
Начало класса TreeNode
Конструкторы
Класс hashMap содержит конструкторы со следующими параметрами:
Конструктор с начальной емкостью массива бакетов (initialCapacity) и критическим процентом заполнения для расширения (loadFactor)
Конструктор с начальной емкостью (initialCapacity)
Пустой конструктор, в этом случае будут использоваться константы по умолчанию (см константы выше)
Конструктор, который принимает другую мапу.
Скриншот исходников:
Конструкторы класса HashMap
Добавление элемента
Разберемся с процессом добавления элемента. В ходе разбора этой операции мы узнаем об особенностях HashMap.
Посмотреть исходник метода добавления:
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
// ШАГ №1
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// ШАГ №2
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
// ШАГ №3
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ШАГ №4
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// ШАГ №5
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// Шаг №6
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// ШАГ №7
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Шаг №1
На первом этапе происходит проверка инициализации массива бакетов. Если массив бакетов еще не был инициализирован или имеет нулевую длину, то он
инициализируется и расширяется до дефолтных значений.
Шаг №2
На основе хэша ключа выбирается индекс в массиве бакетов (через битовую операцию &). Если по этому индексу в массиве нет бакета, то он создается.
Подробнее про битовую операцию &
Оператор & сравнивает первый бит первого числа с первым битом второго. Поскольку это оператор «И», то результат будет равен 1 только в том случае, если оба бита равны 1. Во всех остальных случаях результатом будет 0.
Пример:
100010101&
110110000
-----------------
100010000
Шаг №3
Если по вычисленному индексу уже есть бакет, то следующим этапом происходит проверка идентичности этого бакета и добавляемого элемента. Проверка происходит по хэшу ключа и равенству ссылки на ключ или равенству самого ключа.
Шаг №4
Если бакет является элементом дерева, то вызывается метод для добавления элемента в дерево
Шаг №5
На этом этапе происходит последовательное прохождение по связному списку в бакете. Если находим идентичный ключ (по ссылке или значению с таким хэшом), то сохраняем эту ссылку и проходим к следующему шагу. Если новый элемент уникальный, то вставляем его в самый конец списка. При этом, если при количество элементов в списке превышает значение TREEFY_TRESHOLD, то происходит видоизменение связного списка в дерево.
Шаг №6
На этом этапе происходит замена старого значения на новое, если мы пытаемся положить значение по уже существующему ключу.
Шаг №7
Далее происходит увеличение длины массива бакетов, если количество элементов в массиве превышает пороговое значение (THRESHOLD).
Алгоритмическая сложность:
Сложность добавления элемента зависит от состояния массива бакетов, а это зависит от хэш функции:
Если массив бакетов не содержит связных списков, то есть у каждого бакета нет следующего элемента, то получение элемента всегда будет занимать примерно одинаковое время: вычисляем ячейку массива по хэшу → достаем бакет и выдаем значение. Следовательно, сложность будет O (1)
В самом худшем случае, когда у нас хэш функция работает плохо и всегда выдает одно и то же значение, то все элементы будут помещаться в один бакет и вся мапа станет связным списком, тогда будет сложность O (n). Эта сложность будет наблюдаться до определенного момента.
При увеличении длинны связного списка в бакете более 8 и достаточной длинны массива бакетов происходит преобразование списка в дерево, поэтому сложность станет равной O (logN)
Получение элемента
Метод получения элемента представлен ниже:
public V get(Object key) {
Node e;
return (e = getNode(key)) == null ? null : e.value;
}
В случае отсутствия ключа в мапе возвращается null, поэтому стоит предварительно проверять наличие пары через containsKey(Object key), иначе можем получить NullPointerException в дальнейшем.
Посмотреть исходник метода получения значения:
final Node getNode(Object key) {
Node[] tab; Node first, e; int n, hash; K k;
// Шаг №1
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & (hash = hash(key))]) != null) {
// Шаг №2
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// Шаг №3
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Шаг №1
Сначала происходят проверки на инициализацию массива бакетов, наличие бакетов в массиве и существование бакета в ячейке массива, которую мы получаем по хэшу ключа.
Шаг №2
На этом шаге проверяется первый элемент в бакете, если он соответствует запрашиваемому ключу, то он и возвращается.
Шаг №3
Если не подходит первый элемент в массиве бакетов, то для поиска соответствующего элемента происходит перебор связного списка или дерева в бакете.
В случае отсутствия элемента возвращается null.
Алгоритмическая сложность идентична алгоритму добавления элемента.
Пример
Далее представлен пример, в котором в качестве ключа используется строка. В debug режиме мы можем получать доступ к приватным переменным. На скриншоте мы можем увидеть, что при добавлении трех значений в мапу они все попадают в один бакет и образуют связный список. Кроме этого, видно, что threshold = 12, это составляет 0,75 от стандартной длинны массива бакетов (16). При достижении 12 элементов массив бакетов будет удвоен.
Пример для иллюстрации параметров HashMap
Выводы:
HashMap представляет собой массив бакетов, каждый бакет в этом массиве может быть головой связного списка или дерева.
Вставка и получение элементов имеют имеют сложность O (1) или О (n), или O (logN) в зависимости от состояния мапы и работы хэш-функции.
Эффективность работы мапы зависит от алгоритма хэширования ключа
Если делаем вставку с ключом, который уже есть в мапе, то значение перезаписывается
Массив бакетов расширяется при достижении критического значения
