User gnev
gnev
24 уровень

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

Статья из группы Архив info.javarush.ru
Как HashMap работает в Java? - 1Очень часто на собеседованиях задают вопросы такого рода, как “Как работает 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);
          
        HashMap<country,string> countryCapitalMap=new HashMap<country,string>();
        countryCapitalMap.put(india,"Delhi");
        countryCapitalMap.put(japan,"Tokyo");
        countryCapitalMap.put(france,"Paris");
        countryCapitalMap.put(russia,"Moscow");
          
        Iterator<country> 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. Вы увидите вот такую таблицу: Как HashMap работает в Java? - 2Здесь мы видим следующее:
  1. Есть массив Entry[] из 16 ячеек с именем table;

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

  3. 
    static class Entry implements Map.Entry
            {
                    final K key;
                    V value;
                    Entry next;
                    final int hash;
                    ...//продолжение кода
            }
    
  4. Каждый раз когда мы пытаемся создать пару ключ-значение в хэш-карте, для этой пары создается объект класса Entry, и он будет храниться в указанной выше таблице Entry[]. А теперь вам должно быть интересно, куда именно в этой таблице будет записан этот объект (в какую ячейку). Для ключа из пары ключ-значение высчитывается хэш-код с помощью метода hashcode(). И этот хэш-код используется для вычисления номера ячейки таблицы Entry[];

  5. Теперь, если вы взгляните на ячейку 10 таблицы, вы увидите объект класса Entry с именем HashMap$Entry;

  6. Мы добавили 4 пары ключ-значение, но в массиве только 2!!! Это потому что, если 2 объекта имеют одинаковый хэш-код, то они будут храниться в одной ячейке. Но как? Объекты будут храниться в виде связного списка (LinkedList).
Вот как будет вычислен хеш-код для наших пар ключ-значение.

Hashcode for Japan = 95 так как длина слова Japan имеет нечетное количество букв.
Hashcode for India = 95 так как длина слова India имеет нечетное количество букв.
HashCode for Russia = 31 так как длина слова Russia имеет четное количество букв.
HashCode for France = 31 так как длина слова France имеет четное количество букв.
Следующий рисунок объяснит идею связного списка: Как HashMap работает в Java? - 3Теперь, когда у вас уже есть понимание о структуре хэш-карт, давайте перейдем к методам put и get.

Put:

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

/**
  * Метод связывает указанное значение с указанным ключом в данной хэш-карте. Если
  * карта до этого уже содержала некоторое значение, соответствующее этому ключу, 
  * то старое значение заменяется на указанное.
  * @param key
  *            ключ, с которым связывается указанное значение
  * @param value
  *            значение, связываемое с указанным ключом
  * @возвращает значение связанное с <tt>ключом</tt>, или <tt>null</tt>,
  *         если никакое значение не соответствует <tt>ключу</tt>. ( Возврат <tt>null</tt>
  *         может так же говорить о том, что в карте заведомо <tt>null</tt> был связан с
  *         <tt>ключом</tt>.)
  */
 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 (Entry<k , V> e = 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

/**
  * Возвращает значение, которое соответствует указанному ключу, или {@code null}, если              
  * данная карта не содержит пары с указанным ключом.
  *
  *
  * <p>
  * Более точно, если в данной карте содержится такой ключ {@code k} 
  * с соответствующим ему значением {@code v}, что {@code (key==null ? k==null : key.equals(k))},
  * то метод возвращает {@code v}; в противном случае возвращается {@code null}. 
  * (может быть не более одной такой пары)
  *
  * </p><p>
  * Возвращенное значение {@code null} не <i>обязательно</i> говорит о том, что
  * в карте нет пары с таким указанным ключом; а возможно, что в карте однозначно
  * указано соответствие этого ключа со значением {@code null}.
  * Можно воспользоваться операцией {@link #containsKey containsKey}, чтобы
  * отличить эти два случая
  * @see #put(Object, Object)
  */
 public V get(Object key) {
  if (key == null)
   return getForNullKey();
  int hash = hash(key.hashCode());
  for (Entry<k , V> e = 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;
 }
Теперь, когда у вас есть понимание работы метода put в хэш-картах, понять, как работает метод get, очень просто. Когда вы передаете методу какой-либо ключ, чтобы получить значение из хеш-карты:
  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 вообще не используются.

Источник
Комментарии (6)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Dim Уровень 14, Дубна, Russian Federation
7 мая 2022
У меня у одного не компилируется?
Oleksii Уровень 36, Харьков
3 июня 2021
bucket - ведро,бадья, не корзина. Спасибо за статью: полезно, познавательно.
18 мая 2020
Коллизия в данном случае это ни когда хешкоды ключей одинаковые, а когда позиции корзины, вычисленные в том числе по хеш-коду, совпадают.
Dex Уровень 17, Россия
2 мая 2014
А нельзя вот это:

if (name.equalsIgnoreCase((other.name)))
   return true;
  return false;
заменить на это:

return name.equalsIgnoreCase(other.name)
?