что такое map в java

Использование Map в Java

Использование Map в Java

Множество представляет собой набор данных, в котором можно быстро найти существующий элемент. Однако для этого нужно иметь точную копию требуемого элемента. Этот вид поиска не очень распространен, поскольку обычно известна лишь некоторая информация (ключ), по которой можно найти соответствующий элемент. Специально для этого предназначена структура данных,поддерживающая отображение, которую называют также картой. Карта хранит пары «ключ-значение». Каждое значение можно найти по его ключу. Например, в таблице могут находиться записи с информацией о сотрудниках, где ключами являются идентификационные номера сотрудников, а значениями — объекты Employee.

Интерфейс Map (java.util.Map )

Основные реализации Map

В библиотеке Java предусмотрено две основные реализации карт: хэш-карта HashMap и карта-дерево ТгееМар. Оба класса реализуют интерфейс Map.
В хэш-карте ключи расположены случайным образом, а в карте-дереве — в строгом порядке. Хэш-функция, или функция сравнения, применяется только для ключей, а са­ми значения, соответствующие этим ключам, не хэшируются и не сравниваются.
Какую же из карт следует выбрать? Как и для множеств, хэширование несколько быстрее, поэтому его рекомендуется использовать там, где порядок следования клю­чей не имеет значения.

Ниже показано, как создается хэш-карта для хранения информации о сотрудниках.

При добавлении объекта к карте должен быть указан и его ключ. В данном случае ключом является строка, а соответствующим значением — объект Employee.
Чтобы обратиться к объекту, нужно воспользоваться ключом.

Если данных, соответствующих указанному ключу в наборе данных нет, метод get() возвращает значение null. Ключи должны быть уникальными: нельзя сохранить два значения с одинаковым ключом. Если вызвать метод put() дважды с одинаковым ключом, то второе значение просто заменит первое. Кроме того, метод put() возвращает предыдущее значение, хранимое с указанным ключом.

Метод remove() удаляет элемент из карты, а метод size() возвращает число элементов карты.

В архитектуре наборов данных карта сама по себе не рассматривается как набор. (В других архитектурах структур данных карта считается набором пар, или значений, индексируемых ключами.) Однако в библиотеке Java предусмотрено использованиепредставления (view) карты, которое реализует интерфейс Collection или один из его дочерних интерфейсов.

Существует три типа представлений: в виде множества ключей, набора значений (который не является множеством) или множества пар «ключ-значение». Ключи и пары «ключ-значение» формируют множество, так как в карте может присутствовать только один уникальный экземпляр объекта-ключа. Перечисленные ниже методы возвращают эти три типа представлений карты.

(Элементы последнего множества пар «ключ-значение» являются объектами внутреннего класса Map.Entry) Обратите внимание, что множество ключей не является объектом HashSet или TreeSet,но представляет собой объект некоторого другого класса, реализующего интерфейс Set.Интерфейс Set расширяет интерфейс Collection.Следовательно, вы можете использовать метод keySet().
Например, можно перебрать все ключи карты:

Если нужно одновременно просматривать ключи и значения, то можно избежать необходимости поиска значений, перечисляя всезаписи. Для этого можно использовать следующую заготовку кода:

Специальные реализации Map

Хэш-карты с нестрогим кэшированием

Класс хэш-карт с нестрогим кэшированием WeakHashMap был разработан для ре­шения интересной задачи. Что происходит со значением, ключ которого больше не используется в программе, например из-за того, что исчезла последняя ссылка на этот ключ? В этом случае обратиться к объекту-значению уже нельзя. А так как этот ключ уже не содержится нигде в программе, то нет никакой возможности удалить его пару «ключ-значение» из карты. Но почему его не может удалить система сборки мусора, в обязанности которой как раз и входит удаление неиспользуемых объектов?

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

Вот как работает этот механизм. Класс WeakHashMap использует для хранения ключей нестрогие ссылки (weak references). ОбъектWeakReference содержит ссылку на другой объект, т.е. в данном случае на ключ хэш-таблицы. Обычно, если при сборке мусора выясняется, что на некоторый объект нет ссылок, этот объект удаляется. А еслиединственная ссылка на объект имеет типWeakReference, эта нестрогая ссылка помещается в очередь. Периоди­чески происходит проверка на появление новых ссылок в очереди, так как это означает, что данный ключ больше не используется и его объект можно удалить. Таким образом, классWeakHashMap удаляет соответствующее этому ключу значение.

Связанные хэш-карты

В JDK 1.4 были предложены классы LinkedHashSet и LinkedHashMap, которые запоминают последовательность вставки в набор данных новых пунктов. Таким обра­зом, порядок следования пунктов таблицы уже не выглядит случайным. По мере добавления записей в таблицу они формируют двусвязный список.
Рассмотрим, например, карту:

Итератор staff.ketSet().iterator() перечислит ее ключи в следующем порядке:
А итератор staff.values().iterator() перечислит ее значения так:

Связная хэш-карта может запоминать порядок доступа и учитывать его при пере­боре элементов. Каждый раз, когда вы вызываете метод get() или put() запись, которую он затрагивает, удаляется из занимаемой позиции и перемещается в конец связного списка. При этих операциях изменяется структура связного списка, но не ячеек хэш-таблицы. Запись остается в той ячейке, которая соответствует хэш-коду ключа. Для того чтобы создать подобную хэш-карту, нужно использовать следующее выражение:

Знать порядок доступа необходимо, например, для создания кэша, работающего по принципу «последнего по времени использования». Например, вам может понадо­биться хранить в памяти наиболее часто используемые записи, а те, с которыми приходится работать редко, извлекать из базы данных. Если вы не находите запись в таб­лице, а таблица уже достаточно заполнена, вы можете удалить с помощью итератора первые несколько элементов. Именно эти элементы используются реже других.

Хэш-карты с индивидуальным хэшированнием

В JDK 1.4 добавлен еще один специальный класс IdentityHashMap, выполняю­щий индивидуальное хэширование. Хэш-коды ключей в нем подсчитываются не мето­дом hashCode(),а методом System.identityHashCode().Этот метод вычисляет хэш-код по адресу объекта в памяти. Кроме того, для сравнения объектов класс IdentityHashMapприменяет оператор ==, а не метод equals().

Иначе говоря, разные объекты считаются отличающимися друг от друга, даже если их содержимое совпадает. Этот класс полезендля реализации алгоритмов обхода объектов (например, для сериализации), в которых требуется следить даже за теми объектами, которые уже были пройдены итератором.

Использование Collections в Map

Немодифицируемые представления

Класс Collectionsсодержит методы, которые создаютнемодифицируемые пред-ставления (unmodifiableview) наборов данных. В этих представлениях реализована проверка существующего набора, выполняемая на этапе работы программы. При по¬пытке модифицировать набор, генерируется исключение и набор данных остается неизменным.
Для получения немодифицируемых Map представлений используются методы:

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

МетодCollections.unmodifiableMap возвращает экземпляр класса, реализующего интерфейс Map. Метод доступа этого класса извлекает значения из набора staff.Очевидно, что метод lookAt() может вызывать все методы, объявленные в интерфейсе Map. Однако все модифицирующие методы пере¬определены так, что вместо обращения к базовому набору генерируют исключение UnsupportedOperationException.

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

Синхронизируемые представления

Если вы обращаетесь к набору данных из нескольких потоков, необходимо при¬нять меры, чтобы не повредить информацию в наборе. Это неминуемо произойдет, если, например, один поток будут пытаться включить элемент в хэш-таблицу, а другой — перегенерировать ее.

Вместо того чтобы реализовать классы наборов данных, обеспечивающих безопасную работу с потоками, разработчики библиотеки предпочли использовать для этого механизм представлений. Например, статический метод synchronizedMap() классаCollectionsможет преобразовать любую карту в Map с синхронизированны¬ми методами доступа.

Теперь вы можете обращаться к объекту map из различных потоков. Такие методы, как get() и put(),сериализованы: каждый метод должен полностью закончить свою работу перед тем, как другой поток сможет вызвать подобный метод.

При разработке программы необходимо следить, чтобы ни один поток не обращался к структуре данных посредством обычных де синхронизированных методов. Самый простой способ обеспечить это — не сохранять ни одной ссылки на базовый объект.

Классы Hashtable и Dictionary

Традиционный класс Hashtable служит той же цели, что и HashMap, и имеет, в сущности, такой же интерфейс. Как и методы класса Vector, методы класс Hashtable синхронизированы. Если Вам не требуется обеспечить синхронизацию или совместимость с кодом для предыдущих версий платформы Java, то в таком случае следует воспользоваться классом HashMap. Класс Dictionary является абстрактным классом-родителем Hashtable.

Если Вам понравилась статья, проголосуйте за нее

Голосов: 31 Голосовать

Источник

Ответы на самые популярные вопросы об интерфейсе Map

0. Как перебрать все значения Map

1. Как конвертировать Map в List

2. Как отсортировать ключи мапы

Поместить Map.Entry в список и отсортировать его, используя Comparator.

В компараторе будем сравнивать исключительно ключи пар:

Если разобрался с лямбдами, эту запись можно существенно сократить:

И, конечно, все можно переписать, используя лямбды:

В отличие от первого способа, используя SortedMap, мы всегда будем хранить данные в отсортированном виде.

3. Как отсортировать значения мапы

4. В чем разница между HashMap, TreeMap, и Hashtable

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

Допустимые значения. HashMap позволяет иметь ключ и значение null, HashTable — нет. TreeMap может использовать значения null только если это позволяет компаратор. Без использования компаратора (при хранении пар в порядке добавления) значение null не допускается.

Синхронизация. Только HashTable синхронизирована, остальные — нет. Если к мапе не будут обращаться разные потоки, рекомендуется использовать HashMap вместо HashTable.

И общее сравнение реализаций:

5. Как создать двунаправленную мапу

6. Как создать пустую Map

Обычная инициализация объекта:

Создание неизменяемой (immutable) пустой мапы:

Источник

Map в Java с примерами

В статье о коллекциях я обещал написать статью о Map в Java. Сейчас мы подробно разберем эту очень полезную и нужную структуру данных с примерами кода.

Когда мы слышим слово мап, то первое, что приходит на ум — это карта (у меня гугл мапс). Map как структура данных не имеет ничего общего с картами гугла.

Чтобы правильно понять, что такое мап вспомните поликлинику. Да, воспоминания не очень. Но, нам нужно только вспомнить регистратуру, когда для приема у врача нам сначала нужно выстоять здоровенную очередь за своей картой. Не знаю как там в Европе, но для граждан стран СНГ это знакомо. Мы приходим, говорим свои данные и получаем карточку. Если же мы приходим впервые, нас регистрируют и только потом выдают карточку. Как правило карты находятся в алфавитном порядке и «милой» тете с регистратуры ее не сложно найти.

Иерархия классов Map немного похожа на Set:

HashMap — хранит ключи в hash-таблице. Она имеет наибольшую производительность. Однако такая реализация не гарантирует порядок элементов.

TreeMap — хранит ключи в отсортированном порядке. Работает медленнее чем хэшмап.

LinkedHashMap — хранит ключи в порядке их вставки в мап. Работает немного медленнее чем HashMap.

WeakHashMap — реализация интерфейса Map на основе хэш-таблицы со слабыми ключами. Запись в WeakHashMap будет автоматически удалена, если ее ключ больше не используется обычным образом.

Рассмотрим подробнее HashMap. Скорость ее работы О(1), а в худшем случае O(logn). Чтобы понять, когда будет худший случай давайте разберемся как она работает. Это, кстати, очень популярный вопрос на собеседованиях.

У каждого объекта есть метод hashCode, который возвращает значение хэш кода. Когда мы помещаем объект в HashMap сначала определяется значение hash кода его ключа, далее выбирается место, куда поместить объект в зависимости от полученного хэш кода. Если по такому ключу уже есть значение в мапе, то проверяется объект, который мы пытаемся добавить если он такой же как и существующий, то идет перезапись. Если объекты разные, а хэш код одинаковый (произошла коллизия или мы неправильно переопределили метод hashCode) объект помещается в ту самую ячейку в виде связанного списка. Вот откуда худший случай работы HashMap. Когда хэш код ключей одинаковый эта структура начинает работать как LinkedList скорость которого O(logn). Вы можете спросить: как нужно переопределить метод hashCode чтобы он возвращал одинаковое значение для всех объектов? Вот пример:

public class MapExamples <

private String name ;
private double sum ;

@Override
public int hashCode ( ) <
return 1 ;
>

Да, нужно постараться, чтобы такое сделать, но все же.

Теперь перейдем к примеру. Будут рассмотрены только самые популярные методы. Они у всех реализациях одинаковы.

import java.util.HashMap ;
import java.util.Map ;

public class MapExamples <

Что еще хотелось бы упомянуть о Map в java:

Вот и все, что касается интерфейса Map и его реализации. Теперь у Вас будет полное представление о стандартных коллекциях в java и их применениях.

Источник

Что такое map в java

В интерфейсе java.util.Map параметризуются два типа, это ключ и значение.

Объявление java.util.Map выглядит как:

При этом стоит отметить, что не может быть повторяющихся ключей, что следует из названия и смысла Map : каждому ключу соответствует значение.

Вопрос:

Ответ:

Класс java.util.Dictionary является полностью абтрактным, без какого-либо состояния.

Но благодаря WORA в Java просто так ничего не меняют и не удаляют, поэтому старые классы остались, а новую иерархию начали строить с интерфейсов.

Основные методы, которые предоставляет интерфейс java.util.Map :

Это значит, что все реализации интерфейса java.util.Map позволяют доставать, добавлять и удалять элементы по ключам, а также предоставлять множество ключей и коллекцию хранимых значений.

Как уже было сказано выше, Map это набор пар ключ-значение.

Объявление java.util.Map#Entry выглядит как:

И предоставляет методы, позволяющие получить/установить ключ и значение.

Помимо всего прочего предоставляются также компараторы для сравнения пар по ключу и значению.

Объявление выглядит следующим образом:

Объявление выглядит следующим образом:

Иерархия классов выглядит следующим образом:

Абстрактный класс java.util.AbstractMap предоставляет заготовку для последующих реализаций.

Что говорит о том, что операция не поддерживется и ее надо либо не использовать, либо переопределить метод.

Наиболее известные реализации java.util.Map :

Когда и какую реализацию выбрать?

Если порядок хранения элементов не важен, то выбор java.util.HashMap более чем оправдан.

Помните, что java.util.TreeMap не поддерживает работу с null ключами.

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

Стоит помнить, что, как и в случае с итерированием сипсков, если в ходе работы итератора структура данных была изменена (без использования методов итератора), то будет выброшено исключение:

Избежать этого можно удаляя элемент с помощью итератора, с которым происходит работа:

Источник

Map в Java. Hashmap в Java

Привет! Это статья про Карты (Map), один из способов хранения данных в Java.

Что такое карта (Map)

К сожалению, карта (Map) в Java не имеет никакого отношения к картам из реального мира 🙂 Ну или почти никакого.

Какие есть виды карт (map) в Java

Cреди основных реализаций можно назвать:

Если представить в виде диаграммы, будет выглядеть так:

Но для начала этого явно многовато 🙂 Поэтому по теме «map в Java» мы чуть позже напишем несколько статей. А пока эта статья будет как вводная с основным акцентом на HashMap.

Давайте посмотрим, чем они друг от друга отличаются.

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

Синтаксис HashMap

Источник