1. Обзор
В этой статье мы собираемся более подробно изучить самую популярную реализацию интерфейса Map из Java Collections Framework, продолжая с того места, на котором остановилась наша вступительная статья.
Прежде чем мы приступим к реализации, важно отметить, что основные интерфейсы коллекций List и Set расширяют Collection , а Map — нет.
Проще говоря, HashMap хранит значения по ключу и предоставляет API для добавления, извлечения и обработки сохраненных данных различными способами. Реализация основана на принципах хеш-таблицы , которые на первый взгляд кажутся сложными, но на самом деле их очень легко понять.
Пары ключ-значение хранятся в так называемых корзинах, которые вместе составляют то, что называется таблицей, которая на самом деле является внутренним массивом.
Как только мы узнаем ключ, под которым хранится или должен храниться объект, операции хранения и извлечения выполняются за постоянное время , O(1) в хеш-карте с хорошими размерами.
Чтобы понять, как хеш-карты работают внутри, нужно понять механизм хранения и поиска, используемый HashMap. Мы сосредоточимся на них.
Наконец, вопросы, связанные с HashMap , довольно часто встречаются на собеседованиях , так что это хороший способ либо подготовиться к интервью, либо подготовиться к нему.
2. API put()
Чтобы сохранить значение в хэш-карте, мы вызываем API-интерфейс put , который принимает два параметра; ключ и соответствующее значение:
V put(K key, V value);
Когда значение добавляется к карте под ключом, вызывается API-интерфейс hashCode() объекта ключа для получения так называемого начального хеш-значения.
Чтобы увидеть это в действии, давайте создадим объект, который будет действовать как ключ. Мы создадим только один атрибут для использования в качестве хэш-кода для имитации первой фазы хеширования:
public class MyKey {
private int id;
@Override
public int hashCode() {
System.out.println("Calling hashCode()");
return id;
}
// constructor, setters and getters
}
Теперь мы можем использовать этот объект для отображения значения в хэш-карте:
@Test
public void whenHashCodeIsCalledOnPut_thenCorrect() {
MyKey key = new MyKey(1);
Map<MyKey, String> map = new HashMap<>();
map.put(key, "val");
}
В приведенном выше коде ничего особенного не происходит, но обратите внимание на вывод консоли. Действительно вызывается метод hashCode :
Calling hashCode()
Далее вызывается внутренний API hash() карты хэшей для вычисления конечного значения хеш-функции с использованием начального значения хэш-функции.
Это окончательное хеш-значение в конечном итоге сводится к индексу во внутреннем массиве или к тому, что мы называем местоположением корзины.
Хэш- функция HashMap выглядит так:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Здесь следует отметить только использование хеш-кода из ключевого объекта для вычисления окончательного хеш-значения.
Находясь внутри функции put , конечное значение хеш-функции используется следующим образом:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
Обратите внимание, что вызывается внутренняя функция putVal , которой в качестве первого параметра передается окончательное значение хеш-функции.
Можно задаться вопросом, почему ключ снова используется внутри этой функции, ведь мы уже использовали его для вычисления хеш-значения.
Причина в том, что хеш-карты хранят как ключ, так и значение в расположении корзины как объект Map.Entry .
Как обсуждалось ранее, все интерфейсы фреймворка коллекций Java расширяют интерфейс Collection , а Map — нет. Сравните объявление интерфейса Map, которое мы видели ранее, с объявлением интерфейса Set :
public interface Set<E> extends Collection<E>
Причина в том, что карты хранят не отдельные элементы, как другие коллекции, а набор пар ключ-значение.
Таким образом, общие методы интерфейса Collection , такие как add , toArray , не имеют смысла, когда дело доходит до Map .
Концепция, которую мы рассмотрели в последних трех абзацах, является одним из самых популярных вопросов на собеседовании по Java Collections Framework . Итак, стоит понять.
Одним из специальных атрибутов хэш-карты является то, что она принимает нулевые значения и нулевые ключи:
@Test
public void givenNullKeyAndVal_whenAccepts_thenCorrect(){
Map<String, String> map = new HashMap<>();
map.put(null, null);
}
Когда во время операции put встречается нулевой ключ , ему автоматически присваивается конечное хэш-значение 0 , что означает, что он становится первым элементом базового массива.
Это также означает, что когда ключ имеет значение null, операции хеширования не выполняется, и, следовательно, API-интерфейс hashCode ключа не вызывается, что в конечном итоге позволяет избежать исключения нулевого указателя.
Во время операции размещения , когда мы используем ключ, который уже использовался ранее для хранения значения, он возвращает предыдущее значение, связанное с ключом:
@Test
public void givenExistingKey_whenPutReturnsPrevValue_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("key1", "val1");
String rtnVal = map.put("key1", "val2");
assertEquals("val1", rtnVal);
}
в противном случае возвращается ноль:
@Test
public void givenNewKey_whenPutReturnsNull_thenCorrect() {
Map<String, String> map = new HashMap<>();
String rtnVal = map.put("key1", "val1");
assertNull(rtnVal);
}
Когда put возвращает null, это также может означать, что предыдущее значение, связанное с ключом, равно null, не обязательно, что это новое сопоставление ключ-значение:
@Test
public void givenNullVal_whenPutReturnsNull_thenCorrect() {
Map<String, String> map = new HashMap<>();
String rtnVal = map.put("key1", null);
assertNull(rtnVal);
}
API containsKey можно использовать для различения таких сценариев, как мы увидим в следующем подразделе.
3. Получить API
Чтобы получить объект, уже сохраненный в хэш-карте, мы должны знать ключ, под которым он был сохранен. Вызываем get API и передаем ему ключевой объект:
@Test
public void whenGetWorks_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("key", "val");
String val = map.get("key");
assertEquals("val", val);
}
Внутри используется тот же принцип хеширования. API hashCode() ключевого объекта вызывается для получения начального хеш-значения:
@Test
public void whenHashCodeIsCalledOnGet_thenCorrect() {
MyKey key = new MyKey(1);
Map<MyKey, String> map = new HashMap<>();
map.put(key, "val");
map.get(key);
}
На этот раз API hashCode MyKey вызывается дважды; один раз для put и один раз для get :
Calling hashCode()
Calling hashCode()
Затем это значение повторно хэшируется путем вызова внутреннего API-интерфейса hash() для получения окончательного хеш-значения.
Как мы видели в предыдущем разделе, это окончательное хеш-значение в конечном итоге сводится к местоположению корзины или индексу внутреннего массива.
Затем объект значения, хранящийся в этом месте, извлекается и возвращается в вызывающую функцию.
Когда возвращаемое значение равно null, это может означать, что ключевой объект не связан ни с каким значением в хэш-карте:
@Test
public void givenUnmappedKey_whenGetReturnsNull_thenCorrect() {
Map<String, String> map = new HashMap<>();
String rtnVal = map.get("key1");
assertNull(rtnVal);
}
Или это может просто означать, что ключ был явно сопоставлен с нулевым экземпляром:
@Test
public void givenNullVal_whenRetrieves_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("key", null);
String val=map.get("key");
assertNull(val);
}
Чтобы различать эти два сценария, мы можем использовать containsKey API, которому мы передаем ключ, и он возвращает true тогда и только тогда, когда для указанного ключа в хэш-карте было создано сопоставление:
@Test
public void whenContainsDistinguishesNullValues_thenCorrect() {
Map<String, String> map = new HashMap<>();
String val1 = map.get("key");
boolean valPresent = map.containsKey("key");
assertNull(val1);
assertFalse(valPresent);
map.put("key", null);
String val = map.get("key");
valPresent = map.containsKey("key");
assertNull(val);
assertTrue(valPresent);
}
В обоих случаях в приведенном выше тесте возвращаемое значение вызова API get равно null, но мы можем различить, какой из них есть какой.
4. Представления коллекций в HashMap
HashMap предлагает три представления, которые позволяют нам рассматривать его ключи и значения как другую коллекцию. Мы можем получить набор всех ключей карты :
@Test
public void givenHashMap_whenRetrievesKeyset_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("name", "foreach");
map.put("type", "blog");
Set<String> keys = map.keySet();
assertEquals(2, keys.size());
assertTrue(keys.contains("name"));
assertTrue(keys.contains("type"));
}
Набор поддерживается самой картой. Таким образом , любое изменение, внесенное в набор, отражается на карте :
@Test
public void givenKeySet_whenChangeReflectsInMap_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("name", "foreach");
map.put("type", "blog");
assertEquals(2, map.size());
Set<String> keys = map.keySet();
keys.remove("name");
assertEquals(1, map.size());
}
Мы также можем получить представление коллекции значений :
@Test
public void givenHashMap_whenRetrievesValues_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("name", "foreach");
map.put("type", "blog");
Collection<String> values = map.values();
assertEquals(2, values.size());
assertTrue(values.contains("foreach"));
assertTrue(values.contains("blog"));
}
Как и в случае с набором ключей, любые изменения, внесенные в эту коллекцию, будут отражены в базовой карте .
Наконец, мы можем получить установленное представление всех записей на карте:
@Test
public void givenHashMap_whenRetrievesEntries_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("name", "foreach");
map.put("type", "blog");
Set<Entry<String, String>> entries = map.entrySet();
assertEquals(2, entries.size());
for (Entry<String, String> e : entries) {
String key = e.getKey();
String val = e.getValue();
assertTrue(key.equals("name") || key.equals("type"));
assertTrue(val.equals("foreach") || val.equals("blog"));
}
}
Помните, что хеш-карта специально содержит неупорядоченные элементы, поэтому мы предполагаем любой порядок при тестировании ключей и значений записей в цикле for each .
Много раз вы будете использовать представления коллекций в цикле, как в последнем примере, и, более конкретно, используя их итераторы.
Просто помните, что итераторы для всех вышеперечисленных представлений отказоустойчивы .
Если на карте будет произведена какая-либо структурная модификация, после создания итератора будет выдано исключение параллельной модификации:
@Test(expected = ConcurrentModificationException.class)
public void givenIterator_whenFailsFastOnModification_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("name", "foreach");
map.put("type", "blog");
Set<String> keys = map.keySet();
Iterator<String> it = keys.iterator();
map.remove("type");
while (it.hasNext()) {
String key = it.next();
}
}
Единственная допустимая структурная модификация — это операция удаления , выполняемая через сам итератор:
public void givenIterator_whenRemoveWorks_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("name", "foreach");
map.put("type", "blog");
Set<String> keys = map.keySet();
Iterator<String> it = keys.iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
assertEquals(0, map.size());
}
Последнее, что нужно помнить об этих представлениях коллекций, — это производительность итераций. Здесь хеш-карта работает довольно плохо по сравнению с ее аналогами, связанными хэш-картой и картой дерева.
Итерация по хеш-карте происходит в худшем случае O (n) , где n — сумма ее емкости и количества записей.
5. Производительность HashMap
На производительность хеш-карты влияют два параметра: Initial Capacity и Load Factor . Емкость — это количество сегментов или длина базового массива, а начальная емкость — это просто емкость во время создания.
Короче говоря, коэффициент загрузки или LF — это мера того, насколько полной должна быть хеш-карта после добавления некоторых значений перед изменением ее размера.
Начальная емкость по умолчанию равна 16 , а коэффициент загрузки по умолчанию равен 0,75 . Мы можем создать хеш-карту с пользовательскими значениями начальной емкости и LF:
Map<String,String> hashMapWithCapacity=new HashMap<>(32);
Map<String,String> hashMapWithCapacityAndLF=new HashMap<>(32, 0.5f);
Значения по умолчанию, установленные командой Java, хорошо оптимизированы для большинства случаев. Однако, если вам нужно использовать свои собственные значения, что вполне нормально, вам нужно понимать влияние на производительность, чтобы знать, что вы делаете.
Когда количество записей хеш-карты превышает произведение LF и емкости, происходит повторное хэширование, т . е . создается другой внутренний массив с удвоенным размером исходного, и все записи перемещаются в новые местоположения корзины в новом массиве .
Низкая начальная емкость снижает затраты на место, но увеличивает частоту повторного хеширования . Очевидно, что перефразирование — очень дорогой процесс. Так что, как правило, если вы ожидаете много записей, вам следует установить достаточно большую начальную емкость.
С другой стороны, если вы установите слишком высокую начальную емкость, вы заплатите за время итерации. Как мы видели в предыдущем разделе.
Таким образом , высокая начальная емкость хороша для большого количества записей в сочетании с небольшим количеством итераций или без них .
Низкая начальная емкость хороша для нескольких записей с большим количеством итераций .
6. Коллизии в HashMap
Коллизия или, точнее, коллизия хэш-кода в HashMap — это ситуация, когда два или более ключевых объекта производят одно и то же конечное хеш-значение и, следовательно, указывают на одно и то же местоположение корзины или индекс массива.
Этот сценарий может возникнуть из-за того, что в соответствии с контрактом equals и hashCode два неравных объекта в Java могут иметь одинаковый хэш-код .
Это также может произойти из-за конечного размера базового массива, то есть до изменения размера. Чем меньше этот массив, тем выше вероятность столкновения.
Тем не менее, стоит упомянуть, что в Java реализован метод разрешения коллизий хэш-кода, который мы рассмотрим на примере.
Имейте в виду, что значение хеш-функции ключа определяет корзину, в которой будет храниться объект. Таким образом, если хеш-коды любых двух ключей сталкиваются, их записи все равно будут храниться в одной и той же корзине.
И по умолчанию реализация использует связанный список в качестве реализации корзины.
Первоначально постоянное время O(1) операций put и get будет происходить за линейное время O(n) в случае столкновения. Это связано с тем, что после нахождения местоположения корзины с окончательным хэш-значением каждый из ключей в этом местоположении будет сравниваться с предоставленным ключевым объектом с использованием API equals .
Чтобы имитировать эту технику разрешения коллизий, давайте немного изменим наш предыдущий ключевой объект:
public class MyKey {
private String name;
private int id;
public MyKey(int id, String name) {
this.id = id;
this.name = name;
}
// standard getters and setters
@Override
public int hashCode() {
System.out.println("Calling hashCode()");
return id;
}
// toString override for pretty logging
@Override
public boolean equals(Object obj) {
System.out.println("Calling equals() for key: " + obj);
// generated implementation
}
}
Обратите внимание, что мы просто возвращаем атрибут id в качестве хэш-кода и, таким образом, вызываем коллизию.
Также обратите внимание, что мы добавили операторы журнала в наши реализации equals и hashCode , чтобы мы точно знали, когда вызывается логика.
Давайте теперь продолжим сохранять и извлекать некоторые объекты, которые сталкиваются в какой-то момент:
@Test
public void whenCallsEqualsOnCollision_thenCorrect() {
HashMap<MyKey, String> map = new HashMap<>();
MyKey k1 = new MyKey(1, "firstKey");
MyKey k2 = new MyKey(2, "secondKey");
MyKey k3 = new MyKey(2, "thirdKey");
System.out.println("storing value for k1");
map.put(k1, "firstValue");
System.out.println("storing value for k2");
map.put(k2, "secondValue");
System.out.println("storing value for k3");
map.put(k3, "thirdValue");
System.out.println("retrieving value for k1");
String v1 = map.get(k1);
System.out.println("retrieving value for k2");
String v2 = map.get(k2);
System.out.println("retrieving value for k3");
String v3 = map.get(k3);
assertEquals("firstValue", v1);
assertEquals("secondValue", v2);
assertEquals("thirdValue", v3);
}
В приведенном выше тесте мы создаем три разных ключа — один с уникальным идентификатором , а два других — с одинаковым идентификатором . Так как мы используем id в качестве начального хеш-значения, обязательно будет коллизия как при хранении, так и при извлечении данных с этими ключами.
В дополнение к этому, благодаря технике разрешения коллизий, которую мы видели ранее, мы ожидаем, что каждое из наших сохраненных значений будет извлечено правильно, отсюда и утверждения в последних трех строках.
Когда мы запустим тест, он должен пройти, указывая на то, что коллизии были разрешены, и мы будем использовать созданный журнал, чтобы подтвердить, что коллизии действительно произошли:
storing value for k1
Calling hashCode()
storing value for k2
Calling hashCode()
storing value for k3
Calling hashCode()
Calling equals() for key: MyKey [name=secondKey, id=2]
retrieving value for k1
Calling hashCode()
retrieving value for k2
Calling hashCode()
retrieving value for k3
Calling hashCode()
Calling equals() for key: MyKey [name=secondKey, id=2]
Обратите внимание, что во время операций хранения k1 и k2 были успешно сопоставлены со своими значениями с использованием только хэш-кода.
Однако хранение k3 было не таким простым, система обнаружила, что в его корзине уже содержится отображение для k2 . Поэтому для их различения использовалось сравнение на равенство , и был создан связанный список, содержащий оба сопоставления.
Любое другое последующее сопоставление, хэши ключей которого относятся к тому же местоположению корзины, будет следовать по тому же маршруту и в конечном итоге заменит один из узлов в связанном списке или будет добавлено в начало списка, если сравнение equals возвращает false для всех существующих узлов.
Аналогичным образом, во время поиска k3 и k2 сравнивались друг с другом для определения правильного ключа, значение которого должно быть извлечено.
И наконец, в Java 8 связанные списки динамически заменяются сбалансированными двоичными деревьями поиска в разрешении коллизий после того, как количество коллизий в заданном местоположении корзины превышает определенный порог.
Это изменение обеспечивает повышение производительности, поскольку в случае коллизии сохранение и извлечение происходят за O(log n).
Этот раздел очень распространен в технических интервью, особенно после основных вопросов о хранении и извлечении.
7. Заключение
В этой статье мы рассмотрели реализацию HashMap интерфейса Java Map .
Полный исходный код всех примеров, использованных в этой статье, можно найти в проекте GitHub .