«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);
}Когда нулевой ключ встречается во время операции размещения, ему автоматически присваивается конечное хэш-значение 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);
}При размещении возвращает 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. Get 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; один раз для ввода и один раз для получения:
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);
}Чтобы различать два сценария, мы можем использовать API containsKey, которому мы передаем ключ, и он возвращает 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", "baeldung");
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", "baeldung");
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", "baeldung");
map.put("type", "blog");
Collection<String> values = map.values();
assertEquals(2, values.size());
assertTrue(values.contains("baeldung"));
assertTrue(values.contains("blog"));
}Как и в случае с набором ключей, любые изменения, сделанные в этой коллекции, будут отражается на базовой карте.
Наконец, мы можем получить заданное представление всех записей в карте:
@Test
public void givenHashMap_whenRetrievesEntries_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("name", "baeldung");
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("baeldung") || val.equals("blog"));
}
}Помните, что хеш-карта специально содержит неупорядоченные элементы, поэтому мы предполагаем любой порядок при тестировании ключей и значений записей в for каждую петлю.
Много раз вы будете использовать представления коллекций в цикле, как в последнем примере, а точнее, используя их итераторы.
Просто помните, что итераторы для всех вышеперечисленных представлений работают безотказно.
Если на карте будет произведена какая-либо структурная модификация, после создания итератора будет выдано исключение параллельной модификации:
@Test(expected = ConcurrentModificationException.class)
public void givenIterator_whenFailsFastOnModification_thenCorrect() {
Map<String, String> map = new HashMap<>();
map.put("name", "baeldung");
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", "baeldung");
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. Производительность хэш-карты
На производительность хэш-карты влияют два параметра: начальная емкость и коэффициент загрузки. Емкость — это количество сегментов или длина базового массива, а начальная емкость — это просто емкость во время создания.
Фактор загрузки или 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.