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 . Ви побачите таку таблицю: Тут ми бачимо наступне:
-
Є масив
Entry[]
із 16 осередків з ім'ямtable
; -
У цьому масиві зберігаються об'єкти класу
Entry
. КласHashMap
має внутрішній клас —Entry
. І екземплярами цього класу є пари ключ-значення. Давайте поглянемо на структуру класуEntry
: -
Щоразу, коли ми намагаємося створити пару ключ-значення в хеш-карті, для цієї пари створюється об'єкт класу
Entry
, і він буде зберігатися у вказаній вище таблиціEntry[]
. А тепер вам має бути цікаво, куди саме в цій таблиці буде записаний цей об'єкт (у якийсь осередок). Для ключа з пари ключ-значення обчислюється хеш-код за допомогою методуhashcode()
. І цей хеш-код використовується для обчислення номера комірки таблиціEntry[]
; -
Тепер, якщо ви подивитеся на комірку 10 таблиці, ви побачите об'єкт класу
Entry
з ім'ямHashMap$Entry
; - Ми додали 4 пари ключ-значення, але у масиві тільки 2!!! Це тому, що якщо 2 об'єкти мають однаковий хеш-код, то вони зберігатимуться в одному осередку. Але як? Об'єкти зберігатимуться у вигляді зв'язкового списку (
LinkedList
).
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
...//продолжение кода
}
Hashcode for Japan = 95 так як длина слова Japan имеет нечетное количество букв.
Hashcode for India = 95 так як длина слова India имеет нечетное количество букв.
HashCode for Russia = 31 так як длина слова Russia имеет четное количество букв.
HashCode for France = 31 так як длина слова France имеет четное количество букв.
Наступний малюнок пояснить ідею зв'язкового списку: Тепер, коли у вас вже є розуміння структури хеш-карт, давайте перейдемо до методів 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;
}
Тепер давайте крок за кроком спробуємо зрозуміти цей код:
-
Перевіряємо об'єкт
key
на рівністьnull
. Якщо так і є, то об'єктkey
буде збережений в комірціtable[0]
, тому що хеш-кодnull
завжди дорівнює 0; -
Далі об'єкт
key
викликаємо методhashcode()
, який вирахує його хеш-код. Цей хеш-код використовується для визначення осередку масиву, де зберігатиметься об'єкт класуEntry
. Іноді буває так, що ця функціяhashcode
написана не надто вміло, тому розробники JDK створабо другу функцію —hash()
, яка в якості аргументу приймає раніше вирахований хеш-код. Якщо цікаво почитати про цю функцію докладніше, можете пройти посилання ; -
indexFor(hash,table.length)
використовується для визначення конкретної комірки в масивіtable
, в яку буде визначено для зберігання об'єкт класуEntry
; -
Як ми бачабо в нашому прикладі, якщо два об'єкти
key
мають однаковий хеш-код (ця ситуація відома як колізія), то вони будуть збережені у формі зв'язкового списку. Тому на цьому етапі ми проводимо ітерацію нашого списку: -
якщо щойно розрахована осередок порожня, то об'єкт класу
Entry
буде збережено безпосередньо в цей осередок; -
якщо в цій клітинці вже міститься якийсь об'єкт, тоді відбувається ітерація до елемента, у якого поле
next
дорівнюєnull
. Після цього наш об'єкт класуEntry
стає наступним у списку; -
що, якщо ми додамо такий самий об'єкт
key
ще раз? За логікою він має замінити старе значення. Да так і буде. Під час ітерації буде проводитись порівняння ключів за допомогою методуequals()
(key.equals(k)
). Якщо результатом буде істина, то старе значення буде замінено значення поточного об'єктаEntry
.
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
дуже просто. Коли ви передаєте методу будь-який ключ, щоб отримати значення з хеш-картки:
-
Об'єкт
Ekey перевіряється на рівність null
. Якщо так і є, то буде повернуто значення об'єкта, що зберігається в комірціtable[0]
; -
У об'єкта key викликається метод
hashcode()
, який обчислює хеш-код; -
indexFor(hash,table.length)
використовується для визначення конкретного осередку масивуtable
, з якого необхідно взяти об'єкт класуEntry
; -
Після отримання номера осередку масиву
table
буде проведено ітерацію за списком і порівняння ключів за допомогою методуequals()
. Якщо результатом буде істина, буде повернуто значення об'єктаEntry
, інакше —null
.
Що слід запам'ятати:
-
Клас
HashMap
має внутрішній класEntry
, який зберігає пари ключ-значення; -
Об'єкти класу
Entry
зберігаються в масивіEntry[ ]
під назвоюtable
; -
Осередок масиву називається кошиком і зберігає перший елемент зі зв'язкового списку;
-
Метод
hashcode()
об'єктаkey
використовується для пошуку кошика цього об'єкта класуEntry
; -
Якщо ключі двох об'єктів мають однаковий хеш-код, вони будуть збережені в одному кошику масиву
table
; -
Метод
equals()
об'єктаkey
використовується на підтвердження його унікальності; -
Методи
equals()
таhashcode()
об'єктаvalue
взагалі не використовуються.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ