map in java

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

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

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

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

регистратура

Map в java — это структура данных, которая хранит данные в виде <Ключ, Значение>. Каждое значение можно найти по его ключу. Немного фактов о мап:

  • карта не может содержать дубликаты ключей;
  • каждый ключ может отображать только одно значение (далее мы посмотрим реализации map и что бывает, если попробовать добавить несколько объектов с одним ключом);
  • Map не расширяет интерфейс Collection.

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

мап иерархия классов

Как видим у интерфейса мап есть несколько реализаций. Самые используемые и популярные это: HashMap<K, V>, TreeMap<K, V>. Их мы и рассмотрим подробнее.

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

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

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

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

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

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

Код    
  1. package com.javamaster;
  2.  
  3. public class MapExamples {
  4.    
  5.     private String name;
  6.     private double sum;
  7.    
  8.     public MapExamples(String name, double sum) {
  9.         this.name = name;
  10.         this.sum = sum;
  11.     }
  12.    
  13.    
  14.  
  15.     @Override
  16.     public int hashCode() {
  17.         return 1;
  18.     }
  19.  
  20.     public static void main(String[] args) {
  21.         MapExamples example1 = new MapExamples("Some name", 34);
  22.         MapExamples example2 = new MapExamples("Another name", 12.5);
  23.         System.out.println(example1.hashCode());
  24.         System.out.println(example2.hashCode());
  25.     }
  26.  
  27. }

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

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

Код    
  1. package com.javamaster;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5.  
  6. public class MapExamples {
  7.    
  8.  
  9.     public static void main(String[] args) {
  10.         Map<Integer, String> users = new HashMap<>();
  11.         users.put(1, "Ivan");//добавление элементов
  12.         users.put(2, "Nataliya");
  13.         users.put(3, "Anton");
  14.         System.out.println(users.get(2));//получение по ключу
  15.        
  16.         System.out.println(users.containsKey(1));//проверка есть значение с таким ключем
  17.         users.remove(1);//удаление по ключу
  18.         System.out.println(users.containsKey(1));
  19.        
  20.         System.out.println(users.size());//размер мапы
  21.        
  22.         System.out.println(users.isEmpty());//проверка пустая ли мапа
  23.        
  24.         users.forEach((k, v) -> System.out.println(k + ": " + v));//элегантный вывод
  25.     }
  26. }

результат работы хэш мап

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

  • желательно не использовать ключи, которые могут изменяться. Так можно потерять доступ к объекту;
  • желательно всегда переопределять методы equals и hashCode в объектов, которые вы будете сравнивать, помещать или извлекать с коллекции (не только мап);
  • две мапы равны если у них один и тот же набор пары ключ-значение.

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

2 thoughts on “Map в Java с примерами

Добавить комментарий