JavaRush /Java блог /Java Developer /Подробный разбор класса HashMap

26 уровень

23 января 2020
204002 views
78 comments

Подробный разбор класса 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 или более элементов, то произойдет переход к древовидной структуре.

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

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

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

Вычисляется хеш-значение ключа введенного объекта. Хэш ключа вычисляет метод 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.
Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент:
```
i = (n - 1) & hash
```
где n – длина массива.
Создается объект Node.
Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового элемента поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка.

Теперь к очень подробному примеру.
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) – заключается в поиске первой пустой ячейки после той, на которую указала хеш-функция;

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

С помощью метода put() добавим в хеш-отображение еще одну пару «ключ-значение»:
```
map.put("BLAKE", 10);
```
Вычисляем "предварительный хеш" – 63281361. Модифицируем его и в результате получаем окончательный хеш-код – 63281940.
Так как первая проверка на «пустоту» теперь вернет false (создавать таблицу не надо), сразу вычисляем индекс бакета, куда будет помещен наш объект:
```
i = (n - 1) & hash
i = (16 - 1) & 63281940
i = 4
```
Бакет под указанным индексом проверяется на наличие в нем элементов и так как условие if ((p = tab[i = (n - 1) & hash]) == null) в этом случае не выполняется (в бакете уже есть элемент), тогда переходим к блоку else.
В первую очередь мы сравниваем добавляемый элемент с первым элементом связного списка внутри бакета:
```
(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 уже на первом этапе (разные хеши).
Игнорируем условие (p instanceof TreeNode), так как структура в бакете не является древовидной на данном этапе.
Далее переходим в цикл 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(), что оба ключа одинаковы.
- если ключи одинаковы, заменить текущее значение новым.
- иначе связать новый и старый объекты с помощью структуры данных "связный список", указав ссылку на следующий объект в текущем и сохранить оба под нужным индексом; либо осуществить переход к древовидной структуре
После каждой итерации (добавления нового элемента) в цикле 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 бакета, и все эти элементы скопились в одном бакете. Структурно этот бакет будет выглядеть так (элементы сортируются по хеш-коду): Вид КЧД:

Вид внутри бакета:

Получение элементов (извлечение значения по ключу) Относительно операции добавления осуществляется довольно просто. Алгоритм (когда в бакете связный список) можно записать так:

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

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


map.get("KING");

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

Проверяем:
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;
```
Если внутри бакета находится больше одного элемента, тогда:
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, и тогда дерево обратно перестроится в связный список. Если Вы не разработчик с многолетнем стажем, знать об этом и понимать это совсем не обязательно (да и просто не нужно).

Комментарии (78)

ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ

Максим Уровень 43

23 марта 2025

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

Иван Уровень 23

19 ноября 2024

Спасибо за статью

Konstantin Уровень 22

14 января 2024

В статье неправильно написано В HashMap хеш-таблица реализована на основе массива (а если точнее — динамического, так как таблица может расширяться) односвязных списков На самом деле в HashMap статический массив transient Node<K,V>[] table; размер увеличивается функцией resize, которая создает новый статический массив с большим размером и переписывает в него элементы из старого массива

Максим Уровень 108 Expert

30 января 2024

В этом и суть динамического массива)

Konstantin Уровень 22

29 августа 2024

суть не в этом, суть в туалете в HashMap статический массив а не динамический

Ann Kudra Уровень 109 Expert

3 октября 2023

Мне кажется, для студента на 17ом уровне еще рановато. Оставлю-ка я её в закладках до лучших времен.

Anonymous #2502407 Уровень 2

6 сентября 2023

После балансировки корневой элемент может измениться. Исправляем это вызовом метода, который гарантирует, что переданный ему корень будет первым узлом: moveRootToFront(tab, root) А как же тогда корректно будут распределяться элементы, больше или меньше корня, если он будет туда искусственно помещён и будет скорее всего меньше или больше обоих потомков????

IrinaVyu Уровень 22

1 июля 2023

браво! наконец то понятно

Alexandr Strukov Уровень 1

27 июня 2023

Замечательная статья. Огромное спасибо автору:)

Александр Полозов Уровень 51

4 марта 2023

На хабре прочитал, что если в бакете уже есть элементы, то новый элемент добавляется в начало списка. Здесь же автор пишет что в конец... Кому верить?

Vitya Уровень 33

6 апреля 2023

В конец. Похоже, всё дело в разных Java версиях. Рекомендую следить для какой Java написана какая-либо статья. Здесь, видимо, для Java 8. Хотя на дворе уже 19-ая 🙂. Но HashMap вроде не менялся.

Евгений Уровень 47

16 июля 2023

никому не верить. Пойти в IDEA, открыть класс HashMap и самому посмотреть.

Anonymous #3352746 Уровень 19

21 марта 2024

В конец. В идее посмотрел.


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

Alexey Bril Уровень 4

14 января 2023

Благодарю за статью. Получилось уложить хешмапу в голове

Anonymous #2657901 Уровень 1

8 декабря 2022

надо покурить

Denis Rogov Уровень 1 Expert

12 января 2023

пхахаха

Яков Мануилов Уровень 36

16 февраля 2023

Тут надо дунуть

Ольга Уровень 108 Expert

29 ноября 2022

Слушьте, ну на 18 уровне Java Syntax это выглядит просто целенаправленным взрывом мозга студента, ссылка на статью хоть и позиционируется как доп материал, но тем не менее ввергает новичка в уныние с каждым следующим абзацем. Отложу-ка я ее на далёкое потом...

Denis Rogov Уровень 1 Expert

12 января 2023

это пригодится при изучении Collections на 30+ или 40+ уровне, в зависимости от того в какую ветку пойдёте первее(треды или коллекции). Но судя по тому, что у Вас есть штамп Expert, возможно, оно уже Вам и не надо, но для будущих поколений пояснил.

Яков Мануилов Уровень 36

16 февраля 2023

Согласен, мне эта инфа пригадилась впервые за ночь до собеса на Middle

FragoLanten Уровень 36

30 июня 2023

Все правильно. так глубоко будут спрашивать только на собеседовании, меня например попросили вкратце описать процедуру перехода Node в красно черное дерево, при собеседовании на стажера Java.

Bibzen' Уровень 16

19 июля 2023

Вот это вопросы нынче к стажерам. на мидлах такого не спрашивают

Никита Небольсин Уровень 31

2 ноября 2022

Это божественно! Статья обязательна к прочтению всем!

Anonymous #2686522 Уровень 1

19 октября 2022

Заметил, что в 17 Джяве метод getNode(int hash, Object key) принимает только ключ, а хэш считается внутри. Ну и за счёт этого немножко изменились детали реализации.

Anonymous #2686522 Уровень 1

5 сентября 2022

Ну теперь-то я им на собеседовании популярно объясню, как добавляется элемент в Hashmap!😎

eryominem Уровень 2

1 августа 2022

Благодарю за отличную статью, Вы помогли мне разобраться во внутреннем устройстве работы HashMap

Саша И. Уровень 101 Expert

30 июля 2022

Огненная статья, спасибо!

Владимир Уровень 108

28 июля 2022

офигеть, чтобы понять статью, потратил часа полтора помогла посмотреть под капот, побольше бы таких статей. Зато один раз разберешься - и вгрызается в память навечно

Макс Дудин Уровень 41

14 июня 2022

ну это... это... всё как-то... не помещается в голове за один раз

Саша И. Уровень 101 Expert

21 апреля 2022

Памагити

Евгений Якушин Уровень 2

21 апреля 2022

Да, чтобы эту кухню понять, надо самому реализацию сваять. )

Evgen Уровень 35

19 марта 2022

Жесткая дич... похоже что для самых бородатых... )

Владимир Уровень 109 Expert

16 марта 2022

Иван Голубев Уровень 108 Expert

19 февраля 2022

сложное))

Kes Уровень 41

11 января 2022

Все-таки пока не смог понять, зачем подмешивать старшие биты в младшие. Не смог воспроизвести "плохую" ситуацию, после которой это бы стало необходимым. Даже если просто брать простые числа, то их хеши просто возрастают с самими числами. И идет равномерное распределение по 16 бакетам.

Иван Борзов Уровень 24

18 февраля 2022

Все дело в методе определения индекса корзины: i = (n - 1) & hash Операция & дает фактически побитовую маску размером в 4 бита, если у нас 16 корзин, т.к. 15 в двоичной системе - это 1111. Таким образом, какой бы хэш мы не получили в десятичной системе исчисления, но при равенстве младших 4 битов этого хэша, например 1111 они всегда будут ложиться в 15-ую корзину.... Немного путано, да... проще показать. Есть два хэша, например, 2815 (b101011111111) и 3839 (b111011111111). У них младшие 4 бита - это единицы... ну и таких полно, если перебирать все комбинации остальных битов. Так вот результат операции для всех таких хэшей будет одинаковым, т.е. Х&15 = 15. Получается, что биты, старше четвертого вообще не оказывают влияния на распределение по корзинам, пока таблица не расширилась и в ней все еще 16 корзин. Видимо, хотя я этого и не проверял))), на большой выборке по статистике это создает большой перекос в распределении. Я думаю, что какая-то мат.статистика стоит за решением о подмешивании старших битов ко младшим. Но статистика штука хитрая, поэтому и фраза об этом подмешивании не категоричная, обтекаемая.

Kes Уровень 41

20 февраля 2022

Да, спасибо. Сейчас перечитываю свой вопрос, и понимаю, что он для меня уже не актуален. Порыл другие источники и всё в голове устаканилось.

Kes Уровень 41

11 января 2022

Исходники Java 7 HashMap (Чтобы глянуть на indexFor)

Ilyas Dzhalilov Уровень 50

26 декабря 2021

Статья отличная

Aleksandr Уровень 12

23 октября 2021


https://www.youtube.com/watch?v=c3RVW3KGIIE

эта же статья, только видео и на английском

Kes Уровень 41

7 января 2022

Нейросети яндекса добавляют перевод видео на русский

prime Уровень 42

5 июля 2022

крутое видео, спасибо

Andrey Уровень 18

31 августа 2021

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

Иван Сапронов Уровень 32

14 августа 2021

Лучшая статья про устройство HashMap которую я встречал. Спасибо огромное автору!

Александр Уровень 14

24 июня 2021

final float loadFactor А если все записи в один бакет попали. Допустим что занят один, в нём 500 нодов, а 15 остальных бакетов свободны. То в таком случае увеличения не произойдет?

cavc Уровень 41

20 апреля 2021

Спасибо большое за статью.

Darth Nihilus Уровень 35

10 апреля 2021

Топ статья! Спасибо 😊

Роман И Уровень 20

1 апреля 2021

Вот этот кусок парит. n – n = (tab = resize()).length.... переменная? эээ. Это целое выражение и то n-n это нуль. Хорошо бы поправить, чтобы смысл был яснее.

Darth Nihilus Уровень 35

10 апреля 2021

это просто тире, а не минус. Будет записано в n, а именно n = (tab = resize()).length...

Vesa Уровень 18

12 января 2021

5. Если следующий объект Node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект Node не будет равен null. Наверное, первые 2 шага повторять не надо, только 3-й

Vesa Уровень 18

12 января 2021


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

>Если все три выражения возвращают true, это означает, что ключи равны. А ещё это выражение вернёт true (если

p.hash == hash

равно true), если в выражении


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

хотя бы одна из частей оператора || будет true. Т.е., или если в качестве ключа пришёл тот же самый объект ((k = p.key) == key). Или если объекты ключей равны по equals().

Alexey Korobov Уровень 19

20 декабря 2020

Реально полезная статья. Спасибо автору за труд!

Vyacheslav Уровень 20

17 декабря 2020

Гениальная статья. The best в русскоязычном интернете!

Alexander Уровень 27

10 декабря 2020

И еще. В секции удаление: "если в бакете только один объект (проверяем у него указатель null) сравниваем хеши, ссылки и equals (если вдруг хеши не равны)". Видимо тут имелось ввиду "если вдруг ссылки не равны" ? Если не равны хеши, то никакой equals не вызывается.

Alexander Уровень 27

10 декабря 2020

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

александр Уровень 0

6 декабря 2020

Это реально ооочень класная статья, спасибо добрым людям за такой материал👍

Melkie Kross Уровень 9

25 сентября 2020

Добавлю это в закладки. Вернусь когда вернусь. Спасибо!

Maria Karpikova Уровень 20

21 июля 2020

>external chaining или метод цепочек (реализован в HashMap) — т.е. в ячейке на самом деле содержится список (chain). А уже в списке может содержаться несколько значений (не обязательно с одинаковым хеш-кодом). Разве? Как они попадут в один бакет, если у них разные хэш-коды?

Leonid Уровень 41 Expert

26 июля 2020

Поскольку количество бакетов в мапе слегка меньше, чем диапазон Integer, то для разных хешкодов может оказаться "подходящим" один и то же бакет.

Олег Уровень 31

18 октября 2020

Integer is border in ~4000000000 numbers as well as number of buckets in the hash map, so theoretically we can have more unique objects to store in hash map than range of integer. And in this case even objects with different keys will be store in the same buckets.

Николай Уровень 1

18 июля 2020

Пожалуй, это лучший материал по описанию HashMap, доступный на русском языке.

Daniil Vishnivetsky Уровень 9

5 июня 2020

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

hidden #1691049 Уровень 4

30 июня 2020

почему, на собесах про это всегда спрашивают. надо знать хотя бы принцип работы

Daniil Vishnivetsky Уровень 9

1 июля 2020

я не бывал на собесах ни разу, вы на многих побывали?

hidden #1691049 Уровень 4

11 июля 2020

на десятке может был. и если про хэшмэп не расскажешь (да и вообще про коллекции), дальше даже слушать не будут, ну или так поспрашивают для приличия, в работе откажут 99%

Daniil Vishnivetsky Уровень 9

2 августа 2020

Ну про коллекции понятно, тут я не сомневался, про принцип работы hashmap тоже понятно, но в статье строчка применяется к красно-черному дереву, о нем тоже на собесах спрашивают?

Margarita Уровень 23

15 октября 2020

У меня у знакомого спрашивали

Илья Ненашев Уровень 14

21 октября 2020

его обязательно знать надо?

Адам Уровень 19

28 мая 2020

Тупо пролистал вниз, чтобы посмотреть на размер статьи. Вернусь когда нибудь в будущем и прочитаю.((9(

Владислав Уровень 41

27 июня 2020

Вернешься на уровне этак 34-м :)

Alexandr Mihailovich Уровень 20

4 мая 2020

Спасибо

Sekator Уровень 41

15 апреля 2020

молодец !!!

Кирилл Уровень 35

26 марта 2020

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

stefan Уровень 24

10 марта 2020

>> На вход он принимал хеш-код полученный в результате работы hashCode() и длину внутреннего массива (количество ячеек). А возвращал результат «хеш-код» –> побитовое «И» –> (длина массива – 1). Было бы хорошо добавить, что это остаток от деления полученного hash-кода на количество корзин/групп.

Andrey Andreevich Уровень 11

8 февраля 2020

Почитал статью о мапах, называется. Куча ссылок заставила меня углубиться в это на вечер. Конкретно эта статья довольно доходчива, некоторые хабровские всё же рассчитаны на более опытных джавистов. Спасибо)