класс HashMap

Home » Collections » класс HashMap
Collections, Map Комментариев нет

HashMap

Основные особенности:

  1. Map – отображение(некоторые называют картой или картотекой)
  2. В HashMap отсутствует порядок и, как следствие ее нельзя сортировать.
  3. Все ключи в коллекции уникальны(хешкоды должны быть уникальными, случай, когда хеш-функций создает дубликат уже существующего ключа называется коллизией. См. “Зачем переопределять hashCode() и equals()?”)
  4. Значения в коллекции могут быть равны и содержать null
  5. При записи нового значения в уже существующий ключ, старое значение просто перетирается новым******
  6. Пары ключ-значение именуются записями(Entry). (Map имеет вложенный интерфейс Entry)
  7. Места под записи именуются баккетами.****
  8. Размер HashMap поэтапно увеличивается при добавлении в нее определенного количества элементов, данное увеличение можно настроить.
  9. Операции get() и put() сравнительно быстры
  10. Производительность операции итерации пропорциональна количеству элементов и емкости т.е. iterationTime ~ (capacity + mappings num)
  11. HashMap как и Map не является потомком Collection, а следовательно не имплементирует интерфейса Iterable(чтобы перебрать ее с помощью foreach()), также для нее нельзя получить Iterator. Для перебора элементов коллекции используются методы keySet()(получаем список ключей) entrySet(получаем список записей)
  12. HashMap может служить реализацией многомерного ассоциативного массива*******

Структура данных

hash_map

Термины:

entry – запись, используется
“[…]When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.[…]”
“[…]The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.[…]”

mapping – отображение, в документации используется как заполненная entry, – пара: ключ-значение.
“[…]entrySet() […] Returns a Set view of the mappings contained in this map.[…]”
“[…]The set supports element removal, which removes the corresponding mapping from the map[…]”
“[…] Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings).[…]”
“[…] If many mappings are to be stored in a HashMap instance, creating it with a sufficiently large capacity will allow the mappings to be stored more efficiently than letting it perform automatic rehashing as needed to grow the table. […]”
“[…](A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.[…]”

Поля:

table – массив записей (Enrty[]), хранилище ссылок на цепочки значений
capacity -вместимость(количество баккетов)(initial capacity – исходная вместимость(количество баккетов))***
threshold – предельная вместимость, при достижении максимального количества элементов, размер таблицы увеличивается в два раза.(threshold = capacity * loadFactor)
loadFactor – коэффициент заполнения, чем меньше – тем меньше время доступа к элементам, чем больше – тем больше объем хранимых данных(0.75 по умолчанию), регулируя данный коэффициент можно настраивать HashMap под свои потребности.
size – текущее количество элементов.

Конструкторы HashMap:

HashMap() – Создает HashMap с Capacity = 16 loadFactor=0.75
HashMap(int initialCapacity) – Создает HashMap с loadFactor=0.75
HashMap(int initialCapacity, float loadFactor) – Создает HashMap с указанными параметрами
HashMap(Map extends K,? extends V> m) – Создает HashMap с параметрами Map-аргумента

Важные методы

clone() – создает поверхностную копию коллекции, сами ключи и значения не клонируются.
keySet() – получение списка ключей
entrySet() – получение списка записей

По возможности дословный перевод Javadocs. So, RTFM!

(иногда я перевожу Map, как картотеку(в блоге А.Климова нашел такое сравнение, и оно мне пришлось по душе. Ибо оно образно совпадает с сутью Map), в общем случае – отображение)

Реализация хеш-таблицы Map-интерфейса. Эта реализация разрешает null-ключи и null-значения. HashMap – это грубый эквивалент хеш-таблицы, несинхронизованный и разрешающий null-ы. Класс не гарантирует сохранения порядка последовательности элементов(ни порядка как в Map-аргументе одного из конструкторов, ни сохранения порядка последовательности от вызова к вызову).*****

Данная реализация обеспечивает неизменность производительности базовых get() и put() операций, за счет того, что hash-функция “раскладывает” элементы по баккетам.****
Итерация по коллекции, требует количество времени прямо пропорциональное сумме вместимости(capacity – количества баккетов) экземпляра HashMap и его размера (size – количества сопоставлений ключ-значение). То есть, чем больше вместимость и размер, тем дольше проходит итерация.
Таким образом, очень важно не устанавливать исходную вместимость слишком высокой(или коэффициент загрузки – слишком низким), если важна производительность итераций.

Экземпляр HashMap имеет два параметра затрагивающих его производительность. Исходную вместимость и коэффициент заполнения. Вместимость(capacity) – это количество баккетов в хеш-таблице (исходная вместимость(initial capacity) -количество баккетов на момент создания таблицы). Коэффициент заполнения – это показатель того, насколько должна быть заполнена таблица, прежде чем ее вместимость не будет автоматически увеличена(добавлены баккеты). Как только количество записей в хеш-таблице превысит произведение фактора загрузки на вместимость(threshold = capacity * loadFactor), хеш-таблица рехешируется(перестраиваются структуры данных) так, что в ней становится примерно в два раза больше баккетов.

По большей части, значение коэффициента заполнения по умолчанию(0.75) предлагает хороший вариант компромисса между затратами по быстродействию и по потреблению памяти. Более высокие значения коэффициента уменьшают потребление памяти(таблица использует больше баккетов из своих резервов, перед тем как “попросить” новые) но увеличивают стоимость операции поиска(что в конечном счете отражается на большинстве операций с HashMap, включая get() и put()). Во время выбора значения исходной вместимости необходимо брать во внимание ожидаемое количество записей в картотеке и ее коэффициент заполнения, чтобы минимизировать количество операций по рехешированию. Если исходная вместимость больше максимального количества записей отделенных фактором загрузки, рехеширование никогда не запустится[этот момент, в последнем предложении мне не показался понятным а показался нелогичным(наверное трудности перевода), если кто знает – напишите в комментариях, что вы думаете по поводу последнего предложения].*

Если в HashMap планируется хранить много записей(key-value mappings), необходимо сразу создавать ее с достаточно большой величиной вместимости, это будет более эффективно, так как не будет лишний раз заставлять проводить рехеширование.

Имплементация HashMap – не синхронизирована. Если потоки конкурируют за получение доступа к картотеке и по крайней мере один из них изменяет данные, необходимо синхронизировать доступ к HashMap извне. (Структурное изменение данных – это любая операция по добавлению или удалению записей; простое изменение значения, связанное с ключом уже имеющимся в наличии – не является структурным изменением.) Обычно, этого можно добиться просто инкапсулируя HashMap в объект-оболочку. Если таких объектов нет, можно “завернуть” HashMap используя метод Collections.synchronizedMap(). Этот способ отлично подходит для предотвращения случайного асинхронного доступа к HashMap.

Итераторы, возвращаемые всеми методами просмотра коллекций(“collection view methods”)- быстро падающие(fail-fast). Если отображение структурно изменено после того как создан итератор, независимо от того пытается ли итератор что-нибудь удалить, итератор выбросит ConcurrentModificationException. Таким образом, перед лицом опасности изменения конкурентом, итератор падает быстро и чисто, не рискуя произвольным недетерминируемым поведением программы в неопределенное время в будущем.**

Однако, следует отметить, что такое поведение – быстрое падение итератора не может быть гарантировано, так как оно есть, общими словами, невозможно железно гарантировать, что несинхронизированный конкурент все же не произведет какое-либо изменение. Быстро падающие итераторы, просто прилагают максимальные усилия для выброса исключения ConcurrentModificationException. Поэтому, неправильным подходом было бы писать программу основанную на работе этого исключения, ибо это исключение следует использовать только для того, чтобы ловить баги.

Примечания

*Если установить коэффициент заполнения равным 1, то количество записей, до рехеширования будет равным вместимости, то есть таблица будет заполняться полностью прежде чем получить новые баккеты. Число возможных коллизий(одинаковых ключей) статистически вырастет, а следовательно вырастет и время поиска, так как в одном баккете будет больше одной подходящей записи, ключи которых дополнительно будут проверяться на равенство.

**fail-fast system – быстро-падающая система, система чутко реагирующая на сбои и на ситуации ведущие к сбою программы и немедленно “падающая” и сообщающая о проблемах. В java, есть пример с коллекциями: если один поток перебирает коллекцию, а другой в это время пытается ее структурно модифицировать, выбрасывается исключение Concurrent Modification Exception.
Fail Fast – часть концепции Fail Early, Fail Fast, Fail Often, Fail Cheap.

***при создании пустой HashMap сразу создается место под 16 записей(Entry)

****bucket -ведерко(англ.). Если называть Map картотекой, то Bucket – это карточка, заполненная(с каким-то значением в Entry) или пустая(null).

*****”Хеш-таблицы обладают самой высокой скоростью среди всех структур данных[…]используются когда программе приходится проверять тысячи слов или символьных последовательностей за долю секунды[…]не чувствительны к упорядоченности вставляемых данных, поэтому они могут использоваться вместо сбалансированных деревьев. По простоте программирования они значительно превосходят сбалансированные деревья[…]использование хеш-таблиц сопряжено с дополнительными затратами памяти, особенно при открытой адресации. Также объем хранимых данных должен быть относительно точно известен заранее, потому что в качестве базовой структуры данных используется массив[…]хеш-таблицы не поддерживают ни упорядоченного перебора, ни выборки максимального/минимального элемента[…]”
Роберт Лафоре. Структуры данных и алгоритмы JAVA., 2017

******Не следует путать ситуацию с коллизией и запись значения в уже существующий ключ
Коллизия может произойти либо в момент создания hashMap, когда под ключи для баккетов раздаются хешкоды, либо во время рехеширования, когда HashMap заново раздает хеши, уже в большем количестве, чтобы увеличить объем HashMap.

*******
многомерные массивы с любыми видами объектов:

Как HashMap решает проблему коллизий

Когда HashMap создает два баккета с одинаковыми хешкодами, возникает коллизия.
Один из способов решения коллизии(стратегия Separate chaining):
с помощью привязывания к каждому баккету связанного списка(linked list) хешированного к этому баккету. Именно поэтому, плохая хеш-функция(hashCode()) делает поиск по хеш-таблицам очень медленным.
JGX80
есть и другие способы

Ссылки


подробно про HashMap
о ConcurrentHashMap
Map tutorial
Сортировка Map, упорядоченная Map, и другое
хорошее определение Map

LEAVE A COMMENT