Полное руководство по Java HashMap (с примерами)

От /

1. Введение

HashMap, часть фреймворка Java Collections, используется для хранения пар ключ-значение для быстрых и эффективных операций хранения и извлечения. В паре ключ-значение(также называемой записью), которая должна храниться в HashMap, ключ должен быть уникальным объектом, тогда как значения могут дублироваться.

Ключи используются для выполнения быстрого поиска. При извлечении значения мы должны передать связанный ключ. Если ключ найден в HashMap, он возвращает значение, в противном случае возвращает null. 

HashMap<String, String> map = new HashMap<>();map.put("+1", "USA");map.put("+91", "India");map.get("+1"); // returns "USA"map.get("+2"); // returns null

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

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

2. Создание HashMap

2.1 Использование конструктора по умолчанию

Мы можем создать HashMap разными способами, в зависимости от требований. Например, мы можем создать пустой HashMap, изначально не содержащий пар ключ-значение. Позже мы можем добавить пары ключ-значение в этот пустой HashMap. 

HashMap<String, String> map = new HashMap<>();

Кроме того, мы можем указать начальную грузоподъемность и коэффициент нагрузки по причинам производительности, обсуждаемым далее в этой статье. Обратите внимание, что начальная грузоподъемность должна быть степенью двойки, а коэффициент нагрузки должен быть между 0 и 1. 

HashMap<String, String> map = new HashMap<>(64, 0.90f);

2.2 Использование HashMap.newHashMap()

newHashMap() — статический метод, представленный в Java 19. Он создает новый пустой HashMap, подходящий для ожидаемого количества отображений.

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

HashMap<String, String> map = HashMap.newHashMap(6);

2.3 Использование конструктора копирования

В качестве альтернативы мы также можем инициализировать HashMap с существующей Map. В следующем коде записи из map будут скопированы в collectedMap. 

HashMap<String, String> copiedMap = new HashMap<>(map);

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

HashMap<Integer, Item> map = new HashMap<>();map.put(1, new Item(1, "Name"));// New map with copied entriesHashMap<Integer, Item> copiedMap = new HashMap<>(map);// Changing the value object in one mapcopiedMap.get(1).setName("Modified Name");// Change is visible in both mapsSystem.out.println(map.get(1)); // Item(id=1, name=Modified Name)System.out.println(copiedMap.get(1)); // Item(id=1, name=Modified Name)

3. Общие операции HashMap

Давайте рассмотрим общие операции, выполняемые над записями HashMap в любом приложении.

3.1. Добавление пар ключ-значение(put)

Метод HashMap.put() сохраняет указанное значение и связывает его с указанным ключом. Если карта ранее содержала сопоставление для ключа, старое значение заменяется новым значением. 

HashMap<String, String> hashmap = new HashMap<>();hashmap.put("+1", "USA"); // stores USA and associates with key +1hashmap.put("+1", "United States"); // Overwrites USA with United Stateshashmap.get("+1"); //returns United States

3.2 Извлечение значений по ключу(get)

Метод HashMap.get() возвращает значение, с которым сопоставлен указанный ключ, или значение null, если карта не содержит сопоставления для ключа. 

hashmap.put("+1", "USA");hashmap.get("+1"); // returns USAhashmap.get("+2"); // returns null

Если приложение позволяет нам помещать в карту нулевые значения, то мы можем проверить, отсутствует ли ключ или является ли отображенное значение нулевым, используя метод containsKey().

3.3 Удаление записей по ключу(удалить)

Метод HashMap.remove() удаляет пару ключ-значение для указанного ключа, если она присутствует. 

hashmap.remove("+1");

3.4 Проверка существования ключа/значения(containsKey, containsValue)

Метод containsKey() возвращает true, если хэш-карта содержит сопоставление для указанного ключа. В противном случае он возвращает false. 

hashmap.put("+1", "USA");hashmap.containsKey("+1"); //return truehashmap.containsKey("+2"); //return false

Аналогично, метод containsValue() возвращает true, если хэш-карта содержит одну или несколько пар ключ-значение с указанным значением. В противном случае он возвращает false. 

hashmap.put("+1", "USA");hashmap.containsValue("USA"); //return truehashmap.containsValue("Canada"); //return false

3.5. Итерация по HashMap

Мы можем перебирать ключи, значения или записи HashMap, используя различные представления коллекций, возвращаемые следующими методами:

  • keySet() для перебора ключей и доступа к значениям
  • entrySet() для перебора пар ключ-значение 
for(String key : hashmap.keySet()) {System.out.println("Key: " + key);System.out.println("Value: " + hashmap.get(key));}for(Map.Entry<String, String> entry : hashmap.entrySet()) {System.out.println("Key: " + entry.getKey());System.out.println("Value: " + entry.getValue());}

Мы также можем использовать метод forEach() для более наглядного перебора записей. 

hashmap.forEach((key, value) -> System.out.println(key + ": " + value));

3.6 Использование потоков Java 8 с HashMap

Java Stream API предоставляет краткий способ обработки коллекции объектов в плавной манере. Мы можем использовать потоки с классом HashMap, в первую очередь, для сбора существующего потока в HashMap.

Для сбора элементов Stream в HashMap мы можем использовать метод Stream.collect() вместе со сборщиком Collectors.toMap(). 

Stream<Item> stream = Stream.of(new Item(1, "Item 1"), new Item(2, "Item 2"));Map<Long, String> itemMap = stream.collect(Collectors.toMap(Item::getId, Item::getName,(oldValue, newValue) -> oldValue, HashMap::new));System.out.println(itemMap); // {1=Item 1, 2=Item 2}

Стоит отметить, что мы можем использовать API потоков для сортировки записей карты и сохранять их в другой карте, которая поддерживает порядок вставки, например, LinkedHashMap. 

LinkedHashMap<Long, String> sortedMap = stream.entrySet().stream().sorted(Map.Entry.comparingByKey()).collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue,(oldValue, newValue) -> oldValue,LinkedHashMap::new));

4. Реализация HashMap на Java

Хотя для эффективного использования класса HashMap не обязательно знать его внутреннее устройство, понимание того, «как работает HashMap», расширит ваши знания в этой теме, а также общее понимание структуры данных Map.

HashMap внутренне использует HashTable для хранения записей. HashTable хранит пары ключ-значение в структуре на основе массива и использует функцию хеширования для сопоставления ключей с определенными индексами в массиве. Массив также называется массивом bucket.

Начиная с Java 8, контейнер реализован как LinkedList. Используя LinkedList, мы можем хранить несколько записей в одном контейнере.

Полное руководство по Java HashMap(с примерами)0

Для повышения производительности, когда количество узлов достигает порогового значения(по умолчанию 8), LinkedList преобразуется в RedBlack Tree.

Полное руководство по Java HashMap(с примерами)1

Когда количество узлов становится меньше порогового значения(по умолчанию 6), дерево преобразуется обратно в LinkedList.

Вы можете прочитать эту статью, чтобы глубже понять внутреннюю реализацию HashMap.

5. Производительность и оптимизация HashMap

В большинстве реальных приложений мы будем хранить в HashMap всего несколько записей(возможно, менее 100). В таких случаях любая оптимизация производительности мало что меняет и часто не требуется.

В других случаях, когда мы хотим сохранить сотни или миллионы записей в HashMap, нам следует рассмотреть следующее.

5.1 Анализ временной сложности

Во время операций вставки, удаления и извлечения сложность операций в HashMap в среднем постоянна(O(1)). Обратите внимание, что сложность сильно зависит от хорошо распределенной хэш-функции и соответствующего коэффициента нагрузки.

В худшем случае все ключи попадают в одну и ту же корзину из-за коллизий хэшей, в результате чего эта корзина образует связанный список или дерево, что приводит к линейной временной сложности(O(n)).

  • Средний случай: O(1)
  • Лучший случай: O(1)
  • Худший случай: O(n)

5.2 Уменьшение столкновений и накладных расходов на изменение размера

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

Функция hashCode() по умолчанию во встроенных типах Java(таких как String, Integer, Long и т. д.) отлично справляется с этой задачей в большинстве случаев. Поэтому настоятельно рекомендуется использовать Java String или классы-обертки в качестве ключей в HashMap.

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

Например, в следующем классе Account мы переопределили метод hashcode и equals и использовали только номер счета для проверки уникальности экземпляра Account. Все остальные возможные атрибуты класса Account можно изменить во время выполнения. 

public class Account {private int accountNumber;private String holderName;//constructors, setters, getters//Depends only on account number@Overridepublic int hashCode() {final int prime = 31;int result = 1;result = prime * result + accountNumber;return result;}//Compare only account numbers@Overridepublic boolean equals(Object obj) {if(this == obj)return true;if(obj == null)return false;if(getClass() != obj.getClass())return false;Account other =(Account) obj;if(accountNumber != other.accountNumber)return false;return true;}}

Вы можете изменить приведенную выше реализацию в соответствии с вашими требованиями.

5.3 Эффективность памяти и сборка мусора

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

Оценка идеальной начальной емкости важна, поскольку переоценка может привести к бесполезному расходованию памяти, а недооценка — к увеличению числа операций по изменению размера.

Чтобы избежать проблем с памятью, мы должны очищать записи соответствующим образом, когда они больше не требуются. Удаление ненужных записей или очистка HashMap может помочь освободить память.

В некоторых случаях объекты, хранящиеся как ключи или значения, могут иметь финализаторы. Такие объекты имеют более сложный жизненный цикл и могут потенциально влиять на эффективность сборки мусора.

6. Распространенные ошибки и как их избежать

6.1. ConcurrentModificationException

ConcurrentModificationException возникает, когда коллекция изменяется одновременно с ее итерацией. В случае HashMap, если мы итерируем, используя его представления коллекции(keySet, valueSet, entrySet) и изменяем HashMap во время итерации, мы получим ConcurrentModificationException. 

for(Map.Entry<String, Integer> entry : nameMap.entrySet()) {if(entry.getKey().startsWith("Temp-")) {nameMap.remove(entry.getKey()); // throws ConcurrentModificationException}}

В таких случаях мы можем перебирать и изменять коллекцию с помощью итератора. 

Iterator<Entry<String, Integer>> iterator = nameMap.entrySet().iterator();while(iterator.hasNext()) {Map.Entry<String, Integer> entry = iterator.next();if(entry.getKey().equals("Temp-")) {iterator.remove(); // Safely remove the element}}

6.2 Использование изменяемых ключей

Это также очень распространенная проблема, которую часто можно увидеть. Очень важно понимать, что хэш-код объекта, используемого в качестве ключа, не должен меняться, иначе ранее сохраненная запись будет утеряна. Это приведет к утечке памяти. 

User user = new User(1, "Name");map.put(user, new Account(...));user.setname("New Name"); //It changes the hashcode//Returns null and causes memory leak as Account object is non-reachablemap.get(user);

Чтобы предотвратить такие утечки, мы должны использовать неизменяемые объекты в качестве ключей Map. Неизменяемый объект, будучи однажды созданным, не может быть изменен, поэтому его хэш-код также никогда не изменится. По этой причине классы-обертки Java и строки лучше всего подходят для использования в качестве ключей Map. 

map.put(user.getId(), new Account(...)); //User id cannot be changed

7. Варианты и альтернативы HashMap

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

7.1. Поддержание порядка вставки с помощью LinkedHashMap

LinkedHashMap хранит записи в том порядке, в котором они добавляются. В результате он обеспечивает предсказуемый порядок итерации. Обратите внимание, что порядок вставки не изменяется, если ключ повторно вставляется в карту. 

Map<String, String> linkedHashMap = new LinkedHashMap<>();linkedHashMap.put("key1", "value1");linkedHashMap.put("key2", "value2");

7.2 Сортировка ключей с помощью TreeMap

Если мы хотим отсортировать записи Map по ключам, TreeMap поможет. TreeMap сортируется в соответствии с естественным порядком его ключей или с помощью Comparator, предоставленного во время создания карты.

Обратите внимание, что поддержание порядка сортировки влечет за собой дополнительные затраты на операции вставки и изменения размера. 

Map<String, String> treeMap = new TreeMap<>();TreeMap<Integer, String> reversedMap = new TreeMap<>(Collections.reverseOrder());

7.3 Потокобезопасность с ConcurrentHashMap

ConcurrentHashMap очень похож на класс HashMap, за исключением того, что ConcurrentHashMap предлагает внутренне поддерживаемый параллелизм. Это означает, что нам не нужны синхронизированные блоки при доступе к его парам ключ-значение в многопоточном приложении. 

ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();

7.4 Эффективность памяти с WeakHashMap

Если мы не можем отслеживать записи, добавленные в Map, нам следует рассмотреть возможность использования WeakHashMap. Запись в WeakHashMap будет автоматически удалена, когда ее ключ больше не будет использоваться в обычных целях.

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

Map<String, String> weakMap = new WeakHashMap<>();

7.5 Взаимодействие и преобразование между типами карт

Мы можем создать экземпляр другого типа карты из существующего HashMap, используя конструкторы Map. Каждый класс Map содержит конструктор, который принимает другой тип Map и инициализирует текущую карту записями указанной карты.

В следующем примере мы создаем ConcurrentHashMap с записями, хранящимися в существующем HashMap. Этот метод может быть использован для любого вида преобразования Map. 

HashMap<String, String> hashMap = new HashMap<>();//add few entries// create ConcurrentHashMap with entries from HashMapConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>(hashMap);

8. Реальные примеры использования HashMap

HashMaps широко используются в различных реальных сценариях из-за их эффективного хранения и извлечения пар ключ-значение. Давайте рассмотрим несколько популярных применений:

8.1 Кэширование с помощью HashMap

HashMaps используются для реализации временных механизмов кэширования в небольших приложениях, где настройка и использование полноценного решения для кэширования будет излишним.

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

8.2 Подсчет частоты и встречаемости слов

HashMaps можно использовать для подсчета вхождений элементов или элементов в наборе данных, что делает их ценными для задач, связанных с анализом частот. Это очень полезно при обработке естественного языка и текста. 

String[] items = {"apple", "banana", "orange", "apple", "grape", "banana", "apple"};HashMap<String, Integer> itemOccurrences = new HashMap<>();for(String item : items) {itemOccurrences.put(item, itemOccurrences.getOrDefault(item, 0) + 1);}System.out.println(itemOccurrences); // {banana=2, orange=1, apple=3, grape=1}

8.3 Графовые алгоритмы

В алгоритмах графов(таких как обход графа и алгоритм кратчайшего пути) HashMap обычно используется для хранения узлов графа и их свойств. Он также может эффективно представлять представление списка смежности.

Использование HashMap делает эти алгоритмы эффективными и простыми в реализации.

10. Заключение

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

  • HashMap хранит пары ключ-значение(также называемые записями).
  • HashMap не может содержать повторяющиеся ключи.
  • HashMap допускает несколько значений NULL, но только один ключ NULL.
  • HashMap — неупорядоченная коллекция. Она не гарантирует какой-либо определенный порядок элементов.
  • HashMap не является потокобезопасным. Вы должны явно синхронизировать параллельные изменения в HashMap. Или вы можете использовать Collections.synchronizedMap(hashMap) для получения синхронизированной версии HashMap.
  • Значение можно получить только с помощью соответствующего ключа.
  • HashMap хранит только ссылки на объекты. Поэтому используйте класс-обертку или String для создания ключей Map.
  • HashMap реализует интерфейсы Cloneable и Serializable.

11. Примеры HashMap

Похожие посты

Прокрутить вверх