Что такое коллизия java

What Exactly is Hash Collision

Hash Collision or Hashing Collision in HashMap is not a new topic and I’ve come across several blogs and discussion boards explaining how to produce Hash Collision or how to avoid it in an ambiguous and detailed way. I recently came across this question in an interview. I had lot of things to explain but I think it was really hard to precisely give the right explanation. Sorry if my questions are repeated here, please route me to the precise answer:

1. What exactly is Hash Collision — is it a feature, or common phenomenon which is mistakenly done but good to avoid?
2. What exactly causes Hash Collision — the bad definition of custom class’ hashCode() method, OR to leave the equals() method un-overridden while imperfectly overriding the hashCode() method alone, OR is it not up to the developers and many popular java libraries also has classes which can cause Hash Collision?
3. Does anything go wrong or unexpected when Hash Collision happens? I mean is there any reason why we should avoid Hash Collision?
4. Does Java generate or at least try to generate unique hashCode per class during object initiation? If no, is it right to rely on Java alone to ensure that my program would not run into Hash Collision for JRE classes? If not right, then how to avoid hash collision for hashmaps with final classes like String as key?

I’ll be greateful if you could please share you answers for one or all of these questions.

4 Answers 4

What exactly is Hash Collision — is it a feature, or common phenomenon which is mistakenly done but good to avoid?

It’s a feature. It arises out of the nature of a hashCode: a mapping from a large value space to a much smaller value space. There are going to be collisions, by design and intent.

What exactly causes Hash Collision — the bad definition of custom class’ hashCode() method,

A bad design can make it worse, but it is endemic in the notion.

OR to leave the equals() method un-overridden while imperfectly overriding the hashCode() method alone,

OR is it not up to the developers and many popular java libraries also has classes which can cause Hash Collision?

This doesn’t really make sense. Hashes are bound to collide sooner or later, and poor algorithms can make it sooner. That’s about it.

Does anything go wrong or unexpected when Hash Collision happens?

Not if the hash table is competently written. A hash collision only means that the hashCode is not unique, which puts you into calling equals() , and the more duplicates there are the worse the performance.

I mean is there any reason why we should avoid Hash Collision?

You have to trade off ease of computation against spread of values. There is no single black and white answer.

Does Java generate or atleast try to generate unique hasCode per class during object initiation?

No. ‘Unique hash code’ is a contradiction in terms.

If no, is it right to rely on Java alone to ensure that my program would not run into Hash Collision for JRE classes? If not right, then how to avoid hash collision for hashmaps with final classes like String as key?

The question is meaningless. If you’re using String you don’t have any choice about the hashing algorithm, and you are also using a class whose hashCode has been slaved over by experts for twenty or more years.

Actually I think the hash collision is Normal. Let talk about a case to think. We have 1000000 big numbers(the set S of x), say x is in 2^64. And now we want to do a map for this number set. lets map this number set S to [0,1000000] .

But how? use hash!!

Define a hash function f(x) = x mod 1000000. And now the x in S will be converted into [0,1000000), OK, But you will find that many numbers in S will convert into one number. for example. the number k * 1000000 + y will all be located in y which because (k * 1000000 + y ) % x = y. So this is a hash collision.

And how to deal with collision? In this case we talked above, it is very difficult to delimiter the collision because the math computing has some posibillity. We can find a more complex, more good hash function, but can not definitely say we eliminate the collision. We should do our effort to find a more good hash function to decrease the hash collision. Because the hash collision increase the time cost we use hash to find something.

Simplely there are two ways to deal with hash collision. the linked list is a more direct way, for example: if two numbers above get same value after the hash_function, we create a linkedlist from this value bucket, and all the same value is put the value’s linkedlist. And another way is that just find a new position for the later number. for example, if number 1000005 has took the position in 5 and when 2000005 get value 5, it can not be located at position 5, it then go ahead and find a empty position to took.

For the last question : Does Java generate or at least try to generate unique hashCode per class during object initiation?

the hashcode of Object is typically implemented by converting the internal address of the object into an integer. So you can think different objects has different hashcode, if you use the Object’s hashcode().

Name already in use

JBook / collections / map / hash_map.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

Класс java.util.HashMap является одной из самых популярных и часто используемых реализаций интерфейса java.util.Map . Как уже было сказано во введении, это структура данных, реализующая интерфейс ассоциативного массива. По сути, это набор пар ключ-значение.

Реализация не гарантирует порядок хранения элементов, однако в лучшем случае предоставляет константное время для добавления, удаления, получение и проверку на содержание элемента. Но при условии отсутствия коллизий, т.е хорошо определенной хэш-функции добавляемых элементов. В Java за хэш-функцию отвечает метод hashCode.

Реализация может динамически менять размер и позволяет хранить null значения.

До этого вы уже познакомились с массивами, где обращение к элементу просиходило по индексу. Т.е каждому элементу в массиве соответствует свой номер.

Представьте себе набор пронумерованных корзин, стоящих в ряд. В каждую корзину вы можете положить только одну вещь. Вы кладете обувь на в первую корзину, кофту во вторую и т.д. Грубо говоря, вы уже заранее знаете по какому индексу обращаться к элементу — именно поэтому вы быстро находите нужную вещь.

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

Возвращаясь к примеру с корзинами, представьте, что корзины покрашены в цвета. Добавляя пару вы, с помощью hashCode ключа, понимаете цвет корзины и уже после этого добавляете туда элемент. Т.е hashCode — это цвет, то, в какую корзину вы будете добавлять элемент.

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

Однако, что будет, если произойдет коллизия, т.е hashCode -ы ключей добавляемых элементов совпадут? Как уже было сказано в заметке о hashCode, такое вполне может произойти, особенно, если хэш-функция написана плохо. Элемент будет добавлен, но в таком случае доступ до него уже будет не такой быстрый, так как корзину по цвету мы найдем быстро, а уже в самой корзине надо будет искать нужный элемент.

Это напоминает ситуацию, когда неряшливый человек закидывает в корзину вещи, после чего ему приходится ее разгребать в поисках нужной. Ведь в корзине уже много вещей! И пусть вы знаете, что шапка будет в условной ‘зеленой’ корзине, но там же кроме искомой шапки еще лежит десять других и свитер.

Подобный способ разрешения ситуации с коллизиями элементов называется chaning. Существует еще также и метод открытой адресации, однако в java.util.HashMap за реализацию взят именно chaining .

Поэтому коллизии серьезно влияют на производительность java.util.HashMap .

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

Объявление выглядит как:

Это, наверное, один из самых больших по размеру классов в стандартной библиотеке Java , поэтому полностью его приводить не имеет смысла. Разберем только самые важные компоненты.

Заметьте, что реализуются интерфейсы-маркеры java.lang.Cloneable и java.io.Serializable . Т.е структура данных поддерживает clone (но помните о подводных камнях такого подхода) и сериализацию.

Количество хранящихся пар содержится в переменной size :

Важно понимать, что size — это не размер ассоциативного массива (не количество корзин), это именно количество хранящихся элементов.

Как уже было сказано выше, java.util.HashMap — это массив пар ключ-значение.

Вопрос:

Возникает вопрос: что такое Node и зачем он нужен?

Ответ:

В случае полного отсутствия коллизий хватило бы простого массива, так как каждый элемент находился бы в своей ячейке. Но коллизии неизбежны и возможны даже при очень хорошей хэш-функции. А при коллизии два элемента попадали бы в одну ячейку. Именно поэтому table — это не просто массив, а массив корзин, buckets.

Так вот то, как такая корзина устроена и есть Node . Каждая корзина — это связный список.

Класс Node объявлен в java.util.HashMap , т.е. является вложенным:

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

Если не указать размер массива table , то при создании объекта java.util.HashMap будет создан массив размером 16 . Это значение по-умолчанию, которое хранится в константе DEFAULT_INITIAL_CAPACITY .

Можно указать размер при создании объекта списка воспользовавшись конструктором и передав туда значение желаемого размера:

Однако надо помнить, что массив создается не в конструкторе, а в момент первого добавления элемента.

Точно также, как и в java.util.ArrayList, массив динамически расширяем. Решение, когда расширять массив, принимается на основании достижения предельного значения threshold :

Значение threshold рассчитывается по формуле:

По-умолчанию этот коэффициент равен:

Разумеется, как и в java.util.ArrayList , этот параметр можно задать через конструктор:

Логично, что эти параметры не могут принимать отрицательные значения, а также выходить за рамки максимально допустимой величины:

Теперь перейдем к разбору реализаций основных методов.

За добавление в java.util.HashMap отвечает метод put :

Как видно из описания, результат выполнения метода — это значение, которое ранее ассоциировалось по этому ключу и null , если по такому ключу значений не было, либо значение по такому ключу было null .

Перед добавлением элемента сначала происходит вычисление hashCode ключа:

Как видно из JavaDoc метода, это сделано для того, чтобы распределение по корзинам было более равномерным. Если коротко, то без этих дополнительных манипуляций маленькие значения java.lang.Integer , java.lang.Float и т.д. будут раскладывать значения в первые несколько корзин, что серьезно ухудшит производительность.

Теперь детально рассмотрим само добавление:

После того, как hashCode ключа вычислен, рассчитывается индекс корзины, ячейки в массиве, куда будет добавлен элемент. Возвращаясь к примеру с аналогиями на основании полученного hashCode надо понять цвет корзины, в которую мы положим наш добавляемый предмет.

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

Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Мы открываем корзину!

Если в корзине пусто, то просто добавляется элемент.

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

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

До Java 8 среднее время работы для операций удаления и проверки на содержание будет O(1 + a) , где a — коэффициент возникновения коллизий. Поэтому, в случае постоянных коллизий java.util.HashMap вырождаелась в связный список с доступом до элемента за O(N) .

Начиная же с Java 8 был переработан механизм работы с коллизиями.

При частых коллизиях все преимущества по производительности java.util.HashMap сводятся на нет. До Java 8 каждая корзина представляла собой связный список. Однако после Java 8 это уже не всегда так.

Т.е идет обход списка и подсчет binCount , который отвечает за количество элементов в корзине. Если это значение становится большим или равным TREEIFY_THRESHOLD , то будет вызван метод treeifyBin .

Это количество элементов в одной корзине, при достижении которого внутренний связный список будет преобразован в красно-черное дерево. Метод treeifyBin как раз и занимается тем, что производит это преобразование.

Заметим, что если количество элементов в java.util.HashMap меньше MIN_TREEIFY_CAPACITY , то дерево строится не будет, а все обойдется resize -ом, т.е увеличением размера и перестроением хэш-таблицы.

Т.е, если в хэш-таблице меньше 64 корзин, то даже при частых коллизиях преобразование к дереву происходить не будет, хэш-таблица будет увеличена и элементы перераспределены по новым корзинам.

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

Именно поэтому рекомендуется, чтобы ключи реализовывали интерфейс java.lang.Comparable. Интерфейс необходим для сравнения элементов и построения дерева.

В случае, если ключи не реализуют интерфейс java.lang.Comparable , дерево будет строится на основании System.identityHashCode() .

Обратите внимание, что после перестроения корзины в красно-черное дерево класс, хранящий значение уже не Node , а TreeNode :

Благодаря этому, начиная с Java 8+ производительность java.util.HashMap в худшем случае не O(n) , а O(log n) .

За удаление элемента по ключу отвечает метод remove :

Метод возвращает предыдущее значение по удаляемому ключу или, если элемент не был найден, null .

Здесь также расситывается hashCode , для вычисления того, из какой корзины удалять элемент.

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

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

Точно также как и в java.util.ArrayList, при удалении элементов количество корзин не меняется. И если в java.util.ArrayList предусмотрен метод trimToSize() , то в java.util.HashMap таких методов нет.

Один из способов, если вам необходимо это сделать, это воспользоваться конструктором java.util.HashMap и создать на основе текущей новую структуру данных.

Еще интересно ответить на следующий вопрос.

Вопрос:

Можно ли потерять элемент в java.util.HashMap ?

Ответ:

Да, это возможно. Но при условии, что изменится ключ, а значит изменится и его hashCode .

Рассмотрим ситуацию, когда ключом является класс:

Далее воспроизведем следующий пример:

Результатом работы будет:

Т.е добавили по ключу элемент. Вспомните, как добавляется элемент: по hashCode ключа определяется та корзина, в которую будет происходить добавление. Например, пусть будет так, что по ключу было определено, что элемент должен добавиться в первую корзину.

После чего ключ изменили, а значит его hashCode теперь дает другое значение. Следовательно, при попытке обращения по ключу с новым значением будет уже вычисляться другое значение корзины. Т.е по новому hashCode измененного ключа будет выходить так, что элемент надо искать, например, в четвертой корзине. Но там то ничего нет! А при попытке доступа по старому значению ключа корзина будет вычисляться верно, но поиск ключа по equals не найдет совпадений и значение также нельзя будет получить.

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

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

Вопрос:

Можно ли использовать массив в качестве ключа у java.util.HashMap ?

Ответ:

Так как hashCode массива не зависит от хранимых в нем элементов, а присваивается при создании массива, а также потому, что у массивов не переопределен equals и сравнение идет по ссылке, то использовать массивы в качестве ключей не рекомендуется!

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

Все методы java.util.HashMap — не синхронизированы. Поэтому добавление из различных потоков в такой список строго не рекомендуется.

Если необходима concurrent -реализация java.util.HashMap , то стоит воспользоваться java.util.ConcurrentHashMap.

В Java также существует класс утилит java.util.Collections , предоставляющих статические методы для преобразования в concurrent структуру данных:

Но тут есть подводный камень.

Посмотрим на метод:

Дело в том, что Collections.synchronizedMap(. ) не создает java.util.ConcurrentHashMap . Все, что делает метод synchronizedMap — это оборачивает реализацию java.util.Map в SynchronizedMap :

, где методы синхронизованы на java.lang.Object . Грубо говоря, это превращает java.util.HashMap в java.util.HashTable . А это серьезно снижает производительность. В то время, как java.util.ConcurrentHashMap отличается во внутренней структуре для хранения пар key-value и более производительна в многопоточной среде.

В целом, я бы не использовал Collections.synchronizedMap(. ) , разве что необходимо синхронизировать небольшую по объему структуру и производительность не важна.

Благодаря тому, что в основе реализации лежит массив, java.util.HashMap предоставляет доступ к элементам за константное время. Но при условии отсутствия коллизий, т.е хорошо определенной хэш-функции добавляемых элементов.

В худшем случае при постоянных коллизиях все элементы будут попадать в одну корзину, что в свою очередь вырождает java.util.HashMap в красно-черное дерево и ухудшает производительность до O(log(N)) .

Желательно, чтобы ключ реализовывал интерфейс java.lang.Comparable , иначе дерево будет строится по System.identityHashCode() .

Структура данных java.util.HashMap это коллекция пар ключ-значение. Это высокопроизводительная коллекция, но требующая хорошей реализации методов hashCode и equals у ключа.

Ключи и значения могут быть любых типов, в том числе и null . Для хранения примитивных типов используются соответствующие классы-оберки.

Важно, чтобы ключ был неизменяемым объектом, в противном случае возможны ситуации, когда значение по ключу будет потеряно.

Внутренняя работа HashMap в Java

[примечание от автора перевода] Перевод был выполнен для собственных нужд, но если кому -то это окажется полезным, значит мир стал хоть немного, но лучше! Оригинальная статья — Internal Working of HashMap in Java

В этой статье мы увидим, как изнутри работают методы get и put в коллекции HashMap. Какие операции выполняются. Как происходит хеширование. Как значение извлекается по ключу. Как хранятся пары ключ-значение.

Как и в предыдущей статье, HashMap содержит массив Node и Node может представлять класс, содержащий следующие объекты:

1. int — хэш
2. K — ключ
3. V — значение
4. Node — следующий элемент

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

Хэширование

Хэширование -это процесс преобразования объекта в целочисленную форму, выполняется с помощью метода hashCode(). Очень важно правильно реализовать метод hashCode() для обеспечения лучшей производительности класса HashMap.

Здесь я использую свой собственный класс Key и таким образом могу переопределить метод hashCode() для демонстрации различных сценариев. Мой класс Key:

Здесь переопределенный метод hashCode() возвращает ASCII код первого символа строки. Таким образом, если первые символы строки одинаковые, то и хэш коды будут одинаковыми. Не стоит использовать подобную логику в своих программах.

Этот код создан исключительно для демонстрации. Поскольку HashCode допускает ключ типа null, хэш код null всегда будет равен 0.

Метод hashCode()

Метод hashCode() используется для получения хэш кода объекта. Метод hashCode() класса Object возвращает ссылку памяти объекта в целочисленной форме (идентификационный хеш (identity hash code)). Сигнатура метода public native hashCode() . Это говорит о том, что метод реализован как нативный, поскольку в java нет какого -то метода позволяющего получить ссылку на объект. Допускается определять собственную реализацию метода hashCode(). В классе HashMap метод hashCode() используется для вычисления корзины (bucket) и следовательно вычисления индекса.

Метод equals()

Метод equals используется для проверки двух объектов на равенство. Метод реализованн в классе Object. Вы можете переопределить его в своем собственном классе. В классе HashMap метод equals() используется для проверки равенства ключей. В случае, если ключи равны, метод equals() возвращает true, иначе false.

Корзины (Buckets)

Bucket -это единственный элемент массива HashMap. Он используется для хранения узлов (Nodes). Два или более узла могут иметь один и тот -же bucket. В этом случае для связи узлов используется структура данных связанный список. Bucket -ы различаются по ёмкости (свойство capacity). Отношение между bucket и capacity выглядит следующим образом:

Один bucket может иметь более, чем один узел, это зависит от реализации метода hashCode(). Чем лучше реализованн ваш метод hashCode(), тем лучше будут использоваться ваши bucket -ы.

Вычисление индекса в HashMap

Хэш код ключа может быть достаточно большим для создания массива. Сгенерированный хэш код может быть в диапазоне целочисленного типа и если мы создадим массив такого размера, то легко получим исключение outOfMemoryException. Потому мы генерируем индекс для минимизации размера массива. По сути для вычисления индекса выполняется следующая операция:

где n равна числу bucket или значению длины массива. В нашем примере я рассматриваю n, как значение по умолчанию равное 16.

• изначально пустой hashMap: здесь размер hashmap равен 16:

HashMap:

• вставка пар Ключ — Значение: добавить одну пару ключ — значение в конец HashMap

Вычислить значение ключа <"vishal">. Оно будет сгенерированно, как 118.

Вычислить индекс с помощью метода index , который будет равен 6.

Создать объект node.

Поместить объект в позицию с индексом 6, если место свободно.

Теперь HashMap выглядит примерно так:

• добавление другой пары ключ — значение: теперь добавим другую пару

Вычислить значение ключа <"sachin">. Оно будет сгенерированно, как 115.

Вычислить индекс с помощью метода index , который будет равен 3.

Создать объект node.

Поместить объект в позицию с индексом 3, если место свободно.

Теперь HashMap выглядит примерно так:

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

Вычислить значение ключа <"vaibhav">. Оно будет сгенерированно, как 118.

Вычислить индекс с помощью метода index , который будет равен 6.

Создать объект node.

Поместить объект в позицию с индексом 6, если место свободно.

В данном случае в позиции с индексом 6 уже существует другой объект, этот случай называется коллизией.

В таком случае проверям с помощью методов hashCode() и equals(), что оба ключа одинаковы.

Если ключи одинаковы, заменить текущее значение новым.

Иначе связать новый и старый объекты с помощью структуры данных «связанный список», указав ссылку на следующий объект в текущем и сохранить оба под индексом 6.

Теперь HashMap выглядит примерно так:

[примечание от автора перевода] Изображение взято из оригинальной статьи и изначально содержит ошибку. Ссылка на следующий объект в объекте vishal с индексом 6 не равна null, в ней содержится указатель на объект vaibhav.

• получаем значение по ключу sachin:

Вычислить хэш код объекта <“sachin”>. Он был сгенерирован, как 115.

Вычислить индекс с помощью метода index , который будет равен 3.

Перейти по индексу 3 и сравнить ключ первого элемента с имеющемся значением. Если они равны -вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.

В нашем случае элемент найден и возвращаемое значение равно 30.

• получаем значение по ключу vaibahv:

Вычислить хэш код объекта <"vaibhav">. Он был сгенерирован, как 118.

Вычислить индекс с помощью метода index , который будет равен 6.

Перейти по индексу 6 и сравнить ключ первого элемента с имеющемся значением. Если они равны -вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.

В данном случае он не найден и следующий объект node не равен null.

Если следующий объект node равен null, возвращаем null.

Если следующий объект node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект node не будет равен null.

Изменения в Java 8

Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных «связанный список» и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).

Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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