HashMap

HashMap — структура данных, одна из коллекций языка Java. Представляет собой хэш-таблицу. Так называется набор из пар «ключ-значение», где у ключей есть хэши, то есть числовые уникальные идентификаторы. Они высчитываются для каждого ключа.

Общее название сущности, которая хранит в себе ключи и значения, — ассоциативный массив. То есть структура данных, похожая на массив, где вместо индексов — ключи. Самый очевидный пример — простая таблица, где заголовок является ключом.

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

Для чего нужен HashMap

HashMap пользуются разработчики на Java. Как и все структуры, относящиеся к коллекциям, он нужен в первую очередь для хранения информации и работы с ней. HashMap быстро работает, и большинство операций в нем выполняется за фиксированное время — это происходит благодаря оптимизированному доступу к данным. Как и практически все структуры из Collections Framework, он динамический, то есть его размер не фиксирован — туда можно добавить практически любое количество объектов.

HashMap используется, когда разработчику нужно хранить где-то пары «ключ-значение», при этом иметь возможность быстро получить значение по ключу. Например, имя пользователя и номер его телефона. Если нужно хранить просто список значений, лучше подойдет ArrayList или похожая структура.

Как устроены хэш-таблицы

HashMap — структура из пар «ключ-значение». Внутри это динамический массив ключей. Каждый элемент массива — своеобразная «корзинка», которая хранит связанный список со значением. О том, что собой представляет каждая из этих сущностей, можно почитать в статьях про ArrayList и коллекции.

Но HashMap используют для хранения пар — на каждый ключ приходится только одно значение. То есть связанный список будет состоять из одного элемента, а ссылаться этот элемент будет на null — специальное «пустое» значение. Если бы в такой структуре значений было несколько, первое ссылалось бы на второе и так далее — так устроен связанный список.

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

Для оптимизации доступа используется хэш ключа. Когда в HashMap добавляют ключ и значение, для ключа сразу высчитывается хэш. По нему определяется позиция в массиве для этой пары: для расчета есть специальные формулы.

Реализация и свойства HashMap

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

У HashMap, как и у всех подобных структур, есть набор своих методов — функций, которые позволяют удобно работать с данными. Для добавления, поиска, перезаписи или удаления элемента есть свои команды; также можно перебирать элементы и ключи и делать многое другое. Благодаря использованию хэшей эти методы работают очень быстро, и для самых популярных из них время выполнения константно, если нет коллизий.

Коллизии и их предотвращение

В идеальной ситуации хэш полностью индивидуален для каждого уникального объекта. Но в реальности хэши могут совпадать у совершенно разных объектов. Это происходит из-за несовершенства существующих алгоритмов.

Может случиться так, что у двух разных ключей окажется одинаковый хэш. Или хэш будет разным, но по формуле позиция для обоих хэшей будет одинаковой. Тогда значения обоих ключей окажутся записаны в одну «корзинку». Это и есть коллизия. Именно из-за коллизий для хранения значений используется связанный список: если бы в массиве просто хранился объект, любая коллизия перезаписала бы текущее значение, а это опасно. А при текущей реализации, даже если случится коллизия, новое значение просто запишется в начало той же «корзинки», не изменив старое.

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

Отличие от перезаписи

HashMap умеет отличать коллизию от реальной перезаписи элемента. Когда структуре дают новую пару «ключ-значение», она проверяет, есть ли в массиве такие хэши и такие ключи. Результат такой:

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

Вы можете узнать больше про структуры данных в Java. Получите новую профессию на курсах и станьте разработчиком на популярном языке.