Подробный разбор класса HashMap

Прежде чем переходить к подробному рассмотрению класса, остановимся на базовых понятиях, связанных с хеш-таблицами. В данной статье не будут рассматриваться методы для работы с хеш-отображением. Наглядно и подробно будут рассмотрены только операции вставки, поиска и удаления. Прочитать описание имеющихся у HashMap методов, я думаю не составит труда у того же Шилдта. Возможно, в будущем я напишу ещё одну статью, посвященную таким методам, но пока это под вопросом. По сравнению с Java 7 класс HashMap в Java 8 претерпел значительные изменения (+1000 строк кода). Про реализацию в Java 7 можно почитать тут (но уже не акутально): хабр Хеш-таблицей называется структура данных, реализующая интерфейс ассоциативного массива (абстрактная модель «ключ – значение» или entry), которая обеспечивает очень быструю вставку и поиск: независимо от количества элементов вставка и поиск (а иногда и удаление) выполняются за время, близкое к константе – O(1). По сути, это обычный массив, где местоположение элемента зависит от значения самого элемента. Связь между значением элемента и его позицией в хеш-таблице задает хеш-функция. Хеш-функция получает входную часть данных, которую мы называем ключом, а на выходе она выдает целое число, известное как хеш-значение (или хеш-код). Затем, хеш-значение привязывает наш ключ к определенному индексу хеш-таблицы. Для основных операций: вставки, поиска и удаления мы используем одну и ту же хеш-функцию, поэтому эти операции осуществляются довольно быстро. По этой причине важно, чтобы хеш-функция вела себя последовательно и выводила один и тот же индекс для одинаковых входных данных. Стоит отметить, что полученный хеш-код может быть огромным числовым значением, а исходный массив условно рассчитан только на 16 элементов. Не создавать же массив на миллиард элементов, чтобы добавить туда всего десять? Поэтому мы этот хеш-код должны как-то трансформировать в значения от 0 до 15 (если размер массива 16). И вот для этого используются дополнительные преобразования. Таким образом, мы генерируем индекс для минимизации размера массива. Например, в HashMap до Java 8 использовался вот такой дополнительный метод для нахождения нужной ячейки:

static int indexFor(int h, int length) {
        return h & (length-1);
}

На вход он принимал хеш-код полученный в результате работы hashCode() и длину внутреннего массива (количество ячеек). А возвращал результат «хеш-код» –> побитовое «И» –> (длина массива – 1). Класс HashMap наследуется от класса AbstractMap и реализует следующие интерфейсы: Map, Cloneable, Serializable. За хеш-функцию в Java отвечает метод hashCode(). Реализация по умолчанию hashCode() возвращает значение, которое называется идентификационный хеш (identity hash code). Даже если класс переопределяет hashCode(), вы всегда можете получить идентификационный хеш объекта с помощью вызова System.identityHashCode(Object o). Реализация по умолчанию hashCode() в OpenJDK не имеет ничего общего с адресом памяти, как это порой принято считать. Подробнее здесь: хабр В HashMap хеш-таблица реализована на основе массива (а если точнее — динамического, так как таблица может расширяться) односвязных списков. По сути, мы получаем хеш-код ключа в результате работы метода hashCode(), который затем модифицируется (как рассмотрим далее), а внутри с помощью дополнительного метода полученные значения распределяются по нужным ячейкам. Элементы массива (ячейки) еще называются корзинами «buckets», которые используются для хранения отдельно взятых узлов. Каждый из бакетов представляет из себя коллекцию (список или дерево). Узел представляет собой объект вложенного класса Node (или TreeNode при древовидной структуре). По сути, внутри ячейки массива лежит LinkedList, только список односвязный, либо красное-черное дерево, которое лежит в основе реализации другого класса — TreeMap. Вариант с красно-черным деревом возникает не столь часто (как, что и куда — далее), да и структура эта довольно непростая для понимания, поэтому акцент будет сделан на узле типа Node. Node — это вложенный класс внутри HashMap, который имеет следующие поля:

• final int hash — хеш текущего элемента, который мы получаем в результате хеширования ключа;
• final K key — ключ текущего элемента. Именно сюда записывается то, что вы указываете первым объектом в методе put();
• V value — значение текущего элемента. А сюда записывается то, что вы указываете вторым объектом в методе put();
• Node < K, V> next — ссылка на следующий узел в пределах одной корзины. Список же связный, поэтому ему нужна ссылка не следующий узел, если такой имеется.

Теперь рассмотрим поля самого класса HashMap:

• transient Node < K, V> [] table – сама хеш-таблица, реализованная на основе массива, для хранения пар «ключ-значение» в виде узлов. Здесь хранятся наши Node;
• transient int size — количество пар «ключ-значение»;
• int threshold — предельное количество элементов, при достижении которого размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
• final float loadFactor — этот параметр отвечает за то, при какой степени загруженности текущей хеш-таблицы необходимо создавать новую хеш-таблицу, т.е. как только хеш-таблица заполнилась на 75%, будет создана новая хеш-таблица с перемещением в неё текущих элементов (затратная операция, так как требуется перехеширование всех элементов);
• transient Set< Map.Entry< K,V>> entrySet — содержит кешированный entrySet(), с помощью которого мы можем перебирать HashMap.

И константы:

• static final int DEFAULT_INITIAL_CAPACITY= 1 << 4 — емкость хеш-таблицы по умолчанию (16);
• static final int MAXIMUM_CAPACITY = 1 << 30 — максимально возможная емкость хеш-таблицы (приблизительно 1 млрд.);
• static final float DEFAULT_LOAD_FACTOR = 0.75f — коэффициент загрузки, используемый по умолчанию;
• static final int TREEIFY_THRESHOLD = 8 — это «порог» количества элементов в одной корзине, при достижении которого внутренний связный список будет преобразован в древовидную структуру (красно-черное дерево).
• static final int UNTREEIFY_THRESHOLD = 6 — если количество элементов в одной корзине уменьшится до 6, то произойдет обратный переход от дерева к связному списку;
• static final int MIN_TREEIFY_CAPACITY = 64 — минимальная емкость (количество корзин) хеш-таблицы, при которой возможен переход к древовидной структуре. Т.е. если в хеш-таблице по крайней мере 64 бакета и в одном бакете 8 или более элементов, то произойдет переход к древовидной структуре.

Конструкторы класса:

1. public HashMap() — создает хеш-отображение по умолчанию: объемом (capacity) = 16 и с коэффициентом загруженности (load factor) = 0.75;
2. public HashMap(Map< ? extends K, ? extends V> m) — создает хеш-отображение, инициализируемое элементами другого заданного отображения с той начальной емкостью, которой хватит вместить в себя элементы другого отображения;
3. public HashMap(int initialCapacity) — создает хеш-отображение с заданной начальной емкостью. Для корректной и правильной работы HashMap размер внутреннего массива обязательно должен быть степенью двойки (т.е. 16, 64, 128 и т.д.);
4. public HashMap(int initialCapacity, float loadFactor) — создает хеш-отображение с заданными параметрами: начальной емкостью и коэффициентом загруженности.

Класс реализует интерфейс Map и расширяет класс AbstractMap, не дополняя их своими методами. Хеш-отображение не гарантирует порядок расположения своих элементов. Следовательно, порядок, в котором элементы вводятся в хеш-отображение, не обязательно соответствует тому порядку, в котором они извлекаются итератором. Добавление объектов Добавление пары "ключ-значение" осуществляется с помощью метода put(). Рассмотрим шаги, выполняемые при добавлении объекта:

1. Вычисляется хеш-значение ключа введенного объекта. Хэш ключа вычисляет метод static final int hash(Object key), который уже обращается к известному нам методу hashCode() ключа. Для этого используется либо переопределенный метод hashCode(), либо его реализация по умолчанию. Дополнительные преобразования в методе hash():

   
   static final int hash(Object key) {
           int h;
           return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   

   Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-кодов будут заполнены только нижние. В таком случае ключи в HashMap будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в какой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша объекта начали вносить коррективы в то, в какой бакет попадёт объект) и, как следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap.

2. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:

   
   i = (n - 1) & hash
   

   где n – длина массива.

3. Создается объект Node.

4. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового элемента поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

   Теперь к очень подробному примеру.

   1. Создадим объект класса HashMap:

      
      HashMap < String, Integer> map = new HashMap<>();
      

   2. С помощью метода put() добавим в хеш-отображение первую пару «ключ-значение»:

      
      map.put("KING", 100);
      

      В этот момент внутри вызывается метод putVal().

   3. С помощью хеш-функции, роль которой играет метод hash, вычисляется хеш-код ключа, внутри которого предварительно вычисляется хеш-код с помощью метода hashCode() (в данном случае класса String), в результате чего мы получаем его «предварительное значение» – 2306967. Может проверить в IDEA с помощью

      
      System.out.println("KING".hashCode());
      

      Полученный хеш-код модифицируется по формуле: (хеш-код) ^ (хеш-код>>> 16), и в результате получаем окончательный хеш-код – 2306996.

   4. Проверяем таблицу на «пустоту»:

      
      if ((tab = table) == null || (n = tab.length) == 0)
      

      где [] tab — сама хеш-таблица: ссылаем tab и table (напомню, что это поле класса HashMap, которое хранит массив для наших элементов) на один и тот же массив, а int n – дополнительная переменная-счетчик.

      Так как проверка вернёт true (потому что массив для таблицы не был создан с помощью оператора new в конструкторе), будет вызван метод resize(), который собственно и создаст таблицу размером на 16 элементов. Да-да, конструкторы класса никакой таблицы не создают. Вместо этого всегда происходит вызов метода resize() при первом добавлении элемента. Длина созданной таблицы (считай длина массива) будет записана в переменную n – n = (tab = resize()).length, которая в дальнейшем используется для вычисления бакета.

   5. Одновременно вычисляем индекс бакета, куда будет помещен наш объект, и проверяем, а есть ли уже в нем элементы. Вычисляем:

      
      i = (n - 1) & hash
      i = (16 - 1) & 2306996
      i = 4
      

      проверяем:

      
      if ((p = tab[i = (n - 1) & hash]) == null)
      

   6. Так как в результате проверки мы получим true (в бакете элементов нет), будет сгенерирован объект Node со следующими полями:

      
      {
      int hash = 2306996 — сгенерированный хеш-код
      String key = {"KING"} — ключ
      Integer value = 100 — значение
      Node next = null — ссылка на следующий узел
      }
      

      Наш сформированный объект Node будет добавлен в бакет под индексом [4]:

      
      tab[i] = newNode(hash, key, value, null);
      tab[4] = newNode(2306996, “KING”, 100, null);
      

      newNode() — это метод, который просто возвращает объект класса Node.

   7. После добавления будет произведена проверка не превышает ли текущее количество элементов параметр threshold:

      
      if (++size > threshold)
          resize();
      

      Если превышает, тогда будет вызван метод resize() для увеличения размера хеш-таблицы.

      На этом метод putVal() (соответственно и put()) завершит свою работу.

      Графически полученный результат изобразить можно так:

      Так в общем случае выглядит добавление Node (пара «ключ-значение») в хеш-таблицу, если нужный бакет оказывается пуст. Теперь попробуем добавить такой элемент, который приведет к коллизии (когда в одном бакете оказывается более одного элемента).

Немного про коллизии Ситуация, когда разные ключи попадают в один и тот же бакет (даже с разными хешами), называется коллизией или столкновением. Даже если хеш-таблица больше, чем набор данных, и была выбрана хорошая хеш-функция, это не гарантирует того, что коллизии не возникнут. Да и значение хеша ограничено диапазоном значений типа int (порядка 4 млрд.). Полученное новое значение также нужно куда-то записать, и для этого нужно определить, куда именно оно будет записано. Это называется решением коллизии. Существует два подхода:

• external chaining или метод цепочек (реализован в HashMap) — т.е. в ячейке на самом деле содержится список (chain). А уже в списке может содержаться несколько значений (не обязательно с одинаковым хеш-кодом).
• linear probing или метод открытой адресации (реализован в IdentityHashMap) – заключается в поиске первой пустой ячейки после той, на которую указала хеш-функция;

Про коллизии можно почитать здесь: клик

1. С помощью метода put() добавим в хеш-отображение еще одну пару «ключ-значение»:

   
   map.put("BLAKE", 10);
   

2. Вычисляем "предварительный хеш" – 63281361. Модифицируем его и в результате получаем окончательный хеш-код – 63281940.

3. Так как первая проверка на «пустоту» теперь вернет false (создавать таблицу не надо), сразу вычисляем индекс бакета, куда будет помещен наш объект:

   
   i = (n - 1) & hash
   i = (16 - 1) & 63281940
   i = 4
   

4. Бакет под указанным индексом проверяется на наличие в нем элементов и так как условие if ((p = tab[i = (n - 1) & hash]) == null) в этом случае не выполняется (в бакете уже есть элемент), тогда переходим к блоку else.

5. В первую очередь мы сравниваем добавляемый элемент с первым элементом связного списка внутри бакета:

   
   (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
   

   При проверке сначала сравниваются хеши ключей. Если этот «участок» (p.hash == hash) возвращает false, тогда остальная часть условия игнорируется (&&), так как объекты гарантированно разные. Иначе затем сравниваются ключи по ссылке (==) и в случае неравенства, ключи сравниваются уже посредством метода equals(). Сравнение осуществляется в таком порядке во благо производительности. Если все три выражения возвращают true, это означает, что ключи равны и новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать значение у ключа:

   
   if (e != null) { // existing mapping for key
         V oldValue = e.value;
         if (!onlyIfAbsent || oldValue == null)
         e.value = value;
         afterNodeAccess(e);
          return oldValue;
    }
   

   В результате сравнения ключей мы получаем false уже на первом этапе (разные хеши).

6. Игнорируем условие (p instanceof TreeNode), так как структура в бакете не является древовидной на данном этапе.

7. Далее переходим в цикл for, где в пределах одного бакета проверяем у элементов указатель на следующий элемент next, и если он равен null (значит элемент в списке последний и единственный), добавляем новый элемент Node в конец списка:

   
   if ((e = p.next) == null){
   	p.next = newNode(hash, key, value, null)
   ... };
   

   Вы можете спросить, а где же проверка на равенство ключей? Мы же не можем просто взять и добавить новый элемент. Так вот она уже была заранее осуществлена в пункте (5). Благодаря этому, теперь мы можем просто проверить указатель этого элемента, и так как он сейчас равен null, можно сделать вывод о том, что в списке только один элемент. И так как мы уже проверяли их ключи, мы можем безболезненно добавлять новый элемент.

   Если же при первой итерации указатель не равен null, это говорит о том, что в списке как минимум два элемента, поэтому в таком случае мы переходим к следующему условия и сравниваем ключ добавляемого элемента со всеми ключами элементов в списке (способом, описанным в пятом пункте).

   
   if (e.hash == hash &&
                           ((k = e.key) == key || (key != null && key.equals(k))))
   

   Если при сравнении ключей будет найдено совпадение, новый элемент будет записан в дополнительную переменную, чтобы в дальнейшем с её помощью перезаписать значение у ключа.

   После добавления второго элемента наш объект HashMap графически выглядит так:

   В итоге, добавление элементов при коллизии (в пределах одного бакета) выглядит следующим образом:

   • проверяем с помощью методов hashCode() и equals(), что оба ключа одинаковы.
   • если ключи одинаковы, заменить текущее значение новым.
   • иначе связать новый и старый объекты с помощью структуры данных "связный список", указав ссылку на следующий объект в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре

8. После каждой итерации (добавления нового элемента) в цикле for увеличивается счетчик, который отвечает за количество элементов в бакете:

   
   for (int binCount = 0; ; ++binCount)
   

   До тех пор, пока их количество не станет равно или больше 7:

   
   binCount >= TREEIFY_THRESHOLD – 1
   

   В таком случае произойдет вызов метода treeifyBin()treeify()для непосредственного построения древовидной структуры. Однако, если количество бакетов в текущей хеш-таблице меньше 64:

   
   if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
   

   Вместо перехода к древовидной структуре будет вызван метод resize() для увеличения размера хеш-таблицы с перераспределением элементов. treeify() в свою очередь связный список из TreeNode конвертирует в красно-черное дерево. Метод resize() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.

   Если кратко, не вдаваясь в подробности структуры красно-черного дерева, то происходит следующее:

   1. Первый элемент списка записывается как корень всего дерева (чёрный цвет):

      
      if (root == null) {
          x.parent = null;
          x.red = false;
          root = x;
      }
      

   2. Для остальных элементов:

      распределяем их налево или направо в зависимости от значения хешей:

      
      if ((ph = p.hash) > h)
          dir = -1;
      else if (ph < h)
          dir = 1;
      
      

      Все левые потомки должны быть меньше своего корневого узла (или равны ему), в то время как все правые потомки должны быть больше.

   3. Если у двух элементов совпали хеши и их нельзя сравнить иным образом (не реализуют интерфейс Comparable), прерываем построение дерева и вызываем метод tieBreakOrder(), который в свою очередь использует нативный метод System.identityHashCode() для вычисления глобального уникального хеш-кода.

      Подробнее здесь: ссылка на статью

   4. Проверяем элементы дерева (объекты TreeNode) до тех пор, пока не будет найден дочерний (левый или правый) нулевой элемент.

      
      if ((p = (dir <= 0) ? p.left : p.right) == null)
      

   5. Добавляем дочерний узел (левый или правый в зависимости от dir):

      
      x.parent = xp;
      if (dir <= 0)
          xp.left = x;
      else
          xp.right = x;
      

   6. Так как при добавлении нового элемента может нарушиться баланс дерева, вызываем метод для перебалансировки:

      
      root = balanceInsertion(root, x);
      

      Про балансировку КЧД можно почитать здесь: хабр

   7. После балансировки корневой элемент может измениться. Исправляем это вызовом метода, который гарантирует, что переданный ему корень будет первым узлом:

      
      moveRootToFront(tab, root)
      

      Как строится и самобалансируется красно-черное дерево можно наглядно посмотреть здесь: визуализация

На этом в принципе всё и на примере предположим, что мы хотим добавить в качестве ключей следующие имена: KING, MARY, JOSE, ANNA, FRED, TONY, ALEX, PEPE. И допустим, что в хеш-таблице у нас как минимум 64 бакета, и все эти элементы скопились в одном бакете. Структурно этот бакет будет выглядеть так (элементы сортируются по хеш-коду): Вид КЧД: Вид внутри бакета: Получение элементов (извлечение значения по ключу) Относительно операции добавления осуществляется довольно просто. Алгоритм (когда в бакете связный список) можно записать так:

1. Вычислить хэш код ключа.
2. Вычислить индекс бакета.
3. Перейти по индексу и сравнить ключ первого элемента с имеющимся значением. Если они равны – вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.
4. Если следующий объект Node равен null, возвращаем null.
5. Если следующий объект Node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект Node не будет равен null.

С помощью метода get() получим значение для ключа “KING”:

map.get("KING");

Внутри вызывается метод getNode(int hash, Object key), которому передается сам ключ (“KING”) и его хеш (2306996), который предварительно вычисляется тем же способом, что и при операции put().

1. Проверяем:

   1. существует ли вообще хеш-таблица: (tab = table) != null

      Напомню, что при создании HashMap массив для таблицы в конструкторе не создается, это происходит в дальнейшем в методе resize(), который вызывается всегда при добавлении первого элемента в хеш-таблицу. Поэтому, если в HashMap не было добавлено никаких элементов, внутреннего массива для хранения элементов просто не существует.

   2. если предыдущее выражение возвращает true, необходимо убедиться в том, что длина внутреннего массива больше 0: (n = tab.length) > 0;

   3. если предыдущее выражение также возвращает true, переходим в бакет под индексом (в нашем случае 4), который был предварительно вычислен, и проверяем его на наличие в нем элементов:

      
      (first = tab[(n - 1) & hash]) != null)
      

   4. Сравниваем ключ, который мы ищем, с ключом первого элемента в списке внутри бакета, так как в большинстве бакетов будет находиться (не везде же у нас коллизии) только один элемент (наш случай). Как и в случае с методом put(), сравниваются хеши, и если они совпадают, ключи сравниваются по ссылке, и только потом по equals().

      
      if (first.hash == hash && // always check first node
          ((k = first.key) == key || (key != null && key.equals(k))))
      

      Так как в нашем случае, ключ “KING” будет предшествовать ключу “BLAKE” (внутри связного списка новые элементы добавляются в конец, а KING был добавлен первым), мы остановимся на данном этапе и вернем объект first типа Node методу get(), который «выцепит» у него поле со значением (100):

      
      return (e = getNode(hash(key), key)) == null ? null : e.value;
      

2. Если внутри бакета находится больше одного элемента, тогда:

   1. если бакет представляет собой связный список – проходимся в списке по каждому из элементов в цикле do – while до тех пор , пока не будет найдено совпадение:

      
      do {
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      } while ((e = e.next) != null);
      

   2. если бакет представляет собой древовидную структуру, тогда дополнительно вызывается метод getTreeNode(), который в свою очередь для поиска нужного ключа использует метод find(). Осуществляем поиск по дереву – сравниваются хеши и определяется левый или правый узел корня для поиска. Если ключи равны (по ссылке или по equals), возвращаем этот узел. Если левый или правый дочерний узлы равны null, дополнительно сравниваем ключи через compareTo (если ключи реализуют интерфейс Comparable), иначе осуществляем рекурсивный поиск по дереву (правому или левому поддереву), пока не будет найдено совпадение.

Удаление объектов из HashMap Так как место в статье заканчивается, кратко опишу как происходит удаление по ключу. Алгоритм очень похож:

• заходим в нужный бакет (опять же он предварительно вычисляется);

• если в бакете только один объект (проверяем у него указатель null) сравниваем хеши, ссылки и equals (если вдруг хеши не равны). Нашлось совпадение? Отлично, это наш ключ – удаляем его (=null) и возвращаем значение этого ключа.

• если в бакете больше одного элемента, проверяем каждый элемент в цикле до тех пор, пока не найдем элемент или достигнем конца списка.

• если элемент не был найден — возвращаем null.

В ситуации с деревом довольно мудреная реализация, о которой лучше не знать и спать спокойно (в описании к методу даже написано, что реализация сложнее, чем в обычной операции удаления в красно-черном дереве). Тем более, при удалении количество узлов в одном бакете может вернуться к значению 6, и тогда дерево обратно перестроится в связный список. Если Вы не разработчик с многолетнем стажем, знать об этом и понимать это совсем не обязательно (да и просто не нужно).