Хэш-карта Java Под капотом

Автор оригинала: baeldung.

1. Обзор

В этой статье мы рассмотрим наиболее популярную реализацию интерфейса Map из фреймворка Java Collections более подробно, продолжая с того места, на котором остановилась наша статья intro .

Прежде чем мы приступим к реализации, важно отметить, что основные интерфейсы List и Set collection расширяют Collection , но Map не расширяют.

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

Пары ключ-значение хранятся в так называемых корзинах, которые вместе составляют так называемую таблицу, которая на самом деле является внутренним массивом.

Как только мы узнаем ключ, под которым хранится или должен храниться объект, операции хранения и извлечения происходят в постоянное время , O(1) в хорошо размерной хэш-карте.

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

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

2. API put()

Чтобы сохранить значение в хэш-карте, мы вызываем API put , который принимает два параметра: ключ и соответствующее значение:

V put(K key, V value);

Когда значение добавляется на карту под ключом, вызывается hashCode() API ключевого объекта, чтобы получить то, что известно как начальное значение хэша.

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

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 map = new HashMap<>();
    map.put(key, "val");
}

В приведенном выше коде ничего особенного не происходит, но обратите внимание на вывод консоли. Действительно, вызывается метод hashCode :

Calling hashCode()

Затем hash() API hashmap вызывается внутренне, чтобы вычислить конечное значение хэша, используя начальное значение хэша.

Это конечное значение хэша в конечном итоге сводится к индексу во внутреннем массиве или к тому, что мы называем местоположением корзины.

Функция 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 и в качестве первого параметра задается конечное значение хэша.

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

Причина в том, что hashmaps хранит как ключ, так и значение в местоположении корзины в виде Map.Entry object .

Как обсуждалось ранее, все интерфейсы платформы Java collections расширяют Collection interface, но Map этого не делает. Сравните объявление интерфейса карты, которое мы видели ранее, с объявлением интерфейса Set :

public interface Set extends Collection

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

Таким образом, общие методы интерфейса Collection , такие как add , toArray , не имеют смысла, когда речь заходит о Map .

Концепция, которую мы рассмотрели в последних трех абзацах, является одним из самых популярных вопросов для интервью с Java Collections Framework . Так что это стоит понять.

Один специальный атрибут с хэш-картой заключается в том, что он принимает null значения и ключи null:

@Test
public void givenNullKeyAndVal_whenAccepts_thenCorrect(){
    Map map = new HashMap<>();
    map.put(null, null);
}

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

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

Во время операции put , когда мы используем ключ, который уже использовался ранее для хранения значения, он возвращает предыдущее значение, связанное с ключом:

@Test
public void givenExistingKey_whenPutReturnsPrevValue_thenCorrect() {
    Map map = new HashMap<>();
    map.put("key1", "val1");

    String rtnVal = map.put("key1", "val2");

    assertEquals("val1", rtnVal);
}

в противном случае он возвращает null:

@Test
public void givenNewKey_whenPutReturnsNull_thenCorrect() {
    Map map = new HashMap<>();

    String rtnVal = map.put("key1", "val1");

    assertNull(rtnVal);
}

Когда put возвращает null, это также может означать, что предыдущее значение, связанное с ключом, равно null, не обязательно, что это новое сопоставление ключ-значение:

@Test
public void givenNullVal_whenPutReturnsNull_thenCorrect() {
    Map map = new HashMap<>();

    String rtnVal = map.put("key1", null);

    assertNull(rtnVal);
}

API containsKey можно использовать для различения таких сценариев, как мы увидим в следующем подразделе.

3. API get

Чтобы получить объект, уже сохраненный в хэш-карте, мы должны знать ключ, под которым он был сохранен. Мы вызываем get API и передаем ему ключевой объект:

@Test
public void whenGetWorks_thenCorrect() {
    Map map = new HashMap<>();
    map.put("key", "val");

    String val = map.get("key");

    assertEquals("val", val);
}

Внутри используется тот же принцип хеширования. Хэш-код() API ключевого объекта вызывается для получения начального значения хэша:

@Test
public void whenHashCodeIsCalledOnGet_thenCorrect() {
    MyKey key = new MyKey(1);
    Map map = new HashMap<>();
    map.put(key, "val");
    map.get(key);
}

На этот раз Хэш-код API Мой ключ вызывается дважды; один раз для put и один раз вы получаете :

Calling hashCode()
Calling hashCode()

Это значение затем повторно хэшируется путем вызова внутреннего hash() API для получения конечного значения хэша.

Как мы видели в предыдущем разделе, это конечное значение хэша в конечном итоге сводится к местоположению корзины или индексу внутреннего массива.

Объект value, хранящийся в этом расположении, затем извлекается и возвращается вызывающей функции.

Когда возвращаемое значение равно null, это может означать, что ключевой объект не связан ни с каким значением в хэш-карте:

@Test
public void givenUnmappedKey_whenGetReturnsNull_thenCorrect() {
    Map map = new HashMap<>();

    String rtnVal = map.get("key1");

    assertNull(rtnVal);
}

Или это может просто означать, что ключ был явно сопоставлен с нулевым экземпляром:

@Test
public void givenNullVal_whenRetrieves_thenCorrect() {
    Map map = new HashMap<>();
    map.put("key", null);
        
    String val=map.get("key");
        
    assertNull(val);
}

Чтобы различать эти два сценария, мы можем использовать containsKey API, которому мы передаем ключ, и он возвращает true тогда и только тогда, когда для указанного ключа в хэш-карте было создано сопоставление:

@Test
public void whenContainsDistinguishesNullValues_thenCorrect() {
    Map 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);
}

В обоих случаях в приведенном выше тесте возвращаемое значение вызова get API равно null, но мы можем различить, какой из них какой.

4. Представления коллекции в HashMap

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

@Test
public void givenHashMap_whenRetrievesKeyset_thenCorrect() {
    Map map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set keys = map.keySet();

    assertEquals(2, keys.size());
    assertTrue(keys.contains("name"));
    assertTrue(keys.contains("type"));
}

Набор поддерживается самой картой. Таким образом любое изменение, внесенное в набор, отражается на карте :

@Test
public void givenKeySet_whenChangeReflectsInMap_thenCorrect() {
    Map map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    assertEquals(2, map.size());

    Set keys = map.keySet();
    keys.remove("name");

    assertEquals(1, map.size());
}

Мы также можем получить представление коллекции значений :

@Test
public void givenHashMap_whenRetrievesValues_thenCorrect() {
    Map map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Collection values = map.values();

    assertEquals(2, values.size());
    assertTrue(values.contains("baeldung"));
    assertTrue(values.contains("blog"));
}

Как и набор ключей, любые изменения, внесенные в эту коллекцию, будут отражены в базовой карте .

Наконец, мы можем получить заданное представление всех записей на карте:

@Test
public void givenHashMap_whenRetrievesEntries_thenCorrect() {
    Map map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set> entries = map.entrySet();

    assertEquals(2, entries.size());
    for (Entry e : entries) {
        String key = e.getKey();
        String val = e.getValue();
        assertTrue(key.equals("name") || key.equals("type"));
        assertTrue(val.equals("baeldung") || val.equals("blog"));
    }
}

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

Много раз вы будете использовать представления коллекции в цикле, как в последнем примере, и, более конкретно, использовать их итераторы.

Просто помните, что итераторы для всех вышеперечисленных представлений являются fail-fast .

Если на карте будет произведена какая-либо структурная модификация, то после создания итератора будет выдано исключение параллельной модификации:

@Test(expected = ConcurrentModificationException.class)
public void givenIterator_whenFailsFastOnModification_thenCorrect() {
    Map map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set keys = map.keySet();
    Iterator it = keys.iterator();
    map.remove("type");
    while (it.hasNext()) {
        String key = it.next();
    }
}

Единственная разрешенная структурная модификация-это операция remove , выполняемая через сам итератор:

public void givenIterator_whenRemoveWorks_thenCorrect() {
    Map map = new HashMap<>();
    map.put("name", "baeldung");
    map.put("type", "blog");

    Set keys = map.keySet();
    Iterator it = keys.iterator();

    while (it.hasNext()) {
        it.next();
        it.remove();
    }

    assertEquals(0, map.size());
}

Последнее, что следует помнить об этих представлениях коллекций, – это производительность итераций. Именно здесь хэш-карта работает довольно плохо по сравнению с ее аналогами linkedhashmap и treemap.

Итерация по хэш-карте происходит в худшем случае O(n) , где n-сумма ее емкости и количества записей.

5. Производительность хэш-карты

На производительность хэш-карты влияют два параметра: Начальная емкость и Коэффициент загрузки . Емкость-это количество сегментов или длина базового массива, а начальная емкость-это просто емкость во время создания.

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

Начальная емкость по умолчанию 16 и коэффициент нагрузки по умолчанию равен 0.75 . Мы можем создать хэш-карту с пользовательскими значениями для начальной емкости и LF:

Map hashMapWithCapacity=new HashMap<>(32);
Map hashMapWithCapacityAndLF=new HashMap<>(32, 0.5f);

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

Когда количество записей хэш-карты превышает произведение LF и емкости, происходит перефразирование , т. е. создается еще один внутренний массив с вдвое большим размером исходного, и все записи перемещаются в новые ячейки в новом массиве .

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

С другой стороны, если вы установите слишком высокую начальную емкость, вы заплатите стоимость за время итерации. Как мы видели в предыдущем разделе.

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

A низкая начальная емкость хороша для нескольких записей с большим количеством итераций .

6. Коллизии в хэш-карте

Столкновение, или, более конкретно , столкновение хэш-кода в 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 в качестве хэш – кода-и, таким образом, вызываем столкновение.

Кроме того, обратите внимание, что мы добавили операторы log в наши реализации equals и hashCode , чтобы точно знать, когда вызывается логика.

Давайте теперь перейдем к хранению и извлечению некоторых объектов, которые сталкиваются в какой-то момент:

@Test
public void whenCallsEqualsOnCollision_thenCorrect() {
    HashMap 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 , а два других имеют одинаковый id . Поскольку мы используем 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 .