Большинство из вас согласятся, что 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. Мы постараемся понять назначение этих полей по ходу статьи.

Что делает Java метод 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гарантирует уникальность всех ключей.

Как работает Java метод 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))), После этого просто возвращает значение объекта.

Примечания

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