GeorgeThreeD
8 уровень

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

Пост из группы Архив info.javarush.ru
2599 участников
Большинство из вас согласятся, что 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 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 (Entrye=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 всегда будет храниться в нулевой позиции массива. Я надеюсь, что корректно передал свои мысли в этой статье. Если вы нашли ошибки или у вас имеются вопросы, пожалуйста оставляйте их в комментариях. Счастливого обучения!