Как работает hashmap в java
Перейти к содержимому

Как работает hashmap в java

  • автор:

Как работает HashMap?

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

Нюансы которые стоит повторить и запомнить:
�� Общий принцип: внутренний массив table , содержащий бакеты (корзины) – списки элементов с одинаковыми пересчитанными хэш-суммами;
�� Пересчет хэш-суммы для умещения int индексов в capacity ячейках table ;
�� rehash – удвоение размера table при достижении threshold ( capacity*loadFactor ) занятых бакетов;
�� Невозможность сжать однажды раздувшийся table ;
�� Два способа разрешения коллизий: используемый в HashMap метод цепочек и альтернатива – открытая адресация;
�� Варианты для многопоточного использования: пересинхронизированная Hashtable и умная ConcurrentHashMap ;
�� Оптимизация Java 8: превращение списка в бакете в дерево при достижении 8 элементов – при большом количестве коллизий скорость доступа растет с O(n) до O(log(n));
�� Явное использование бакета 0 для ключа null ;
�� Связь с HashSet – HashMap , в котором используются только ключи;
�� Нет гарантий порядка элементов;

Обсуждая этот вопрос на интервью вы обязательно затронете особенности методов equals/hashCode. Возможно придется поговорить об альтернативных хранилищах ключ-значение – TreeMap, LinkedHashMap.

HashMap

HashMap — структура данных, одна из коллекций языка Java. Представляет собой хэш-таблицу. Так называется набор из пар «ключ-значение», где у ключей есть хэши, то есть числовые уникальные идентификаторы. Они высчитываются для каждого ключа.

Освойте профессию «Java-разработчик»

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

В HashMap ключом может быть практически что угодно, но важен в первую очередь хэш ключа.

Профессия / 14 месяцев
Java-разработчик

Освойте востребованный язык

Group 1321314345 (4)

Для чего нужен 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 месяцев.

Внутренняя работа HashMap в Java

[примечание от автора перевода] Перевод был выполнен для собственных нужд, но если кому -то это окажется полезным, значит мир стал хоть немного, но лучше! Оригинальная статья — Internal Working of HashMap in Java

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

Как и в предыдущей статье, HashMap содержит массив Node и Node может представлять класс, содержащий следующие объекты:

  1. int — хэш
  2. K — ключ
  3. V — значение
  4. Node — следующий элемент

Теперь мы увидим, как все это работает. Для начала мы рассмотрим процесс хеширования.

Хэширование

Хэширование -это процесс преобразования объекта в целочисленную форму, выполняется с помощью метода hashCode(). Очень важно правильно реализовать метод hashCode() для обеспечения лучшей производительности класса HashMap.

Здесь я использую свой собственный класс Key и таким образом могу переопределить метод hashCode() для демонстрации различных сценариев. Мой класс Key:

// специальный класс Key для переопределени методов hashCode() // и equals() class Key < String key; Key(String key) < this.key = key; >@Override public int hashCode() < return (int)key.charAt(0); >@Override public boolean equals(Object obj) < return key.equals((String)obj); >>

Здесь переопределенный метод hashCode() возвращает ASCII код первого символа строки. Таким образом, если первые символы строки одинаковые, то и хэш коды будут одинаковыми. Не стоит использовать подобную логику в своих программах.

Этот код создан исключительно для демонстрации. Поскольку HashCode допускает ключ типа null, хэш код null всегда будет равен 0.

Метод hashCode()

Метод hashCode() используется для получения хэш кода объекта. Метод hashCode() класса Object возвращает ссылку памяти объекта в целочисленной форме (идентификационный хеш (identity hash code)). Сигнатура метода public native hashCode() . Это говорит о том, что метод реализован как нативный, поскольку в java нет какого -то метода позволяющего получить ссылку на объект. Допускается определять собственную реализацию метода hashCode(). В классе HashMap метод hashCode() используется для вычисления корзины (bucket) и следовательно вычисления индекса.

Метод equals()

Метод equals используется для проверки двух объектов на равенство. Метод реализованн в классе Object. Вы можете переопределить его в своем собственном классе. В классе HashMap метод equals() используется для проверки равенства ключей. В случае, если ключи равны, метод equals() возвращает true, иначе false.

Корзины (Buckets)

Bucket -это единственный элемент массива HashMap. Он используется для хранения узлов (Nodes). Два или более узла могут иметь один и тот -же bucket. В этом случае для связи узлов используется структура данных связанный список. Bucket -ы различаются по ёмкости (свойство capacity). Отношение между bucket и capacity выглядит следующим образом:

capacity = number of buckets * load factor

Один bucket может иметь более, чем один узел, это зависит от реализации метода hashCode(). Чем лучше реализованн ваш метод hashCode(), тем лучше будут использоваться ваши bucket -ы.

Вычисление индекса в HashMap

Хэш код ключа может быть достаточно большим для создания массива. Сгенерированный хэш код может быть в диапазоне целочисленного типа и если мы создадим массив такого размера, то легко получим исключение outOfMemoryException. Потому мы генерируем индекс для минимизации размера массива. По сути для вычисления индекса выполняется следующая операция:

index = hashCode(key) & (n-1).

где n равна числу bucket или значению длины массива. В нашем примере я рассматриваю n, как значение по умолчанию равное 16.

  • изначально пустой hashMap: здесь размер hashmap равен 16:
HashMap map = new HashMap();

HashMap:

  • вставка пар Ключ — Значение: добавить одну пару ключ — значение в конец HashMap
map.put(new Key("vishal"), 20);
  1. Вычислить значение ключа . Оно будет сгенерированно, как 118.
  2. Вычислить индекс с помощью метода index , который будет равен 6.
  3. Создать объект node.

 < int hash = 118 // не строка, а // объект класса Key Key key = Integer value = 20 Node next = null >

Теперь HashMap выглядит примерно так:

  • добавление другой пары ключ — значение: теперь добавим другую пару
map.put(new Key("sachin"), 30);
  1. Вычислить значение ключа . Оно будет сгенерированно, как 115.
  2. Вычислить индекс с помощью метода index , который будет равен 3.
  3. Создать объект node.

 < int hash = 115 Key key = Integer value = 30 Node next = null >

Теперь HashMap выглядит примерно так:

  • в случае возникновения коллизий: теперь добавим другую пару
map.put(new Key("vaibhav"), 40);
  1. Вычислить значение ключа . Оно будет сгенерированно, как 118.
  2. Вычислить индекс с помощью метода index , который будет равен 6.
  3. Создать объект node.

 < int hash = 118 Key key = Integer value = 20 Node next = null >

Теперь HashMap выглядит примерно так:

[примечание от автора перевода] Изображение взято из оригинальной статьи и изначально содержит ошибку. Ссылка на следующий объект в объекте vishal с индексом 6 не равна null, в ней содержится указатель на объект vaibhav.

map.get(new Key("sachin"));
  1. Вычислить хэш код объекта . Он был сгенерирован, как 115.
  2. Вычислить индекс с помощью метода index , который будет равен 3.
  3. Перейти по индексу 3 и сравнить ключ первого элемента с имеющемся значением. Если они равны -вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.
  4. В нашем случае элемент найден и возвращаемое значение равно 30.
  • получаем значение по ключу vaibahv:
map.get(new Key("vaibhav"));
  1. Вычислить хэш код объекта . Он был сгенерирован, как 118.
  2. Вычислить индекс с помощью метода index , который будет равен 6.
  3. Перейти по индексу 6 и сравнить ключ первого элемента с имеющемся значением. Если они равны -вернуть значение, иначе выполнить проверку для следующего элемента, если он существует.
  4. В данном случае он не найден и следующий объект node не равен null.
  5. Если следующий объект node равен null, возвращаем null.
  6. Если следующий объект node не равен null, переходим к нему и повторяем первые три шага до тех пор, пока элемент не будет найден или следующий объект node не будет равен null.
// Java программа для иллюстрации // внутренней работы HashMap import java.util.HashMap; class Key < String key; Key(String key) < this.key = key; >@Override public int hashCode() < int hash = (int)key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; >@Override public boolean equals(Object obj) < return key.equals(((Key)obj).key); >> // Driver class public class GFG < public static void main(String[] args) < HashMap map = new HashMap(); map.put(new Key("vishal"), 20); map.put(new Key("sachin"), 30); map.put(new Key("vaibhav"), 40); System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); >>
hashCode for key: vishal = 118 hashCode for key: sachin = 115 hashCode for key: vaibhav = 118 hashCode for key: sachin = 115 Value for key sachin: 30 hashCode for key: vaibhav = 118 Value for key vaibhav: 40

Изменения в Java 8

Как мы уже знаем в случае возникновения коллизий объект node сохраняется в структуре данных «связанный список» и метод equals() используется для сравнения ключей. Это сравнения для поиска верного ключа в связанном списке -линейная операция и в худшем случае сложность равнa O(n).

Для исправления этой проблемы в Java 8 после достижения определенного порога вместо связанных списков используются сбалансированные деревья. Это означает, что HashMap в начале сохраняет объекты в связанном списке, но после того, как колличество элементов в хэше достигает определенного порога происходит переход к сбалансированным деревьям. Что улучшает производительность в худшем случае с O(n) до O(log n).

Важный момент

  1. Сложность операций get() и put() практически константна до тех пор, пока не будет проведенно повторное хэширование.
  2. В случае коллизий, если индексы двух и более объектов node одинаковые, объекты node соединяются с помощью связанного списка, т.е. ссылка на второй объект node хранится в первом, на третий во втором и т.д.
  3. Если данный ключ уже существует в HashMap, значение перезаписывается.
  4. Хэш код null равен 0.
  5. Когда объект получается по ключу происходят переходы по связанному списку до тех пор, пока объект не будет найден или ссылка на следующий объект не будет равна null.

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

Вы можете указать свои ёмкость и коэффициент загрузки, используя конструкторы 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.

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

Ваш адрес email не будет опубликован. Обязательные поля помечены *