get
и put
в HashMap?”. Тут я попытаюсь объяснить внутреннюю функциональность на простом примере. Не вдаваясь в теорию, мы начнем с примера, чтобы вы лучше поняли, а затем и увидели, How работают методы get
и put
в Java. Возьмем очень простой пример. У нас есть класс Country
(англ. “страна”), мы будем использовать an object класса Country
, How ключ, и название столицы этой страны, How meaning. Ниже приведен пример, который поможет нам понять, How пара ключ-meaning будет храниться в хэш-карте.
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;
}
// если длина имени в an objectе Country - четное число,
// то возвращаем 31(любое случайное число), а если нечетное - 95 (любое случайное число).
// указанный ниже метод - это не самый лучший способ генерации хеш-codeа,
// но мы воспользуемся им для более четкого понимания хеш-карт.
@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. Вы увидите вот такую таблицу: Здесь мы видим следующее:
-
Есть массив
Entry[]
из 16 ячеек с именемtable
; -
В этом массиве хранятся an objectы класса
Entry
. У классаHashMap
есть внутренний класс —Entry
. И экземплярами этого класса являются пары ключ-meaning. Давайте взглянем на структуру классаEntry
: -
Каждый раз когда мы пытаемся создать пару ключ-meaning в хэш-карте, для этой пары создается an object класса
Entry
, и он будет храниться в указанной выше таблицеEntry[]
. А теперь вам должно быть интересно, куда именно в этой таблице будет записан этот an object (в Howую ячейку). Для ключа из пары ключ-meaning высчитывается хэш-code с помощью методаhashcode()
. И этот хэш-code используется для вычисления номера ячейки таблицыEntry[]
; -
Теперь, если вы взгляните на ячейку 10 таблицы, вы увидите an object класса
Entry
с именемHashMap$Entry
; - Мы добавor 4 пары ключ-meaning, но в массиве только 2!!! Это потому что, если 2 an object имеют одинаковый хэш-code, то они будут храниться в одной ячейке. Но How? Объекты будут храниться в виде связного списка (
LinkedList
).
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
...//продолжение codeа
}
Hashcode for Japan = 95 так How длина слова Japan имеет нечетное количество букв.
Hashcode for India = 95 так How длина слова India имеет нечетное количество букв.
HashCode for Russia = 31 так How длина слова Russia имеет четное количество букв.
HashCode for France = 31 так How длина слова France имеет четное количество букв.
Следующий рисунок объяснит идею связного списка: Теперь, когда у вас уже есть понимание о структуре хэш-карт, давайте перейдем к методам put
и get
.
Put:
Давайте посмотрим, How используется этот метод:
/**
* Метод связывает указанное meaning с указанным ключом в данной хэш-карте. Если
* карта до этого уже содержала некоторое meaning, соответствующее этому ключу,
* то старое meaning заменяется на указанное.
* @param key
* ключ, с которым связывается указанное meaning
* @param value
* meaning, связываемое с указанным ключом
* @возвращает meaning связанное с <tt>ключом</tt>, or <tt>null</tt>,
* если ниHowое meaning не соответствует <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;
}
Теперь давайте шаг за шагом попытаемся понять этот code:
-
Проверяем an object
key
на equalsствоnull
. Если так и есть, то an objectkey
будет сохранен в ячейкеtable[0]
, потому что хэш-code дляnull
всегда equals 0; -
Далее у an object
key
вызываем методhashcode()
, который высчитает его хэш-code. Этот хэш-code используется для определения ячейки массива, где будет храниться an object классаEntry
. Иногда бывает так, что эта функцияhashcode
написана не слишком умело, потому разработчики JDK создали другу функцию —hash()
, которая в качестве аргумента принимает до этого высчитанный хэш-code. Если интересно почитать про эту функцию более подробно, можете пройти по ссылке; -
indexFor(hash,table.length)
используется для определения конкретной ячейку в массивеtable
, в которую будет определен для хранения an object классаEntry
; -
Как мы видели в нашем примере, если два an object
key
имеют одинаковый хэш-code (эта ситуации известна, How коллизия), то они будут сохранены в форме связного списка. Поэтому на данном этапе мы проводим итерацию нашего списка: -
если только что рассчитанная ячейка пуста, то an object класса
Entry
будет сохранен непосредственно в эту ячейку; -
если в этой ячейке уже содержится Howой-либо an object, тогда происходит итерация до element, у которого поле
next
равноnull
. После этого наш an object классаEntry
становится следующим в списке; -
что, если мы добавим такой же an object
key
еще раз? По логике он должен заменить старое meaning. Да, так и будет. Во время итерации будет производиться сравнение ключей с помощью методаequals()
(key.equals(k)
). Если результатом будет истина, то старое meaning будет заменено на meaning текущего an objectEntry
.
Get:
Теперь давайте взглянем на применение метода
/**
* returns meaning, которое соответствует указанному ключу, or {@code null}, если
* данная карта не содержит пары с указанным ключом.
*
*
* <p>
* Более точно, если в данной карте содержится такой ключ {@code k}
* с соответствующим ему meaningм {@code v}, что {@code (key==null ? k==null : key.equals(k))},
* то метод возвращает {@code v}; в противном случае возвращается {@code null}.
* (может быть не более одной такой пары)
*
* </p><p>
* Возвращенное meaning {@code null} не <i>обязательно</i> говорит о том, что
* в карте нет пары с таким указанным ключом; а возможно, что в карте однозначно
* указано соответствие этого ключа со meaningм {@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 в хэш-картах, понять, How работает метод
get
, очень просто. Когда вы передаете методу Howой-либо ключ, чтобы получить meaning из хеш-карты:
-
Объект
Ekey проверяется на equalsство null
. Если так и есть, то будет возвращено meaning an object, хранящегося в ячейкеtable[0]
; -
У an object key вызывается метод
hashcode()
, который высчитывает хэш-code; -
indexFor(hash,table.length)
используется для определения конкретной ячейки массиваtable
, из которой необходимо взять an object классаEntry
; -
После получения номера ячейки массива
table
будет произведена итерация по списку и сравнение ключей с помощью методаequals()
. Если результатом будет истина, то будет возвращено meaning an objectEntry
, в противном случае —null
.
What следует запомнить:
-
Класс
HashMap
имеет внутренний классEntry
, который хранит пары ключ-meaning; -
Объекты класса
Entry
хранятся в массивеEntry[ ]
под названиемtable
; -
Ячейка массива называется корзиной и хранит первый элемент из связного списка;
-
Метод
hashcode()
an objectkey
используется для поиска корзины этого an object классаEntry
; -
Если ключи двух an objectов имеют одинаковый хэш-code, они будут сохранены в одной корзине массива
table
; -
Метод
equals()
an objectkey
используется для подтверждения его уникальности; -
Методы
equals()
иhashcode()
an objectvalue
вообще не используются.
GO TO FULL VERSION