Тема 18. Карты - BelyiZ/JavaCourses GitHub Wiki
Отображение (Map
) - это структура данных, в которой объекты хранятся не по одному, как во всех остальных, а в паре "ключ - значение".
Интерфейс Java Map, java.util.Map, представляет собой программную реализацию математического отображения дискретных множеств.
Отображение хранит данные в формате ключ и значение.
Каждый ключ связан с определенным значением. После сохранения в Map
вы можете позже найти значение, используя только ключ.
Важно отметить, что в отображении не может быть повторяющихся ключей, что следует из названия.
Иногда реализации java.util.Map называют справочниками или хэш-таблицами.
Интерфейс java.util.Map не является наследником интерфейса java.util.Collection. Следовательно, он немного отличается от остальных типов коллекций. Однако формально относится к Collections Framework
.
В интерфейсе java.util.Map параметризуются два типа: ключ и значение. Объявление java.util.Map выглядит следующим образом:
public interface Map<K,V> {
// ...
}
Под ключом мы имеем ввиду объект, который используем для извлечения данных, то есть связанного значения. В структурном плане Map
не наследует интерфейс Iterable
и имеет ряд уникальных методов, характерных только для него. У этого интерфейса схожая с Set
структурная иерархия классов.
Наиболее известные реализации java.util.Map
:
• java.util.HashMap - основана на хэш-таблицах. • java.util.LinkedHashMap - расширение предыдущей реализации с использованием двусвязных списков. • java.util.TreeMap - основана на стуктуре красно-черное дерева. • Их Concurrent & unmodifiable варианты.
Также существует реализация java.util.HashTable, но она уже давно не рекомендуется к использованию, во многом благодаря тому, что большинство методов в ней является synchronized
, что губительо сказывается на производительности.
HashMap — коллекция является альтернативой Hashtable
. Двумя основными отличиями от Hashtable
являются то,
что HashMap
не синхронизирована и HashMap
позволяет использовать null как в качестве ключа, так и значения. Так же
как и Hashtable
, данная коллекция не является упорядоченной: порядок хранения элементов зависит от хэш-функции.
Добавление элемента выполняется за константное время O(1), но время удаления, получения зависит от распределения
хэш-функции. В идеале является константным, но может быть и линейным O(n). Более подробную информацию о HashMap можно
почитать здесь (актуально для Java < 8).
LinkedHashMap — это упорядоченная реализация хэш-таблицы. Здесь, в отличии от HashMap
, порядок итерирования равен
порядку добавления элементов. Данная особенность достигается благодаря двунаправленным связям между элементами (
аналогично LinkedList
). Но это преимущество имеет также и недостаток — увеличение памяти, которое занимает коллекция.
TreeMap — реализация Map основанная на красно-чёрных деревьях. Как и LinkedHashMap
является упорядоченной.
По-умолчанию, коллекция сортируется по ключам с использованием принципа "natural ordering", но это поведение может быть
настроено под конкретную задачу при помощи объекта Comparator, который указывается в качестве параметра при создании
объекта TreeMap
.
Наиболее часто используемые реализации – это HashMap
и TreeMap
.
Каждая из них ведет себя немного по-разному в отношении порядка элементов при итерации и времени, необходимого для вставки и доступа к элементам.
Примеры, как создать экземпляр:
Map mapA = new HashMap();
Map mapB = new TreeMap();
1. put(K key, V value) - добавляет элемент в карту;
Map mapA = new HashMap();
mapA.put("key1", "element 1");
Только объекты могут быть использованы в качестве ключей и значений.
Если вы передаете примитивные значения (например, int
, double
и т. Д.) в качестве ключа или значения, они будут автоматически упакованы перед передачей в качестве параметров.
Вот пример параметров примитива auto-boxing, передаваемых методу put()
:
mapA.put("key", 123);
Значение, переданное методу put()
в приведенном выше примере, является примитивом int
.
Java автоматически упаковывает его внутри экземпляра Integer
, поскольку для put()
в качестве ключа и значения требуется экземпляр Oject
.
Автобокс также может произойти, если вы передадите примитив в качестве ключа.
Заданный ключ может появляться на карте только один раз. Это означает, что только одна пара ключ + значение для каждого из них может существовать одновременно. Другими словами, для ключа «key1» в одном экземпляре может храниться только одно значение. Конечно, возможно хранить значения одного и того же ключа в разных экземплярах карты.
Если вызывать put()
более одного раза с одним и тем же ключом, последнее заменяет существующее значение для данного ключа.
Обратите внимание, что ключ не может быть нулевым!
Карта использует методы ключа hashCode() и equals() для внутреннего хранения пары ключ-значение, поэтому, если ключ имеет значение null, карта не может правильно разместить пару внутри.
Но значение пары ключ + значение, хранящееся на карте, может быть нулевым.
mapA.put("D", null);
Интерфейс имеет метод putAll()
, который может копировать все пары ключ-значение (записи) из другого экземпляра в себя.
В теории множеств это также называется объединением двух экземпляров Map
.
Map mapA = new HashMap();
mapA.put("key1", "value1");
mapA.put("key2", "value2");
Map mapB = new HashMap();
mapB.putAll(mapA);
После выполнения этого кода карта, на которую ссылается переменная mapB, будет содержать обе записи ключ + значение, вставленные в mapA в начале примера кода.
Копирование записей идет только в одну сторону.
Вызов mapB.putAll(mapA)
будет копировать только записи из mapA
в mapB
, а не из mapB
в mapA
.
Чтобы скопировать записи другим способом, вам нужно будет выполнить код mapA.putAll(mapB)
.
2. get(Object key) - ищет значение по его ключу;
Обратите внимание, что метод get() возвращает Java-объект, поэтому мы должны привести его к String(поскольку мы знаем, что значение является String). Позже в этом руководстве по Java Map вы увидите, как использовать Java Generics для ввода Map, чтобы она знала, какие конкретные типы ключей и значений она содержит. Это делает ненужным приведение типов и усложняет случайное добавление неправильных значений в карту.
String element1 =(String) mapA.get("key1");
Интерфейс имеет метод getOrDefault()
, который может возвращать значение по умолчанию, предоставленное заранее – в случае, если никакое значение не сохранено с помощью данного ключа:
Map map = new HashMap();
map.put("A", "1");
map.put("B", "2");
map.put("C", "3");
Object value = map.getOrDefault("E", "default value");
В этом примере создается карта и в ней хранятся три значения с использованием ключей A, B и C.
Затем вызывается метод Map getOrDefault()
, передавая в качестве ключа строку String E
вместе со значением по умолчанию – значением String
по умолчанию.
Поскольку карта не содержит объектов, хранящихся в ключе E, будет возвращено заданное значение по умолчанию.
- remove(Object key) - удаляет значение по его ключу;
Возможно удалить записи, вызывая метод remove(Object key)
.
Таким образом, удаляется пара (ключ, значение), соответствующую ключу.
mapA.remove("key1");
После выполнения этой инструкции карта, на которую ссылается mapA
, больше не будет содержать запись (пара ключ + значение) для ключа key1
.
Для удаление всех записей используется метод clear()
mapA.clear();
- containsKey(Object key) - спрашивает, есть ли в карте заданный ключ;
boolean hasKey = mapA.containsKey("123");
После выполнения этого кода переменная hasKey
будет иметь значение true
, если пара ключ + значение была вставлена ранее с помощью строкового ключа 123, и false
, если такая пара ключ + значение не была вставлена.
- containsValue(Object value) - спрашивает есть ли в карте заданное значение;
boolean hasValue = mapA.containsValue("value 1");
После выполнения этого кода переменная hasValue будет содержать значение true
, если пара ключ-значение была вставлена раньше, со строковым значением «значение 1», и false
, если нет.
- size() - возвращает размер карты (количество пар "ключ-значение").
Возможно узнать количество записей, используя метод size()
.
Количество записей в Java-карте также называется размером карты – отсюда и имя метода size()
.
int entryCount = mapA.size();
По умолчанию вы можете поместить любой объект в карту, но Generics
из Java 5 позволяет ограничить типы объектов, которые возможно использовать как для ключей, так и для значений в карте:
Map map = new HashMap();
Эта карта теперь может принимать только объекты String
для ключей и экземпляры MyObject
для значений.
Затем вы можете получить доступ к итерированным ключам и значениям без их приведения.
for(MyObject anObject : map.values()){
}
for(String key : map.keySet()){
MyObject value = map.get(key);
}
Интерфейс имеет несколько функциональных операций, добавленных из Java 8. Они позволяют взаимодействовать с Map в более функциональном стиле. Например, возможно передать лямбда-выражение в качестве параметра этим методам.
Функциональные методы работы:
- compute().
- computeIfAbsent().
- computeIfPresent().
- merge().
compute()
Метод принимает ключевой объект и лямбда-выражение в качестве параметров.
Лямбда-выражение должно реализовывать интерфейс java.util.function.BiFunction
.
map.compute("123",(key, value) -> value == null ? null : value.toString().toUpperCase());
Метод compute()
будет вызывать лямбда-выражение внутри себя, передавая ключевой объект и любое значение, сохраненное в Map
для этого ключевого объекта, в качестве параметров лямбда-выражения.
Какое бы значение не возвращалось лямбда-выражением, оно сохраняется вместо текущего значения этого ключа. Если лямбда-выражение возвращает ноль, запись удаляется. Там не будет ключа -> нулевое отображение хранится на карте.
Если лямбда-выражение выдает исключение, запись также удаляется.
В приведенном выше примере лямбда-выражение проверяет, является ли значение, сопоставленное данному ключу, нулевым или нет, перед вызовом toString().ToUpperCase()
для него.
computeIfAbsent()
Метод Map computeIfAbsent()
работает аналогично методу compute()
:
Лямбда-выражение вызывается, только если для данного ключа уже не существует записи. Значение, возвращаемое лямбда-выражением, вставляется в карту. Если возвращается ноль, запись не вставляется. Если лямбда-выражение генерирует исключение, запись также не вставляется.
map.computeIfAbsent("123",(key) -> "abc");
Этот пример просто возвращает постоянное значение – строку 123. Однако лямбда-выражение могло вычислить значение любым необходимым способом – например, извлечь значение из другого объекта или объединить его с другими значениями и т. д.
computeIfPresent()
Метод работает противоположно computeIfAbsent()
.
Он вызывает только лямбда-выражение, переданное ему в качестве параметра, если в Map
уже существует запись для этого ключа.
map.computeIfPresent("123",(key, value) -> value == null ? null : value.toString().toUpperCase());
Значение, возвращаемое лямбда-выражением, будет вставлено в экземпляр Map. Если лямбда-выражение возвращает ноль, запись для данного ключа удаляется. Если лямбда-выражение выдает исключение, оно перебрасывается, и текущая запись для данного ключа остается неизменной.
merge()
Метод принимает в качестве параметров ключ, значение и лямбда-выражение, реализующее интерфейс BiFunction
.
Если в карте нет записи для ключа или если значение для ключа равно нулю, значение, переданное в качестве параметра методу merge()
, вставляется для данного ключа.
Однако, если существующее значение уже сопоставлено с данным ключом, вместо этого вызывается лямбда-выражение, переданное как параметр.
Таким образом, лямбда-выражение получает возможность объединить существующее значение с новым значением. Значение, возвращаемое им, затем вставляется в карту для данного ключа.
Если лямбда-выражение возвращает ноль, запись для данного ключа удаляется.
Если в лямбда-выражении выдается исключение, оно перебрасывается, и текущее отображение для данного ключа сохраняется без изменений.
map.merge("123", "XYZ",(oldValue, newValue) -> newValue + "-abc");
В этом примере будет вставлено значение XYZ в карту, если значение не сопоставлено с ключом (123) или если значение NULL сопоставлено с ключом. Если ненулевое значение уже сопоставлено с ключом, вызывается лямбда-выражение. Лямбда-выражение возвращает новое значение (XYZ) + значение -abc, что означает XYZ-abc.
Когда удобно применять:
- Вставка элементов (объектов).
- Вставка элементов с тем же ключом.
- Вставка всех элементов с другой карты.
- Возвращение значения по умолчанию.
- Проверка содержится ли ключ.
- Проверка содержится ли значение.
- Перебор ключей.
- Использование ключевого итератора.
- Итерация значений.
- Итерация записей.
- Удаление записей (в том числе всех).
- Замена записи.
- Выяснение количества записей.
- Проверка, пуста ли карта.
- Формирование общих карт.