Статьи

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

Апрель 13, 2019

Наиболее распространенные вопросы интервью: «Как HashMap работает в Java», «Как метод get и put HashMap работает внутри». Здесь я пытаюсь объяснить внутреннюю функциональность простым примером. Вместо того, чтобы изучать теорию, мы сначала начнем с примера, чтобы вы лучше поняли, а затем посмотрим, как функции get и put работают в Java.
Давайте возьмем очень простой пример. У меня есть класс Country, мы собираемся использовать объект класса Country в качестве ключа и его заглавное имя (строка) в качестве значения. Приведенный ниже пример поможет вам понять, как эти пары ключ-значение будут храниться в hashmap.

1. Country.java

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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;
 }
 
 // If length of name in country object is even then return 31(any random number) and if odd then return 95(any random number).
 // This is not a good practice to generate hashcode as below method but I am doing so to give better and easy understanding of hashmap.
 @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 объекта, вы можете обратиться к методам hashcode () и equals () в java

2. HashMapStructure.java (основной класс)

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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();//put debug point at this line
        while(countryCapitalIter.hasNext())
        {
            Country countryObj=countryCapitalIter.next();
            String capital=countryCapitalMap.get(countryObj);
            System.out.println(countryObj.getName()+"----"+capital);
            }
        }
   
   
}
</country></country,string></country,string>

Теперь поместите точку отладки в строку 23 и щелкните правой кнопкой мыши проект-> отладка as-> java-приложения. Программа остановит выполнение в строке 23, затем щелкните правой кнопкой мыши на countryCapitalMap, затем выберите часы. Вы сможете увидеть структуру, как показано ниже.

HashMapStructure1
Теперь из приведенной выше диаграммы вы можете наблюдать следующие пункты

  1. Существует массив Entry [] с именем table, который имеет размер 16.
  2. В этой таблице хранится объект класса Entry. Класс HashMap имеет внутренний класс с именем Entry. Эта запись имеет ключевое значение в качестве переменной экземпляра. Давайте посмотрим структуру класса входа Entry Structure.
    3. 1
    2
    3
    4
    5
    6
    7
    8
    static class Entry implements Map.Entry
    {
            final K key;
            V value;
            Entry next;
            final int hash;
            ...//More code goes here
    }
  3. Всякий раз, когда мы пытаемся поместить любую пару значений ключа в hashmap, объект класса Entry создается для значения ключа, и этот объект будет храниться в вышеупомянутой Entry [] (таблица). Теперь вам должно быть интересно, где будет храниться созданный выше объект Enrty (точное положение в таблице). Ответ таков: хеш-код рассчитывается для ключа с помощью метода Hascode (). Этот хеш-код используется для расчета индекса для указанной выше таблицы Entry [].
  4. Теперь, если вы видите индекс массива 10 на приведенной выше диаграмме, у него есть объект Entry с именем HashMap $ Entry.
  5. Мы поместили 4 значения ключа в hashmap, но, похоже, их всего 2 !!!! Это потому, что если два объекта имеют одинаковый хеш-код, они будут храниться с одинаковым индексом. Теперь возникает вопрос, как? Он хранит объекты в форме LinkedList (логически).

Итак, как вычисляется хэш-код вышеуказанных пар ключ-значение страны.

1
2
3
4
Hashcode for Japan = 95 as its length is odd.
Hashcode for India =95 as its length is odd
HashCode for Russia=31 as its length is even.
HashCode for France=31 as its length is even.

Ниже на диаграмме будет четко объяснена концепция LinkedList.

HashMapStructure2
Так что теперь, если у вас есть хорошее понимание структуры hashmap, давайте рассмотрим метод put и get.

Положить :

Посмотрим реализацию метода put:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
  * Associates the specified value with the specified key in this map. If the
  * map previously contained a mapping for the key, the old value is
  * replaced.
  *
  * @param key
  *            key with which the specified value is to be associated
  * @param value
  *            value to be associated with the specified key
  * @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
  *         if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
  *         can also indicate that the map previously associated
  *         <tt>null</tt> with <tt>key</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. Ключевой объект проверяется на ноль. Если ключ равен нулю, он будет сохранен в таблице [0], потому что хеш-код для нуля всегда равен 0.
  2. Вызывается метод hashcode () ключевого объекта и вычисляется хеш-код. Этот хеш-код используется для поиска индекса массива для хранения объекта Entry. Иногда может случиться так, что эта функция хеширования написана плохо, поэтому разработчик JDK поместил другую функцию с именем hash (), которая принимает выше вычисленное значение хеша в качестве аргумента. Если вы хотите узнать больше о функции hash (), вы можете ссылаться на hash и indexFor метод в hashmap .
  3. indexFor (hash, table.length) используется для вычисления точного индекса в массиве таблиц для хранения объекта Entry.
  4. Как мы видели в нашем примере, если два ключевых объекта имеют одинаковый хеш-код (который называется коллизией ), то он будет сохранен в виде связного списка. Здесь мы будем перебирать наш связанный список.
  • Если в этом индексе нет элемента, который мы только что вычислили, он непосредственно поместит наш объект Entry в этот индекс.
  • Если в этом индексе присутствует элемент, то он будет повторяться до тех пор, пока не получит Entry-> next как null. Затем текущий объект Entry станет следующим узлом в этом списке ссылок
  • Что если мы снова введем тот же ключ, логически он должен заменить старое значение. Да, он будет делать это. Во время итерации он будет проверять равенство ключей, вызывая метод equals () ( key.equals (k) ), если этот метод возвращает true, тогда он заменяет объект-значение на объект-значение текущей записи.

Получить:

Давайте посмотрим реализацию get сейчас:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
  * Returns the value to which the specified key is mapped, or {@code null}
  * if this map contains no mapping for the key.
  *
  * <p>
  * More formally, if this map contains a mapping from a key {@code k} to a
  * value {@code v} such that {@code (key==null ? k==null :
  * key.equals(k))}, then this method returns {@code v}; otherwise it returns
  * {@code null}. (There can be at most one such mapping.)
  *
  * </p><p>
  * A return value of {@code null} does not <i>necessarily</i> indicate that
  * the map contains no mapping for the key; it's also possible that the map
  * explicitly maps the key to {@code null}. The {@link #containsKey
  * containsKey} operation may be used to distinguish these two cases.
  *
  * @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;
 }

Как вы получили представление о поставленной функциональности hashmap. Так что понять функциональность получить довольно просто. Если вы передадите любой ключ, чтобы получить значение объекта из hashmap.

  1. Ключевой объект проверяется на ноль. Если ключ равен нулю, то значение Object находится в таблице [0] будет возвращено.
  2. Вызывается метод hashcode () ключевого объекта и вычисляется хеш-код.
  3. indexFor (hash, table.length) используется для вычисления точного индекса в массиве таблиц с использованием сгенерированного хеш-кода для получения объекта Entry.
  4. После получения индекса в массиве таблицы он будет перебирать связанный список и проверять равенство ключей, вызывая метод equals (), и если он возвращает значение true, он возвращает значение объекта Entry, иначе возвращается значение NULL.

Ключевые моменты для Remeber:

  • HashMap имеет внутренний класс Entry, который хранит пары ключ-значение.
  • Над объектом Entry хранится в Entry [] (Array) с именем table
  • Индекс таблицы логически известен как bucket, и в нем хранится первый элемент связного списка.
  • Хэш-код ключевого объекта () используется для поиска сегмента этого объекта Entry.
  • Если два ключевых объекта имеют одинаковый хеш-код, они будут помещены в один и тот же сегмент массива таблицы.
  • Метод equals () ключевого объекта используется для обеспечения уникальности ключевого объекта.
  • Метод equals () объекта значения и метод hashcode () вообще не используются

74
Share: