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 содержит конструкторы со следующими параметрами:

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

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

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

Разберемся с процессом добавления элемента. В ходе разбора этой операции мы узнаем об особенностях 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) &amp; hash]) == null)  
        tab[i] = newNode(hash, key, value, null);  
    else {
        Node e; K k;
        
        // ШАГ №3  
        if (p.hash == hash &amp;&amp;  
            ((k = p.key) == key || (key != null &amp;&amp; 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 &gt;= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);  
                    break;  
                }  
                if (e.hash == hash &amp;&amp;  
                    ((k = e.key) == key || (key != null &amp;&amp; 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 &gt; 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 &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;  
        (first = tab[(n - 1) &amp; (hash = hash(key))]) != null) {  
        
        // Шаг №2
        if (first.hash == hash &amp;&amp; // always check first node  
            ((k = first.key) == key || (key != null &amp;&amp; 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 &amp;&amp;  
                    ((k = e.key) == key || (key != null &amp;&amp; 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) в зависимости от состояния мапы и работы хэш-функции.
Эффективность работы мапы зависит от алгоритма хэширования ключа
Если делаем вставку с ключом, который уже есть в мапе, то значение перезаписывается
Массив бакетов расширяется при достижении критического значения