HashMap под микроскопом

Введение

Привет! Эта статья будет полезна новичкам в разработке или тем, кому нужно освежить знания перед собеседованием. Как ни странно, но вопросы о том, как устроен HashMap, всё ещё популярны среди интервьюеров.

Раньше, когда я готовился к собеседованиям и изучал материалы на Хабре, у меня часто возникали сомнения в актуальности некоторых статей и их слишком теоретическом подходе. По моему мнению, лучший способ разобраться в теме — это заглянуть в документацию с примерами и/или изучить исходный код. Но если вы сами пока не готовы копаться в коде, я покажу и прокомментирую основные моменты. Версия java 21.

Внутренние параметры

Начнем с компонентов класса HashMap. На следующем скрине представлены поля класса HashMap:

Исследуемый класс имеет следующие поля:

• table — это массив корзин (бакетов), класс Node опишу ниже

• size — количество пар ключ — значение, хранящиеся в мапе

• threshold — критическое количество заполненных ячеек массива бакетов, после которого происходит его расширение (зависит от capacity и loadFactor)

• loadFactor — критическое значение процента заполнения бакетов в массиве для его расширения

Далее представлены константы. Некоторые из переменных можно задавать при инициализации массива вместо использования дефолтных значений:

• DEFAULT_INITIAL_CAPACITY — размер массива бакетов по умолчанию

• DEFAULT_LOAD_FACTOR — пороговый процент заполнения массива бакетов для расширения

• TREEIFY_THRESHOLD — пороговое значение длинны списка в бакете для превращения списка в дерево (об этом подробнее ниже)

• UNTREEIFY_THRESHOLD — пороговое значение для обратного превращения

• MIN_TREEIFY_CAPACITY — минимальное значение длинны массива бакетов, при котором возможно превращение списка в дерево

Класс бакета (корзины)

HashMap содержит массив бакетов, бакеты — это внутренний класс, который содержит ключ, значение, хэш и ссылку на следующую ноду.

Ниже представлен класс корзины (бакета), который описан внутри HashMap:

Бакет содержит ссылку на следующий бакет (next), поэтому каждая ячейка массива table содержит в себе связный список. (или дерево, см ниже)

При определенных обстоятельствах связный список из объектов Node трансформируется в дерево из объектов TreeNode. Полностью представить код класса TreeNode не получится, потому что он занимает около 600 строк. Ниже представлено начало класса с переменными:

Конструкторы

Класс hashMap содержит конструкторы со следующими параметрами:

1. Конструктор с начальной емкостью массива бакетов (initialCapacity) и критическим процентом заполнения для расширения (loadFactor)

2. Конструктор с начальной емкостью (initialCapacity)

3. Пустой конструктор, в этом случае будут использоваться константы по умолчанию (см константы выше)

4. Конструктор, который принимает другую мапу.

Скриншот исходников:

Добавление элемента

Разберемся с процессом добавления элемента. В ходе разбора этой операции мы узнаем об особенностях 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
На основе хэша ключа выбирается индекс в массиве бакетов (через битовую операцию &). Если по этому индексу в массиве нет бакета, то он создается.

Шаг №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 представляет собой массив бакетов, каждый бакет в этом массиве может быть головой связного списка или дерева.

• Вставка и получение элементов имеют имеют сложность O(1) или О(n), или O(logN) в зависимости от состояния мапы и работы хэш-функции.

• Эффективность работы мапы зависит от алгоритма хэширования ключа

• Если делаем вставку с ключом, который уже есть в мапе, то значение перезаписывается

• Массив бакетов расширяется при достижении критического значения