HashMap
При работе с массивами я сравнивал их с коробочками. Слово HashMap содержит слово map — карта. Только это не пытайтесь найти сходство с картами в географическом атласе, с гуглокартами, с Яндекс.Картами или, на худой конец, с игральными картами. Это карточка в картотеке. Вы заполняете карточки какими-то данными и кладёте их в ящик. Если вы содержите гостиницу для котов, то скорее всего вы занесёте в карточку имя кота, возраст и т.п.
Класс HashMap использует хеш-таблицу для хранения карточки, обеспечивая быстрое время выполнения запросов get() и put() при больших наборах. Класс реализует интерфейс Map (хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. При этом все ключи обязательно должны быть уникальны, а значения могут повторяться. Данная реализация не гарантирует порядка элементов.
Общий вид HashMap:
// K - это Key (ключ), V - Value (значение) class HashMap
Объявить можно следующим образом:
Map hashMap = new HashMap(); // или так Map hashMap = new HashMap();
По умолчанию при использовании пустого конструктора создается картотека ёмкостью из 16 ячеек. При необходимости ёмкость увеличивается, вам не надо об этом задумываться.
Вы можете указать свои ёмкость и коэффициент загрузки, используя конструкторы HashMap(capacity) и HashMap(capacity, loadFactor). Максимальная ёмкость, которую вы сможете установить, равна половине максимального значения int (1073741824).
Добавление элементов происходит при помощи метода put(K key, V value). Вам надо указать ключ и его значение.
hashMap.put("0", "Васька");
hashMap.size();
Проверяем ключ и значение на наличие:
hashMap.containsKey("0"); hashMap.containsValue("Васька");
Выбираем все ключи:
for (String key : hashMap.keySet())
Выбираем все значения:
for (int value : hashMap.values())
Выбираем все ключи и значения одновременно:
for (Map.Entry entry : hashMap.entrySet())
Пример первый
// Создадим хеш-карточку Map hashMap = new HashMap<>(); // Помещаем данные на карточку hashMap.put("Васька", 5); hashMap.put("Мурзик", 8); hashMap.put("Рыжик", 12); hashMap.put("Барсик", 5); // Получаем набор элементов Set set = hashMap.entrySet(); // Отобразим набор for (Map.Entry me : set) < System.out.print(me.getKey() + ": "); System.out.println(me.getValue()); >// Добавляем значение int value = hashMap.get("Рыжик"); hashMap.put("Рыжик", value + 3); System.out.println("У Рыжика стало " + hashMap.get("Рыжик"));
Если вы посмотрите на результат, то увидите, что данные находятся не в том порядке, в котором вы заносили. Второй важный момент — если в карточке уже существует какой-то ключ, то если вы помещаете в него новое значение, то ключ перезаписывается, а не заносится новый ключ.
В древних версиях Java приходилось добавлять новые значения следующим образом.
hashMap.put("Мурзик", new Integer(8)); // или hashMap.put("Мурзик", Integer.valueOf(8));
Потом Java поумнела и стала самостоятельно переводить число типа int в объект Integer. Но это не решило основной проблемы — использование объектов очень сильно сказывается на потреблении памяти. Поэтому в Android были предложены аналоги этого класса (см. ниже). Ключом в Map может быть любой объект, у которого корректно реализованы методы hashCode() и equals().
Пример второй
Так как ключи являются уникальными, мы можем написать следующую программу — сгенерируем набор случайных чисел сто раз и посчитаем количество повторов. Map легко решит эту задачу — в качестве ключа используется сгенерированное число, а в качестве значения — количество повторов.
Random random = new Random(36); Map hashMap = new HashMap<>(); for (int i = 0; i < 100; i++)< // Создадим число от 0 до 10 int number = random.nextInt(10); Integer frequency = hashMap.get(number); hashMap.put(number, frequency == null ? 1 : frequency + 1); >System.out.println(hashMap);
Метод get() возвращает null, если ключ отсутствует, т.е число было сгенерировано впервые или в противном случае метод возвращает для данного ключа ассоциированное значение, которое увеличивается на единицу.
Пример третий
Пример для закрепления материала. Поработаем с объектами классов. Нужно самостоятельно создать класс Pet и его наследников Cat, Dog, Parrot.
Создадим отображение из домашних животных, где в качестве ключа выступает строка, а в качестве значения класс Pet.
Map hashMap = new HashMap<>(); hashMap.put("Кот", new Cat("Мурзик")); hashMap.put("Собака", new Dog("Бобик")); hashMap.put("Попугай", new Parrot("Кеша")); System.out.println(hashMap); Pet cat = hashMap.get("Кот"); System.out.println(cat); System.out.println(hashMap.containsKey("Кот")); System.out.println(hashMap.containsValue(cat));
Многомерные отображения
Контейнеры Map могут расширяться до нескольких измерений, достаточно создать контейнер Map, значениями которого являются контейнеры Map (значениями которых могут быть другие контейнеры). Предположим, вы хотите хранить информацию о владельцах домашних животных, у каждого из которых может быть несколько любимцев. Для этого нам нужно создать контейнер Map>.
Map> personMap = new HashMap<>(); personMap.put(new Person("Иван"), Arrays.asList(new Cat("Барсик"), new Cat("Мурзик"))); personMap.put(new Person("Маша"), Arrays.asList(new Cat("Васька"), new Dog("Бобик"))); personMap.put(new Person("Ирина"), Arrays.asList(new Cat("Рыжик"), new Dog("Шарик"), new Parrot("Гоша"))); System.out.println("personMap: " + personMap); System.out.println("personMap.keySet(): " + personMap.keySet()); for(Person person : personMap.keySet()) < System.out.println(person + " имеет"); for (Pet pet : personMap.get(person))< System.out.println(" " + pet); >>
Метод keySet() возвращает контейнер Set, содержащий все ключи из personMap, который используется в цикле для перебора элементов Map.
Sparse arrays — аналог в Android
Разработчик Android посчитали, что HashMap не слишком оптимизирован для мобильных устройств и предложили свой вариант в виде специальных массивов. Данные классы являются родными для Android, но не являются частью Java. Очень рекомендуют использовать именно Android-классы. Не все программисты знают об этих аналогах, а также классический код может встретиться в различных Java-библиотеках. Если вы увидите такой код, то заменить его на нужный. Ниже представлена таблица для замены.
| HashMap | Array class |
|---|---|
| HashMap | ArrayMap |
| HashMap | SparseArray |
| HashMap | SparseBooleanArray |
| HashMap | SparseIntArray |
| HashMap | SparseLongArray |
| HashMap | LongSparseArray |
Существует ещё класс HashTable, который очень похож в использовании как и HashMap.
Разница между HashMap и Hashtable в Java?
Оба HashTable и HashMap реализуют интерфейс карты, но между ними существуют некоторые различия. Они есть:
- Безопасность потоков (синхронизировано)
- Нулевые ключи
- Наследование
- Производительность
- Траверс
- Сбой
- Сложность по времени
- Наследие
Безопасность потоков (синхронизировано)
Первым и самым значительным различием между Hashtable и HashMap является то, что HashMap не является потокобезопасным (несинхронизированным), тогда как Hashtable представляет собой потокобезопасную (синхронизированную) коллекцию. Это делает HashMap лучше для не-потоковых приложений, поскольку несинхронизированные объекты обычно работают лучше, чем синхронизированные.
Первым и самым значительным различием между Hashtable и HashMap является то, что HashMap не является потокобезопасным (несинхронизированным), тогда как Hashtable представляет собой потокобезопасную (синхронизированную) коллекцию. Это делает HashMap лучше для не-потоковых приложений, поскольку несинхронизированные объекты обычно работают лучше, чем синхронизированные.
Вы можете сделать HashMap потокобезопасным (синхронизированным), вызвав этот код
Map mp = Collections.synchronizedMap(hashMap);
Null Keys
HashTable может содержать только ненулевой объект в качестве ключа или в качестве значения. Чтобы хранить и извлекать объекты из хеш-таблицы, объекты, используемые в качестве ключей, должны реализовывать метод hashCode и метод equals. Поскольку «null» не является объектом, вы не можете вызывать на нем .equals() или .hashCode(), поэтому Hashtable не может вычислить хэш, чтобы использовать его в качестве ключа.
Наследование
Хотя оба интерфейса HashMap и HashTable реализуют интерфейс Map, но они расширяют два разных класса. HashMap расширяет класс AbstractMap, где, поскольку HashTable расширяет класс Dictionary, который является унаследованным классом в JDK.
Производительность
HashMap не синхронизирован, поэтому он работает быстро. HashTable внутренне синхронизирован, что делает HashTable немного медленнее, чем HashMap. Несинхронизированные объекты часто намного лучше в производительности по сравнению с синхронизированным объектом, например Hashtable, в однопоточной среде.
Traverse
HashMap проходит через Iterator, а Hashtable проходит через Enumerator и Iterator.
Безотказная
Итератор в HashMap является отказоустойчивым, а перечислитель для Hashtable — нет. Отказоустойчивость относится к контексту итераторов. Если итератор был создан в объекте коллекции, а какой-либо другой поток пытается изменить объект коллекции «структурно», будет выбрано исключение параллельной модификации.
Сложность времени
Hashtable использует целую цепочку (со связанными списками) в качестве стратегии обработки столкновений, ограничивающей время поиска O (n). Начиная с JAVA 8 HashMap использует Balanced Tree в качестве стратегии разрешения конфликтов, которая имеет ограниченное временное время O (log n).
Наследство
HashMap является членом Java Collection Framework с самого начала его внедрения в JDK 1.2. Но HashTable был там до JDK 1.2, и он расширяет класс Dictionary, который является унаследованным классом в JDK. Из JDK 1.2 было сделано для реализации интерфейса Map, что делает его членом коллекции.
Внедрение HashMap
import Java.util.*; class TestClass < public static void main (String[] args) < // Создание HashMap HashMap < Integer,String >days = new HashMap < Integer,String >(); // Добавление пар ключ / значение days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); Set < Map.Entry < Integer,String >> set = days.entrySet(); for (Map.Entry < Integer,String >sg : set) < System.out.println("Key :"+sg.getKey() + " Value :"+days.get(sg.getKey())); >> >
Выход
Key :1 Value :Sunday Key :2 Value :Monday Key :3 Value :Tuesday Key :4 Value :Wednesday
Как создать документ Excel программно
import Java.util.*; class TestClass < public static void main (String[] args) < // Как создать Hashtable? Hashtable < Integer,String >days = new Hashtable < Integer,String >(); // Как добавить пары «ключ / значение» в Hashtable? days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); days.put(5,"Thursday"); days.put(6,"Friday"); days.put(7,"Saturday"); // Как проходить через Hashtable? for(Map.Entry m:days.entrySet()) < System.out.println(m.getKey()+" "+m.getValue()); >> >
Выход
7 Saturday 6 Friday 5 Thursday 4 Wednesday 3 Tuesday 2 Monday 1 Sunday
Как вычисляется длина хеш-таблицы?
Уважаемые коллеги, столкнулся с таким вопросом касаемо хэш-таблицы, подскажите пожалуйста: Понятно что каждая ячейка массива может быть либо связанным списком, либо деревом. А как определяется длинна самого массива? Есть ли какой-то обобщенный принцип что-бы мы могли сказать что-то вроде: «контекст в котором данная таблица будет использована, такой-то такой-то, и поэтому мы считаем длину ее массива по такой-то формуле.» Или какие-нибудь, твердо обосновывающие решение о длине критерии, которыми необходимо руководствоваться, при создании своей таблицы?
Отслеживать
22k 3 3 золотых знака 27 27 серебряных знаков 37 37 бронзовых знаков
задан 27 янв 2017 в 15:22
5,297 11 11 золотых знаков 58 58 серебряных знаков 116 116 бронзовых знаков
HashMap
HashMap — структура данных, одна из коллекций языка Java. Представляет собой хэш-таблицу. Так называется набор из пар «ключ-значение», где у ключей есть хэши, то есть числовые уникальные идентификаторы. Они высчитываются для каждого ключа.
Освойте профессию «Java-разработчик»
Общее название сущности, которая хранит в себе ключи и значения, — ассоциативный массив. То есть структура данных, похожая на массив, где вместо индексов — ключи. Самый очевидный пример — простая таблица, где заголовок является ключом.
В HashMap ключом может быть практически что угодно, но важен в первую очередь хэш ключа.
Профессия / 14 месяцев
Java-разработчик
Освойте востребованный язык
Для чего нужен HashMap
HashMap пользуются разработчики на Java. Как и все структуры, относящиеся к коллекциям, он нужен в первую очередь для хранения информации и работы с ней. HashMap быстро работает, и большинство операций в нем выполняется за фиксированное время — это происходит благодаря оптимизированному доступу к данным. Как и практически все структуры из Collections Framework, он динамический, то есть его размер не фиксирован — туда можно добавить практически любое количество объектов.
HashMap используется, когда разработчику нужно хранить где-то пары «ключ-значение», при этом иметь возможность быстро получить значение по ключу. Например, имя пользователя и номер его телефона. Если нужно хранить просто список значений, лучше подойдет ArrayList или похожая структура.
Как устроены хэш-таблицы
HashMap — структура из пар «ключ-значение». Внутри это динамический массив ключей. Каждый элемент массива — своеобразная «корзинка», которая хранит связанный список со значением. О том, что собой представляет каждая из этих сущностей, можно почитать в статьях про ArrayList и коллекции.
Но HashMap используют для хранения пар — на каждый ключ приходится только одно значение. То есть связанный список будет состоять из одного элемента, а ссылаться этот элемент будет на null — специальное «пустое» значение. Если бы в такой структуре значений было несколько, первое ссылалось бы на второе и так далее — так устроен связанный список.
Связанный список нужен, чтобы избежать коллизий. Мы подробнее расскажем об этом ниже.
Для оптимизации доступа используется хэш ключа. Когда в HashMap добавляют ключ и значение, для ключа сразу высчитывается хэш. По нему определяется позиция в массиве для этой пары: для расчета есть специальные формулы.
Станьте Java-разработчиком
и создавайте сложные сервисы
на востребованном языке
Реализация и свойства HashMap
HashMap — динамическая структура, то есть количество «корзинок» может изменяться. По умолчанию сущность создается с 16 «корзинками», но это поведение можно поменять при создании, для чего надо задать хэш-таблице начальный размер вручную. Когда элементов в ней становится больше, чем корзинок, структура удлиняется — перезаписывает массив на новый, с большей длиной. По умолчанию длина увеличивается вдвое.
У HashMap, как и у всех подобных структур, есть набор своих методов — функций, которые позволяют удобно работать с данными. Для добавления, поиска, перезаписи или удаления элемента есть свои команды; также можно перебирать элементы и ключи и делать многое другое. Благодаря использованию хэшей эти методы работают очень быстро, и для самых популярных из них время выполнения константно, если нет коллизий.
Коллизии и их предотвращение
В идеальной ситуации хэш полностью индивидуален для каждого уникального объекта. Но в реальности хэши могут совпадать у совершенно разных объектов. Это происходит из-за несовершенства существующих алгоритмов.
Может случиться так, что у двух разных ключей окажется одинаковый хэш. Или хэш будет разным, но по формуле позиция для обоих хэшей будет одинаковой. Тогда значения обоих ключей окажутся записаны в одну «корзинку». Это и есть коллизия. Именно из-за коллизий для хранения значений используется связанный список: если бы в массиве просто хранился объект, любая коллизия перезаписала бы текущее значение, а это опасно. А при текущей реализации, даже если случится коллизия, новое значение просто запишется в начало той же «корзинки», не изменив старое.
Если такое случится, структура потеряет эффективность и будет работать медленнее, поэтому коллизий все равно лучше не допускать, но сами данные останутся целы.
Отличие от перезаписи
HashMap умеет отличать коллизию от реальной перезаписи элемента. Когда структуре дают новую пару «ключ-значение», она проверяет, есть ли в массиве такие хэши и такие ключи. Результат такой:
- если таких хэшей и ключей нет, в хэш-таблицу просто добавляется новая пара;
- если такой ключ есть, это перезапись — структура переписывает элемент с таким же ключом;
- если такого ключа нет, но хэш есть — это коллизия, новое значение записывается в ту же «корзинку» за предыдущим.
Вы можете узнать больше про структуры данных в Java. Получите новую профессию на курсах и станьте разработчиком на популярном языке.
Java-разработчик
Java уже 20 лет в мировом топе языков программирования. На нем создают сложные финансовые сервисы, стриминги и маркетплейсы. Освойте технологии, которые нужны для backend-разработки, за 14 месяцев.