Hashmap в java как работает

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

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

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

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

Map hashmap = new HashMap();

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

 // Инициализация хранилища в конструкторе // capacity - по умолчанию имеет значение 16 table = new Entry[capacity]; 

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

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

hashmap.put("0", "zero");

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

 static int hash(int h) < h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); > 

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

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

 h ^ (h >>> 20) ^ (h >>> 12) = 48 h ^ (h >>> 7) ^ (h >>> 4) = 51 

 static int indexFor(int h, int length)

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

 h & (length - 1) = 3 

 if (e.hash == hash && (e.key == key || key.equals(e.key)))

 void addEntry(int hash, K key, V value, int index) < Entrye = table[index]; table[index] = new Entry(hash, key, value, e); . > 

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

hashmap.put("key", "one");

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

 h ^ (h >>> 20) ^ (h >>> 12) = 106054 h ^ (h >>> 7) ^ (h >>> 4) = 99486 

 h & (length - 1) = 14 

hashmap.put(null, null);

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

addEntry(0, null, value, 0);

hashmap.put("idx", "two");

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

 h ^ (h >>> 20) ^ (h >>> 12) = 104100 h ^ (h >>> 7) ^ (h >>> 4) = 101603 

 h & (length - 1) = 3 

 // В table[3] уже хранится цепочка состоящая из элемента ["0", "zero"] Entry e = table[index]; // Новый элемент добавляется в начало цепочки table[index] = new Entry(hash, key, value, e); 

Resize и Transfer

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

 void resize(int newCapacity) < if (table.length == MAXIMUM_CAPACITY) < threshold = Integer.MAX_VALUE; return; >Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); > 

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

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

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

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

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

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

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

 hashmap = new HashMap(hashmap); 

Итераторы

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

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

Как работает 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.put()?

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

1. Вычисляется хэш ключа. Если ключ null , хэш считается равным 0 . Чтобы достичь лучшего распределения, результат вызова hashCode() «перемешивается»: его старшие биты XOR-ятся на младшие.

2. Значения внутри хэш-таблицы хранятся в специальных структурах данных – нодах, в массиве. Из хэша высчитывается номер бакета – индекс для значения в этом массиве. Полученный хэш обрезается по текущей длине массива. Длина – всегда степень двойки, так что для скорости используется битовая операция & .

3. В бакете ищется нода. В ячейке массива лежит не просто одна нода, а связка всех нод, которые туда попали. Исполнение проходит по этой связке (цепочке или дереву), и ищет ноду с таким же ключом. Ключ сравнивается с имеющимися сначала на == , затем на equals .

4. Если нода найдена – её значение просто заменяется новым. Работа метода на этом завершается.

5. Если ноды с таким же ключом в бакете пока нет – добавляемая пара ключ-значение запаковывается в новый объект типа Node, и прикрепляется к структуре существующих нод бакета. Ноды составляют структуру за счет того, что в ноде хранится ссылка на следующий элемент (для дерева – следующие элементы). Кроме самой пары и ссылок, чтобы потом не считать заново, записывается и хэш ключа.

6. В случае, когда структурой была цепочка а не дерево, и длина цепочки превысила 7 элементов – происходит процедура treeification – превращение списка в самобалансирующееся дерево. В случае коллизии это ускоряет доступ к элементам на чтение с O(n) до O(log(n)). У comparable-ключей для балансировки используется их естественный порядок. Другие ключи балансируются по порядку имен их классов и значениям identityHashCode-ов. Для маленьких хэш-таблиц (< 64 бакетов) «одеревенение» заменяется увеличением (см. п.8).

7. Если новая нода попала в пустую ячейку, заняла новый бакет – увеличивается счетчик структурных модификаций. Изменение этого счетчика сообщит всем итераторам контейнера, что при следующем обращении они должны выбросить ConcurrentModificationException .

8. Когда количество занятых бакетов массива превысило пороговое (capacity * load factor), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш – все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера.

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

Очень часто на собеседованиях задают вопросы такого рода, как “Как работает HashMap в Java?”, “Каков внутренний механизм работы методов get и put в HashMap?”. Тут я попытаюсь объяснить внутреннюю функциональность на простом примере. Не вдаваясь в теорию, мы начнем с примера, чтобы вы лучше поняли, а затем и увидели, как работают методы get и put в Java. Возьмем очень простой пример. У нас есть класс Country (англ. “страна”), мы будем использовать объект класса Country , как ключ, и название столицы этой страны, как значение. Ниже приведен пример, который поможет нам понять, как пара ключ-значение будет храниться в хэш-карте.

1. Country.java

 package org.arpit.javapostsforlearning; public class Country < String name; long population; public Country(String name, long population) < super(); this.name = name; this.population = population; >public String getName() < return name; >public void setName(String name) < this.name = name; >public long getPopulation() < return population; >public void setPopulation(long population) < this.population = population; >// если длина имени в объекте Country - четное число, // то возвращаем 31(любое случайное число), а если нечетное - 95 (любое случайное число). // указанный ниже метод - это не самый лучший способ генерации хеш-кода, // но мы воспользуемся им для более четкого понимания хеш-карт. @Override public int hashCode() < if(this.name.length()%2==0) return 31; else return 95; >@Override public boolean equals(Object obj) < Country other = (Country) obj; if (name.equalsIgnoreCase((other.name))) return true; return false; >> 

Если хотите понять и узнать больше о методах hashcode и equals, можете пройти по этой ссылке.

2. HashMapStructure.java(main class)

 import java.util.HashMap; import java.util.Iterator; public class HashMapStructure < /** * @author Arpit Mandliya */ public static void main(String[] args) < Country india=new Country("India",1000); Country japan=new Country("Japan",10000); Country france=new Country("France",2000); Country russia=new Country("Russia",20000); HashMapcountryCapitalMap=new HashMap(); countryCapitalMap.put(india,"Delhi"); countryCapitalMap.put(japan,"Tokyo"); countryCapitalMap.put(france,"Paris"); countryCapitalMap.put(russia,"Moscow"); Iterator countryCapitalIter=countryCapitalMap.keySet().iterator();//установите //debug-точку на этой строке(23) while(countryCapitalIter.hasNext()) < Country countryObj=countryCapitalIter.next(); String capital=countryCapitalMap.get(countryObj); System.out.println(countryObj.getName()+"----"+capital); >> > 

Теперь установите брейкпоинт на строку 23 и запустите run -> debug as-> java application (прим. переводчика — действительно для Eclipse). Программа остановит выполнение на строке 23, после этого кликните правой кнопкой на countryCapitalMap и выберете watch. Вы увидите вот такую таблицу: Здесь мы видим следующее:

1. Есть массив Entry[] из 16 ячеек с именем table ;
2. В этом массиве хранятся объекты класса Entry . У класса HashMap есть внутренний класс — Entry . И экземплярами этого класса являются пары ключ-значение. Давайте взглянем на структуру класса Entry :

 static class Entry implements Map.Entry < final K key; V value; Entry next; final int hash; . //продолжение кода >

 Hashcode for Japan = 95 так как длина слова Japan имеет нечетное количество букв. Hashcode for India = 95 так как длина слова India имеет нечетное количество букв. HashCode for Russia = 31 так как длина слова Russia имеет четное количество букв. HashCode for France = 31 так как длина слова France имеет четное количество букв. 

Следующий рисунок объяснит идею связного списка: Теперь, когда у вас уже есть понимание о структуре хэш-карт, давайте перейдем к методам put и get .

Put:

Давайте посмотрим, как используется этот метод:

 /** * Метод связывает указанное значение с указанным ключом в данной хэш-карте. Если * карта до этого уже содержала некоторое значение, соответствующее этому ключу, * то старое значение заменяется на указанное. * @param key * ключ, с которым связывается указанное значение * @param value * значение, связываемое с указанным ключом * @возвращает значение связанное с ключом, или null, * если никакое значение не соответствует ключу. ( Возврат null * может так же говорить о том, что в карте заведомо null был связан с * ключом.) */ public V put(K key, V value) < if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entrye = table[i]; e != null; e = e.next) < Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) < V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; >> modCount++; addEntry(hash, key, value, i); return null; > 

1. Проверяем объект key на равенство null . Если так и есть, то объект key будет сохранен в ячейке table[0] , потому что хэш-код для null всегда равен 0;
2. Далее у объекта key вызываем метод hashcode() , который высчитает его хэш-код. Этот хэш-код используется для определения ячейки массива, где будет храниться объект класса Entry . Иногда бывает так, что эта функция hashcode написана не слишком умело, потому разработчики JDK создали другу функцию — hash() , которая в качестве аргумента принимает до этого высчитанный хэш-код. Если интересно почитать про эту функцию более подробно, можете пройти по ссылке;
3. indexFor(hash,table.length) используется для определения конкретной ячейку в массиве table , в которую будет определен для хранения объект класса Entry ;
4. Как мы видели в нашем примере, если два объекта key имеют одинаковый хэш-код (эта ситуации известна, как коллизия), то они будут сохранены в форме связного списка. Поэтому на данном этапе мы проводим итерацию нашего списка:
   • если только что рассчитанная ячейка пуста, то объект класса Entry будет сохранен непосредственно в эту ячейку;
   • если в этой ячейке уже содержится какой-либо объект, тогда происходит итерация до элемента, у которого поле next равно null . После этого наш объект класса Entry становится следующим в списке;
   • что, если мы добавим такой же объект key еще раз? По логике он должен заменить старое значение. Да, так и будет. Во время итерации будет производиться сравнение ключей с помощью метода equals() ( key.equals(k) ). Если результатом будет истина, то старое значение будет заменено на значение текущего объекта Entry .

Get:

Теперь давайте взглянем на применение метода get

 /** * Возвращает значение, которое соответствует указанному ключу, или , если * данная карта не содержит пары с указанным ключом. * * * 
* Более точно, если в данной карте содержится такой ключ * с соответствующим ему значением , что , * то метод возвращает ; в противном случае возвращается . * (может быть не более одной такой пары) * *
 
* Возвращенное значение не обязательно говорит о том, что * в карте нет пары с таким указанным ключом; а возможно, что в карте однозначно * указано соответствие этого ключа со значением . * Можно воспользоваться операцией , чтобы * отличить эти два случая * @see #put(Object, Object) */ public V get(Object key) < if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entrye = table[indexFor(hash, table.length)]; e != null; e = e.next) < Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; >return null; > 

1. Объект Ekey проверяется на равенство null . Если так и есть, то будет возвращено значение объекта, хранящегося в ячейке table[0] ;
2. У объекта key вызывается метод hashcode() , который высчитывает хэш-код;
3. indexFor(hash,table.length) используется для определения конкретной ячейки массива table , из которой необходимо взять объект класса Entry ;
4. После получения номера ячейки массива table будет произведена итерация по списку и сравнение ключей с помощью метода equals() . Если результатом будет истина, то будет возвращено значение объекта Entry , в противном случае — null .

Что следует запомнить:

• Класс HashMap имеет внутренний класс Entry , который хранит пары ключ-значение;
• Объекты класса Entry хранятся в массиве Entry[ ] под названием table ;
• Ячейка массива называется корзиной и хранит первый элемент из связного списка;
• Метод hashcode() объекта key используется для поиска корзины этого объекта класса Entry ;
• Если ключи двух объектов имеют одинаковый хэш-код, они будут сохранены в одной корзине массива table ;
• Метод equals() объекта key используется для подтверждения его уникальности;
• Методы equals() и hashcode() объекта value вообще не используются.