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

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

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

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

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

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

Хеширование в простейшем представлении, это – способ преобразования любой переменной/an object в уникальный code после применения любой формулы/алгоритма к их свойствам. Настоящая функция хеширования, должна следовать следующему правилу: Хеш-функция должна возвращать одинаковый хеш-code всякий раз, когда она применена к одинаковым or равным an objectм. Другими словами, два одинаковых an object должны возвращать одинаковые хеш-codeы по очереди. Больше об этом вы можете прочитать здесь: Работа с hashCode и методом equals в Java

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

Карта(map) по определению, это – «Объект хранящий попарно значения(values) и ключи(keys)». Довольно просто, да? Значит, в HashMap должен быть Howой-то механизм хранящий пары Значений и Ключей? Ответ – Да. HashMap имеет внутренний класс Entry, который выглядит так:

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

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

What делает Java метод put()

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

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

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

/**
* Связывает определенное meaning с определенным ключом в этой карте(map). 
* Если карта перед этим содержала meaning для данного ключа, это meaning 
* заменится на новое.  
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null 
*         так же, если перед этим key был связан со meaningм 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), meaning помещается в таблицу на нулевую позицию, потому что хеш-code для значения null, это – всегда 0.


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


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


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

Итак, an objectы Entry хранятся в форме LinkedList. Когда an object Entry должен быть помещен в определенное место, HashMap проверяет нет ли уже в этом месте записи. Если записи нету, то an object помещается в данную позицию. Если все же в данной позиции уже есть an object, проверяется следующий атрибут. Если он возвращает null и текущий an object Entry становится следующим звеном в LinkedList. Если следующая переменная не null, proceduresа повторяется для следующей, пока не найдет null. What если мы поместим другой an object с другим meaningм но с тем же ключом, что был ранее? Логически это должно привести к замене старого значения. Как это происходит? В общем, после определения позиции an object Entry, во время прохода по LinkedList до расчетной позиции, HashMapвызывает метод сравнения ключа для каждого an object Entry. Все эти Entry an objectы в LinkedList могут иметь аналогичные хеш-codeы, но метод equals()проверит их на истинное сходство. Это приведет к замене значения только внутри an object Entry. Таким образом HashMapгарантирует уникальность всех ключей.

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

Теперь мы имеем представление, о том, How пары ключ-meaning хранятся в HashMap. Следующим большим вопросом будет: What происходит, когда an object передается из HashMap в метод get()? Как определяется meaning an object? Ответ мы уже должны знать, потому что способ которым определяется уникальность ключа в методе put() имеет ту же логику, которую применяет метод get(). Как только HashMap определяет ключ an object переданного в аргументе, он просто возвращает meaning соответствующего an object Entry. Если же совпадений не найдено, метод get() вернет null. Давайте взглянем на code:

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))), После этого просто возвращает meaning an object.

Примечания

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

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