Java util hashmap

HashMap

При работе с массивами я сравнивал их с коробочками. Слово HashMap содержит слово map — карта. Только это не пытайтесь найти сходство с картами в географическом атласе, с гуглокартами, с Яндекс.Картами или, на худой конец, с игральными картами. Это карточка в картотеке. Вы заполняете карточки какими-то данными и кладёте их в ящик. Если вы содержите гостиницу для котов, то скорее всего вы занесёте в карточку имя кота, возраст и т.п.

Класс HashMap использует хеш-таблицу для хранения карточки, обеспечивая быстрое время выполнения запросов get() и put() при больших наборах. Класс реализует интерфейс Map (хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. При этом все ключи обязательно должны быть уникальны, а значения могут повторяться. Данная реализация не гарантирует порядка элементов.

Общий вид HashMap:

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

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

Вы можете указать свои ёмкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная ёмкость, которую вы сможете установить, равна половине максимального значения int (1073741824).

Добавление элементов происходит при помощи метода put(K key, V value). Вам надо указать ключ и его значение.

Проверяем ключ и значение на наличие:

Выбираем все ключи:

Выбираем все значения:

Выбираем все ключи и значения одновременно:

Пример первый

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

В древних версиях Java приходилось добавлять новые значения следующим образом.

Потом Java поумнела и стала самостоятельно переводить число типа int в объект Integer. Но это не решило основной проблемы — использование объектов очень сильно сказывается на потреблении памяти. Поэтому в Android были предложены аналоги этого класса (см. ниже). Ключом в Map может быть любой объект, у которого корректно реализованы методы hashCode() и equals().

Пример второй

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

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

Пример третий

Пример для закрепления материала. Поработаем с объектами классов. Нужно самостоятельно создать класс Pet и его наследников Cat, Dog, Parrot.

Создадим отображение из домашних животных, где в качестве ключа выступает строка, а в качестве значения класс Pet.

Многомерные отображения

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

Метод keySet() возвращает контейнер Set, содержащий все ключи из personMap, который используется в цикле для перебора элементов Map.

Sparse arrays — аналог в Android

Разработчик Android посчитали, что HashMap не слишком оптимизирован для мобильных устройств и предложили свой вариант в виде специальных массивов. Данные классы являются родными для Android, но не являются частью Java. Очень рекомендуют использовать именно Android-классы. Не все программисты знают об этих аналогах, а также классический код может встретиться в различных Java-библиотеках. Если вы увидите такой код, то заменить его на нужный. Ниже представлена таблица для замены.

Существует ещё класс HashTable, который очень похож в использовании как и HashMap.

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

HashMap является частью коллекции Java начиная с Java 1.2. Он обеспечивает базовую реализацию интерфейса Map Java. Хранит данные в парах (ключ, значение). Чтобы получить доступ к значению, нужно знать его ключ. HashMap известен как HashMap, потому что он использует технику, называемую Hashing. Хеширование — это метод преобразования большой строки в маленькую строку, представляющую одну и ту же строку. Более короткое значение помогает в индексации и ускоряет поиск. HashSet также использует HashMap для внутреннего использования. Он внутренне использует список ссылок для хранения пар ключ-значение, которые подробно описаны в HashSet и в других статьях.
Несколько важных функций HashMap:

• HashMap является частью пакета java.util.
• HashMap расширяет абстрактный класс AbstractMap, который также обеспечивает неполную реализацию интерфейса Map.
• Он также реализует интерфейс Cloneable и Serializable . K и V в вышеприведенном определении представляют Ключ и Значение соответственно.
• HashMap не позволяет дублировать ключи, но позволяет дублировать значения. Это означает, что один ключ не может содержать более 1 значения, но более 1 ключа может содержать одно значение.
• HashMap допускает также нулевой ключ, но только один раз и несколько нулевых значений.
• Этот класс не дает никаких гарантий относительно порядка карты; в частности, это не гарантирует, что порядок останется постоянным с течением времени. Это примерно похоже на HashTable, но не синхронизировано.

Внутренняя структура HashMap

Внутренне HashMap содержит массив Node, а узел представлен в виде класса, который содержит 4 поля:

1. int hash
2. К ключ
3. Значение V
4. Узел следующий

Видно, что узел содержит ссылку на свой собственный объект. Так что это связанный список.
HashMap:

Производительность HashMap

Производительность HashMap зависит от 2 параметров:

1. Начальная емкость
2. Коэффициент нагрузки

Как уже говорилось, Capacity — это просто количество сегментов, тогда как Initial Capacity — это емкость экземпляра HashMap при его создании. Коэффициент загрузки — это показатель, который при повторной перемотке должен быть выполнен. Перефразировка — это процесс увеличения емкости. В HashMap емкость умножается на 2. Коэффициент загрузки также является мерой того, какую долю HashMap можно заполнить перед повторной перепрошивкой. Когда количество записей в HashMap увеличивает произведение текущей емкости и коэффициента загрузки, увеличивается емкость, выполняется перефразировка. Если первоначальная емкость сохраняется выше, то перефразировка никогда не будет выполнена. Но поддерживая его выше, это увеличивает временную сложность итерации. Поэтому его следует выбирать очень умно, чтобы повысить производительность. Ожидаемое количество значений должно быть принято во внимание, чтобы установить начальную емкость. Наиболее предпочтительное значение коэффициента нагрузки составляет 0,75, что обеспечивает значительную экономию времени и пространства. Значение коэффициента нагрузки варьируется от 0 до 1.

Синхронизированный HashMap

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

Теперь карта m синхронизирована.

Итераторы этого класса работают быстро, если какая-либо модификация структуры выполняется после создания итератора, любым способом, кроме метода удаления итератора. В случае сбоя итератора он выдаст исключение ConcurrentModificationException.

Конструкторы в HashMap

HashMap предоставляет 4 конструктора, и модификатор доступа каждого является общедоступным:

1. HashMap (): это конструктор по умолчанию, который создает экземпляр HashMap с начальной емкостью 16 и коэффициентом загрузки 0,75.
2. HashMap (int начальная емкость): создается экземпляр HashMap с указанной начальной емкостью и коэффициентом загрузки 0,75.
3. HashMap (int начальная емкость, float loadFactor): создает экземпляр HashMap с указанной начальной емкостью и указанным коэффициентом загрузки.
4. HashMap (Карта карты): создает экземпляр HashMap с теми же отображениями, что и указанная карта.

Пример:

// Java-программа для иллюстрации
// Java.util.HashMap

public class GFG <

public static void main(String[] args)

map.put( «vishal» , 10 );

map.put( «sachin» , 30 );

map.put( «vaibhav» , 20 );

System.out.println( «Size of map is:- «

if (map.containsKey( «vishal» )) <

Integer a = map.get( «vishal» );

System.out.println( «value for key»

public static void print(Map map)

System.out.println( «map is empty» );

Временная сложность HashMap

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

Методы в HashMap

1. void clear (): Используется для удаления всех отображений с карты.
2. boolean containsKey (Object key): используется для возврата True, если для указанного ключа отображение присутствует на карте.
3. boolean containsValue (Object value): используется для возврата true, если один или несколько ключей сопоставлены с указанным значением.
4. Object clone (): используется для возврата поверхностной копии упомянутой хэш-карты.
5. boolean isEmpty (): Используется, чтобы проверить, является ли карта пустой или нет. Возвращает true, если карта пуста.
6. Set entrySet (): используется для возврата установленного представления хэш-карты.
7. Object get (Object key): используется для извлечения или извлечения значения, сопоставленного определенному ключу.
8. Set keySet (): используется для возврата установленного вида ключей.
9. int size (): используется для возврата размера карты.
10. Object put (Object key, Object value): используется для вставки определенного отображения пары ключ-значение в карту.
11. putAll (Карта M): используется для копирования всех элементов с одной карты на другую.
12. Удаление объекта (ключ объекта): используется для удаления значений любого конкретного ключа на карте.
13. Collection values (): используется для возврата представления Collection значений в HashMap.
14. compute (клавиша K, BiFunction remappingFunction) : этот метод пытается вычислить сопоставление для указанного ключа и его текущего сопоставленного значения (или ноль, если текущего сопоставления нет).
15. computeIfAbsent (ключ K, функция mappingFunction) : этот метод, если указанный ключ еще не связан со значением (или сопоставлен со значением NULL), пытается вычислить его значение с использованием данной функции сопоставления и вводит его в эту карту, если только значение NULL.
16. computeIfPresent (ключ K, BiFunction remappingFunction): этот метод, если значение для указанного ключа присутствует и не равно нулю, пытается вычислить новое сопоставление, учитывая ключ и его текущее сопоставленное значение.
17. forEach (действие BiConsumer ): этот метод выполняет заданное действие для каждой записи в этой карте, пока все записи не будут обработаны или действие не вызовет исключение.
18. getOrDefault (Object key, V defaultValue): этот метод возвращает значение, которому сопоставлен указанный ключ, или defaultValue, если эта карта не содержит сопоставления для ключа.
19. слияние (ключ K, значение V, BiFunction remappingFunction): этот метод, если указанный ключ еще не связан со значением или связан с нулевым значением, связывает его с заданным ненулевым значением.
20. putIfAbsent (ключ K, значение V): этот метод, если указанный ключ еще не связан со значением (или сопоставлен со значением NULL), связывает его с данным значением и возвращает значение NULL, иначе возвращается текущее значение.
21. replace (ключ K, значение V): этот метод заменяет запись для указанного ключа, только если она в настоящий момент сопоставлена с некоторым значением.
22. replace (ключ K, V oldValue, V newValue): этот метод заменяет запись для указанного ключа, только если в данный момент отображается на указанное значение.
23. replaceAll (функция BiFunction ): этот метод заменяет значение каждой записи на результат вызова данной функции для этой записи, пока все записи не будут обработаны или функция не выдаст исключение.

Статьи по Теме:

Эта статья предоставлена Вишалом Гаргом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Набор данных интерфейса Map

Интерфейс Map располагается на вершине иерархии в Java Collection. Он входит в состав JDK начиная с версии 1.2, предоставляя разработчику базовые методы для работы с данными вида «ключ — значение». Функции интерфейса расширяются вместе с развитием технологий Java. Полную англоязычную документацию интерфейса Map можно найти здесь.

Иерархия интерфейса Map представлена на рисунке.

Наиболее часто используемые методы интерфейса Map

Описание Hashtable

Класс Hashtable позволяет реализовывать структуру данных типа hash-таблица, содержащую пары вида «ключ — значение». Значение «null» в качестве значения или ключа использовать нельзя. Hashtable является синхронизированной, т.е. почти все методы помечены как synchronized, в связи с чем могут быть проблемы с производительностью.

Экземпляр Hashtable включает два параметра, влияющие на его производительность. Это начальная емкость и коэффициент загрузки. Начальная емкость формируется на этапе создания объекта.

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

Полную документацию по Hashtable можно найти здесь.

Конструкторы Hashtable

• Hashtable()
  Создание хеш-таблицы с емкостью по умолчанию (11 записей) и коэффициент загрузки по умолчанию (0.75).
• Hashtable(int initialCapacity)
  Создание хеш-таблицы с указанной начальной емкостью и коэффициентом загрузки по умолчанию (0.75).
• Hashtable(int initialCapacity, float loadFactor)
  Создание хеш-таблицы с указанной начальной емкостью и указанным коэффициентом загрузки.
• Hashtable(Map t)
  Создание хеш-таблицы с указанными параметрами.

Дополнительные методы Hashtable

Hashtable реализует все методы интерфейса Map и включает дополнительно следующие методы :

В качестве примера рассмотрим задачу организации небольшого телефонного справочника с помощью Hashtable, позволяющего использовать механизм хеш-таблиц для эффективного поиска записей по ключу. С помощью метода put программа добавляет новые записи в хеш-таблицу. Извлечение записей выполняется методом get, которому в качестве параметра передается ключ.

Пример телефонного справочника, содержащего имена и телефоны :

Для добавления записей используется метод put, которому в качестве параметров передается «ключ» (первый параметр — имя) и «значение» (второй параметр — телефон). Для чтения списка ключей используется метод keys класса Hashtable, который возвращает объект класса Enumeration.

Условие завершения цикла — возвращение методом hasMoreElements значения «false». С помощью метода nextElement в цикле извлекаются все значения ключей, а затем методом get получаем соответствующие этим ключам значения.

Набор данных HashMap

Набор данных HashMap является альтернативой Hashtable. Основными отличиями от Hashtable являются то, что HashMap не синхронизирован и позволяет использовать null как в качестве ключа, так и значения.

Также как и Hashtable, коллекция HashMap не является упорядоченной: порядок хранения элементов зависит от хэш-функции. Реализация HashMap обеспечивает постоянно-разовую производительность для основных операций (get и put).

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

Полную документацию по HashMap можно найти здесь.

Конструкторы и описание HashMap

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

Результат работы программы :

Хэш-таблицы LinkedHashMap

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

Конструкторы и описание LinkedHashMap

Полную документацию по LinkedHashMap можно найти здесь.

Пример использования LinkedHashMap :

Результат работы программы :

Набор данных TreeMap

TreeMap, как и LinkedHashMap, является упорядоченным набором данных. По-умолчанию, TreeMap сортируется по ключам с использованием принципа «natural ordering». Но это поведение может быть настроено под конкретную задачу при помощи объекта Comparator, который указывается в качестве параметра при создании объекта TreeMap.

Конструкторы и описание TreeMap

Полную документацию по TreeMap можно найти здесь.

Структуры данных в картинках. HashMap

Приветствую вас, хабрачитатели!

Продолжаю попытки визуализировать структуры данных в Java. В предыдущих сериях мы уже ознакомились с ArrayList и LinkedList, сегодня же рассмотрим HashMap.

HashMap — основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Разрешение коллизий осуществляется с помощью метода цепочек.

Создание объекта

Новоявленный объект hashmap, содержит ряд свойств:

• table — Массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений;
• loadFactor — Коэффициент загрузки. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных;
• threshold — Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
• size — Количество элементов HashMap-а;

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

Вы можете указать свои емкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная емкость, которую вы сможете установить, равна половине максимального значения int (1073741824).

Добавление элементов

При добавлении элемента, последовательность шагов следующая:

Сначала ключ проверяется на равенство null. Если это проверка вернула true, будет вызван метод putForNullKey(value) (вариант с добавлением null-ключа рассмотрим чуть позже).

Далее генерируется хэш на основе ключа. Для генерации используется метод hash(hashCode), в который передается key.hashCode().

Комментарий из исходников объясняет, каких результатов стоит ожидать — метод hash(key) гарантирует что полученные хэш-коды, будут иметь только ограниченное количество коллизий (примерно 8, при дефолтном значении коэффициента загрузки).

В моем случае, для ключа со значением »0» метод hashCode() вернул значение 48, в итоге:

С помощью метода indexFor(hash, tableLength), определяется позиция в массиве, куда будет помещен элемент.

При значении хэша 51 и размере таблице 16, мы получаем индекс в массиве:

Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Хэш и ключ нового элемента поочередно сравниваются с хэшами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается.

Если же предыдущий шаг не выявил совпадений, будет вызван метод addEntry(hash, key, value, index) для добавления нового элемента.

Для того чтобы продемонстрировать, как заполняется HashMap, добавим еще несколько элементов.

Пропускается, ключ не равен null

Определение позиции в массиве

Подобные элементы не найдены

Footprint
Object size: 376 bytes

Как было сказано выше, если при добавлении элемента в качестве ключа был передан null, действия будут отличаться. Будет вызван метод putForNullKey(value), внутри которого нет вызова методов hash() и indexFor() (потому как все элементы с null-ключами всегда помещаются в table[0]), но есть такие действия:

Все элементы цепочки, привязанные к table[0], поочередно просматриваются в поисках элемента с ключом null. Если такой элемент в цепочке существует, его значение перезаписывается.

Если элемент с ключом null не был найден, будет вызван уже знакомый метод addEntry().

Footprint
Object size: 496 bytes

Теперь рассмотрим случай, когда при добавлении элемента возникает коллизия.

Пропускается, ключ не равен null

Определение позиции в массиве

Подобные элементы не найдены

Resize и Transfer

Когда массив table[] заполняется до предельного значения, его размер увеличивается вдвое и происходит перераспределение элементов. Как вы сами можете убедиться, ничего сложного в методах resize(capacity) и transfer(newTable) нет.

Метод transfer() перебирает все элементы текущего хранилища, пересчитывает их индексы (с учетом нового размера) и перераспределяет элементы по новому массиву.

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

Удаление элементов

У HashMap есть такая же «проблема» как и у ArrayList — при удалении элементов размер массива table[] не уменьшается. И если в ArrayList предусмотрен метод trimToSize(), то в HashMap таких методов нет (хотя, как сказал один мой коллега — «А может оно и не надо?«).

Небольшой тест, для демонстрации того что написано выше. Исходный объект занимает 496 байт. Добавим, например, 150 элементов.

Теперь удалим те же 150 элементов, и снова замерим.

Как видно, размер даже близко не вернулся к исходному. Если есть желание/потребность исправить ситуацию, можно, например, воспользоваться конструктором HashMap(Map).

Итераторы

HashMap имеет встроенные итераторы, такие, что вы можете получить список всех ключей keySet(), всех значений values() или же все пары ключ/значение entrySet(). Ниже представлены некоторые варианты для перебора элементов:

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

Итоги

— Добавление элемента выполняется за время O(1), потому как новые элементы вставляются в начало цепочки;
— Операции получения и удаления элемента могут выполняться за время O(1), если хэш-функция равномерно распределяет элементы и отсутствуют коллизии. Среднее же время работы будет Θ(1 + α), где α — коэффициент загрузки. В самом худшем случае, время выполнения может составить Θ(n) (все элементы в одной цепочке);
— Ключи и значения могут быть любых типов, в том числе и null. Для хранения примитивных типов используются соответствующие классы-оберки;
— Не синхронизирован.

Ссылки

Инструменты для замеров — memory-measurer и Guava (Google Core Libraries).