Как работает HashMap в Java

Большинство из вас согласятся, что HashMap, на сегодняшний день, является самой любимой темой для дискуссий на собеседованиях. Иногда я проводил подобные дискуссии со своими коллегами и это действительно помогло. Теперь я проведу такую дискуссию с вами.
Я полагаю, что если вы интересуетесь внутренним устройством и работой HashMap, то вы уже знакомы с основами HashMap, поэтому я пропущу эту часть. Но если вы новичок в этом деле, советую вам проследовать на сайт Java Docs.
Прежде чем мы двинемся дальше, я настоятельно рекомендую вам ознакомится с моей предыдущей статьей: Работа с hashCode и методом equals в Java.

Содержание данной статьи:

  1. Единственный возможный ответ.
  2. Что такое Хеширование.
  3. Немного о классе Entry.
  4. Что делает метод put().
  5. Как работает метод get().
  6. Примечания


Единственный возможный ответ


Если кто-нибудь попросит меня объяснить «Как работает HashMap?», я просто отвечу: «По принципам Хеширования». Проще некуда. Чтобы понять это и получить расширенный ответ, надо быть уверенным, что вы знаете основы Хеширования. Правильно?

Что такое Хеширование


Хеширование в простейшем представлении, это – способ преобразования любой переменной/объекта в уникальный код после применения любой формулы/алгоритма к их свойствам. Настоящая функция хеширования, должна следовать следующему правилу:

Хеш-функция должна возвращать одинаковый хеш-код всякий раз, когда она применена к одинаковым или равным объектам. Другими словами, два одинаковых объекта должны возвращать одинаковые хеш-коды по очереди.

Примечание: Все объекты в java наследуют стандартную реализацию hashCode() функции, описанной в классе Object. Эта функция возвращает хеш-код полученный путем конвертации внутреннего адреса объекта в число, что ведет к созданию уникального кода для каждого отдельного объекта.

Больше об этом вы можете прочитать здесь: Работа с hashCode и методом equals в Java

Немного о классе Entry


Карта(map) по определению, это – «Объект хранящий попарно значения(values) и ключи(keys)». Довольно просто, да?

Значит, в HashMap должен быть какой-то механизм хранящий пары Значений и Ключей? Ответ – Да. HashMap имеет внутренний класс Entry, который выглядит так:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной код тут…
}


Естественно класс Entry имеет Ключ и Значение хранящиеся, как атрибуты. Ключ помечен как final и еще мы видим два дополнительных поля: next и hash. Мы постараемся понять назначение этих полей по ходу статьи.

Что делает метод put().


Прежде чем мы углубимся в реализацию метода put(), очень важно понять, что экземпляры класса Entry хранятся в массиве. Класс HashMap определяет эту переменную как:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть 
* кратна двум!
*/
    transient Entry[] table;


Теперь взгляните на код реализации метода put():

/**
* Связывает определенное значение с определенным ключом в этой карте(map). 
* Если карта перед этим содержала значение для данного ключа, это значение 
* заменится на новое.  
*
* @param key
*            ключ с которым указанное значение должно быть связано.
* @param value
*            значение которое должно быть связано с ключом.
* @return вернет предыдущее значение связанное с key, или null
*         если не было значений связанных с key. (Вернет null 
*         так же, если перед этим key был связан со значением null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
 
modCount++;
addEntry(hash, key, value, i);
return null;
}


Давайте разберемся с этим шаг за шагом:

— Первым делом, проверяем существует ли ключ. Если ключ не существует (null), значение помещается в таблицу на нулевую позицию, потому что хеш-код для значения null, это – всегда 0.

— На следующем шаге, рассчитывается хеш-значение используя хеш-код ключа, получаемый вызовом метода hashCode(). Это хеш-значение используется для вычисления позиции в массиве, куда будет помещен объект Entry. Дизайнеры JDK предполагали, что плохо написанная функция hashCode() может вернуть слишком высокое или слишком низкое значение хеш-кода. Для решения этой проблемы, они ввели другую hash() функцию, и передали в нее значение хеш-кода объекта, чтобы привести хеш-значение в соответствие с размером массива.

— Теперь вызывается функция indexFor(hash, table.length), для вычисления точной позиции, куда будет помещен объект Entry.

— Здесь начинается главная часть. Теперь, исходя из того, что нам известно, что – два не равных объекта могут иметь равные значения хеш-кодов, зададим вопрос: Будут ли два разных объекта помещаться в одинаковую позицию в массиве [корзина]?
Ответом является LinkedList. Если вы помните, класс Entry имеет атрибут «next». Этот атрибут всегда указывает на следующий объект в цепи. Это в точности соответствует поведению LinkedList.

Итак, объекты Entry хранятся в форме LinkedList. Когда объект Entry должен быть помещен в определенное место, HashMap проверяет нет ли уже в этом месте записи. Если записи нету, то объект помещается в данную позицию.
Если все же в данной позиции уже есть объект, проверяется следующий атрибут. Если он возвращает null и текущий объект Entry становится следующим звеном в LinkedList. Если следующая переменная не null, процедура повторяется для следующей, пока не найдет null.

Что если мы поместим другой объект с другим значением но с тем же ключом, что был ранее? Логически это должно привести к замене старого значения. Как это происходит? В общем, после определения позиции объекта Entry, во время прохода по LinkedList до расчетной позиции, HashMap вызывает метод сравнения ключа для каждого объекта Entry. Все эти Entry объекты в LinkedList могут иметь аналогичные хеш-коды, но метод equals() проверит их на истинное сходство. Это приведет к замене значения только внутри объекта Entry.

Таким образом HashMap гарантирует уникальность всех ключей.

Как работает метод get()


Теперь мы имеем представление, о том, как пары ключ-значение хранятся в HashMap. Следующим большим вопросом будет: Что происходит, когда объект передается из HashMap в метод get()? Как определяется значение объекта?

Ответ мы уже должны знать, потому что способ которым определяется уникальность ключа в методе put() имеет ту же логику, которую применяет метод get(). Как только HashMap определяет ключ объекта переданного в аргументе, он просто возвращает значение соответствующего объекта Entry.

Если же совпадений не найдено, метод get() вернет null.

Давайте взглянем на код:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

Код выше подобен методу put() до этого места if (e.hash == hash && ((k = e.key) == key || key.equals(k))), После этого просто возвращает значение объекта.

Примечания


1. Структура данных для хранения в объекте Entry это массив с именем table и типом Entry.
2. Каждая индивидуальная позиция в массиве называется корзина, потому что она может содержать первый элемент LinkedList объектов Entry.
3. hashCode() Ключа требуется для вычисления позиции объекта Entry.
4. equals() Ключа используется для проверки уникальности ключа в карте(map).
5. hashCode() и equals() Значения не используется в методах get() и set() в HashMap.
6. Хеш-код для ключей со значением null это всегда 0. И такой объект Entry всегда будет храниться в нулевой позиции массива.


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

Счастливого обучения!

16 комментариев

Sant9Iga
оооо вот это очень интересная статья. спасибо
GeorgeThreeD
Переведена по просьбам трудящихся=) Пожалуйста=)
Anton_n
Прочтя эту статью и найдя вот эту картинку anbuwrites.files.wordpress.com/2010/09/image003.jpg я наконец-то понял (хотя бы смутно) как это работает :)
Kiba-From-North
Спасибо. Картинка все объяснила. В статье не особо понятно написано.
Igor_Odessa
Уже который час разбираюсь с данной темой. Возник вопрос по картинке и примечании в статье п.6
6. Хеш-код для ключей со значением null это всегда 0. И такой объект Entry всегда будет храниться в нулевой позиции массива.
На картинке же в нулевой позиции массива хранится объект Entry с клюём «ANT». Хеш-код ключа «ANT» ведь не равен 0?
Как это понимать? Почему такие противоречия? Заранее спасибо тому кто сможет разъяснить этот парадокс.
Sant9Iga
в мапе есть корзины пронумерованные. каждой корзине соответствует определенный отрезок int-a. в 0 корзине лежат все пары хэшкод ключей которых лежит в промежутке от 0 до n, где n зависит от размера мапы
Igor_Odessa
ув. Sant9Iga, огромное спасибо за ответ, но всё же до меня не доходит. Если я Вас правильно понял выходит, что примечание верно и рисунок. Можно для тех, кто в бронетранспортёре поподробнее. Если есть такая возможность, визуально отобразить, где всё же на этом рисунке будет отображён Entry с клюём «Null»? И как n зависит от размера мапы? И что значит отрезок int-a? Заранее спасибо за уделённое внимание.
Sant9Iga
Замечательная статья.
почитай замечательную статью. если что то будет непонятно после прочтения — пиши в скайп
forza
  • forza
  • 0
  • Комментарий отредактирован 2016-03-28 18:17:19 пользователем forza
Привет. Из статьи следует, что если в bucket уже есть объекты, новый объект помещается в конец LinkedList при вызове метода put(). Однако здесь и здесь говорится, что новый объект помещается в начало LinkedList.
P.S. Не нашел ссылки на оригинал. Можно ли ее как-нибудь получить?
sheyl
Гораздо логичнее добавлять в начало LinkedList, т.к. в этом случае отсутствует необходимость изменять значение 'next' для предыдущего элемента цепочки, как если бы это пришлось делать при добавлении в конец листа.
SteFFun
  • SteFFun
  • 0
  • Комментарий отредактирован 2016-09-29 11:14:43 пользователем SteFFun
Автор статьи, поправьте меня если я не прав. В методе put в строке:
<code>for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;</code>
а именно Entry<тут должно быть K а не k>, ибо как я понимаю K означает дженерик в объекте Entry, а k ссылка типа Object. Я посмотрел реализацию этого метода в доках и там так, как я и описал. Может для кого-то это мелочь и он так все понимает, но я перечитывая эту статью n раз и пытаясь понять суть работы HashMap, осознал что такой нюанс меня очень сбил с толку при разборе этого метода. Тоже самое с методом get.
SaltToTaste
А может кто объяснить значимость коэффициента loadfactor? В статье о нем не написано, но разобраться хотелось бы.
riko
Он определяет степень загруженности корзин, т.е. максимальное соотношение количества элементов хранимых в мапе и длины массива (количества корзин), после достижения которого длина массива удваивается.
IceBlade
static class Node<K,V> implements Map.Entry<K,V> — сейчас используется массив Нодов.
lichMax
А перевода той статьи про хеш-коды и equals нет?
Sambalinski
Не понял вот что: В примечании 5 написано:
5. hashCode() и equals() Значения не используется в методах get() и set() в HashMap.
Но в методе get есиь такая сторока под номеров 3:
int hash = hash(key.hashCode());
и такая под номером 6:
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
Получается, что и hashCode и equals всё-таки используются? Или я чего-то не уловил?
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.