Class HashMap<K, V>
This implementation provides constant-time performance for the basic operations ( get and put ), assuming the hash function disperses the elements properly among the buckets. 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). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. 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.
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put ). 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.
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. Note that using many keys with the same hashCode() is a sure way to slow down performance of any hash table. To ameliorate impact, when keys are Comparable , this class may use comparison order among keys to help break ties.
Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (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.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be «wrapped» using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:
The iterators returned by all of this class’s «collection view methods» are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the iterator will throw a ConcurrentModificationException . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
Map в Java. Hashmap в Java
Привет! Это статья про Карты (Map), один из способов хранения данных в Java.
Что такое карта (Map)
К сожалению, карта (Map) в Java не имеет никакого отношения к картам из реального мира �� Ну или почти никакого.
В программировании, карта (Map) — это структура данных, в которой объекты хранятся не по одному, как во всех остальных, а в паре «ключ — значение».
Ну вот представьте, что у нас есть обычный массив строк, в котором хранятся, например, имена людей — Вася, Катя, Лена:
Тем не менее, в карте мы храним пары «ключ-значение» — и обращаться к элементам мы будем не по индексам, а по ключам. В нашем случае ключ — это дата рождения:
Причем ключем может быть что угодно — число, строка или какой-нибудь другой объект.
Какие есть виды карт (map) в Java
Cреди основных реализаций можно назвать:
- HashMap
- LinkedHashMap
- TreeMap
- Hashtable
Если представить в виде диаграммы, будет выглядеть так:
Но для начала этого явно многовато �� Поэтому по теме «map в Java» мы чуть позже напишем несколько статей. А пока эта статья будет как вводная с основным акцентом на HashMap.
Давайте посмотрим, чем они друг от друга отличаются.
- HashMap — хранит значения в произвольном порядке, но позволяет быстро искать элементы карты. Позволяет задавать ключ или значение ключевым словом null.
- LinkedHashMap — хранит значения в порядке добавления.
- TreeMap — сама сортирует значения по заданному критерию. TreeMap используется либо с Comparable элементами, либо в связке с Comparator. Смотрите статью «Интерфейсы Comparable и Comparator».
- Hashtable — как HashMap, только не позволяет хранить null и синхронизирован с точки зрения многопоточности — это значит, что много потоков могут работать безопасно с Hashtable. Но данная реализация старая и медленная, поэтому сейчас уже не используется в новых проектах.
Можно сказать, что для начала Вам хватит знать и уметь работать с HashMap. Именно на ней мы и будем приводить примеры.
Синтаксис HashMap
Создание объекта типа Map похоже на создание коллекций — только мы должны задавать два типа — тип ключа и тип значения:
HashMap
HashMap — структура данных, одна из коллекций языка Java. Представляет собой хэш-таблицу. Так называется набор из пар «ключ-значение», где у ключей есть хэши, то есть числовые уникальные идентификаторы. Они высчитываются для каждого ключа.
Общее название сущности, которая хранит в себе ключи и значения, — ассоциативный массив. То есть структура данных, похожая на массив, где вместо индексов — ключи. Самый очевидный пример — простая таблица, где заголовок является ключом.
В HashMap ключом может быть практически что угодно, но важен в первую очередь хэш ключа.
Для чего нужен HashMap
HashMap пользуются разработчики на Java. Как и все структуры, относящиеся к коллекциям, он нужен в первую очередь для хранения информации и работы с ней. HashMap быстро работает, и большинство операций в нем выполняется за фиксированное время — это происходит благодаря оптимизированному доступу к данным. Как и практически все структуры из Collections Framework, он динамический, то есть его размер не фиксирован — туда можно добавить практически любое количество объектов.
HashMap используется, когда разработчику нужно хранить где-то пары «ключ-значение», при этом иметь возможность быстро получить значение по ключу. Например, имя пользователя и номер его телефона. Если нужно хранить просто список значений, лучше подойдет ArrayList или похожая структура.
Как устроены хэш-таблицы
HashMap — структура из пар «ключ-значение». Внутри это динамический массив ключей. Каждый элемент массива — своеобразная «корзинка», которая хранит связанный список со значением. О том, что собой представляет каждая из этих сущностей, можно почитать в статьях про ArrayList и коллекции.
Но HashMap используют для хранения пар — на каждый ключ приходится только одно значение. То есть связанный список будет состоять из одного элемента, а ссылаться этот элемент будет на null — специальное «пустое» значение. Если бы в такой структуре значений было несколько, первое ссылалось бы на второе и так далее — так устроен связанный список.
Связанный список нужен, чтобы избежать коллизий. Мы подробнее расскажем об этом ниже.
Для оптимизации доступа используется хэш ключа. Когда в HashMap добавляют ключ и значение, для ключа сразу высчитывается хэш. По нему определяется позиция в массиве для этой пары: для расчета есть специальные формулы.
Реализация и свойства HashMap
HashMap — динамическая структура, то есть количество «корзинок» может изменяться. По умолчанию сущность создается с 16 «корзинками», но это поведение можно поменять при создании, для чего надо задать хэш-таблице начальный размер вручную. Когда элементов в ней становится больше, чем корзинок, структура удлиняется — перезаписывает массив на новый, с большей длиной. По умолчанию длина увеличивается вдвое.
У HashMap, как и у всех подобных структур, есть набор своих методов — функций, которые позволяют удобно работать с данными. Для добавления, поиска, перезаписи или удаления элемента есть свои команды; также можно перебирать элементы и ключи и делать многое другое. Благодаря использованию хэшей эти методы работают очень быстро, и для самых популярных из них время выполнения константно, если нет коллизий.
Коллизии и их предотвращение
В идеальной ситуации хэш полностью индивидуален для каждого уникального объекта. Но в реальности хэши могут совпадать у совершенно разных объектов. Это происходит из-за несовершенства существующих алгоритмов.
Может случиться так, что у двух разных ключей окажется одинаковый хэш. Или хэш будет разным, но по формуле позиция для обоих хэшей будет одинаковой. Тогда значения обоих ключей окажутся записаны в одну «корзинку». Это и есть коллизия. Именно из-за коллизий для хранения значений используется связанный список: если бы в массиве просто хранился объект, любая коллизия перезаписала бы текущее значение, а это опасно. А при текущей реализации, даже если случится коллизия, новое значение просто запишется в начало той же «корзинки», не изменив старое.
Если такое случится, структура потеряет эффективность и будет работать медленнее, поэтому коллизий все равно лучше не допускать, но сами данные останутся целы.
Отличие от перезаписи
HashMap умеет отличать коллизию от реальной перезаписи элемента. Когда структуре дают новую пару «ключ-значение», она проверяет, есть ли в массиве такие хэши и такие ключи. Результат такой:
- если таких хэшей и ключей нет, в хэш-таблицу просто добавляется новая пара;
- если такой ключ есть, это перезапись — структура переписывает элемент с таким же ключом;
- если такого ключа нет, но хэш есть — это коллизия, новое значение записывается в ту же «корзинку» за предыдущим.
Вы можете узнать больше про структуры данных в Java. Получите новую профессию на курсах и станьте разработчиком на популярном языке.