Більшість з вас погодяться, що
Я вважаю, що якщо ви цікавитеся внутрішнім пристроєм та роботою HashMap, то ви вже знайомі з основами HashMap , тому я пропущу цю частину. Але якщо ви новачок у цій справі, раджу вам проїхати на сайт Java Docs . Перш ніж ми рушимо далі, я настійно рекомендую вам ознайомитися з моєю попередньою статтею: Робота з hashCode та методом equals у Java. Зміст цієї статті:
Більше про це ви можете прочитати тут: Робота з hashCode та методом equals у Java
HashMap
на сьогоднішній день є найулюбленішою темою для дискусій на співбесідах. Іноді я проводив подібні дискусії зі своїми колегами, і це справді допомогло. Тепер я зроблю таку дискусію з вами. 
- Єдина можлива відповідь.
- Що таке хешування.
- Трохи про клас
Entry
. - Що робить метод
put()
. - Як працює метод
get()
. - Примітки
Єдина можлива відповідь
Якщо хтось попросить мене пояснити « Як працює HashMap? », Я просто відповім: « За принципами Хешування ». Простіше нікуди. Щоб зрозуміти це та отримати розширену відповідь, треба бути впевненим, що ви знаєте основи Хешування. Правильно?Що таке Хешування
Хешування в найпростішому поданні, це спосіб перетворення будь-якої змінної/об'єкта в унікальний код після застосування будь-якої формули/алгоритму до їх властивостей. Дана функція хешування повинна дотримуватися наступного правила: Хеш-функція повинна повертати однаковий хеш-код кожного разу, коли вона застосована до однакових або рівних об'єктів. Іншими словами, два однакові об'єкти повинні повертати однакові хеш-коди по черзі.Примітка: Всі об'єкти java успадковують стандартну реалізацію hashCode() функції, описаної в класі Object . Ця функція повертає хеш-код, отриманий шляхом конвертації внутрішньої адресаи об'єкта в число, що веде до створення унікального коду для кожного окремого об'єкта. |
Трохи про клас Entry
Карта (map) за визначенням, це - "Об'єкт що зберігає попарно значення (values) і ключі (keys)". Досить просто, так? Значить, у HashMap повинен бути якийсь механізм, що зберігає пари Значень і Ключів? Відповідь – Так.HashMap
має внутрішній клас Entry
, який виглядає так:
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
...//остальной код тут…
}
Природно, клас Entry
має ключ і значення зберігаються як атрибути. Ключ позначений як final
і ще бачимо два додаткових поля: next
і hash
. Ми постараємося зрозуміти призначення цих полів у ході статті.
Що робить Java метод put()
Перш ніж ми заглибимося у реалізацію методуput()
, дуже важливо зрозуміти, що екземпляри класу Entry
зберігаються у масиві. Клас HashMap визначає цю змінну як:
/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
transient Entry[] table;
Тепер погляньте на код реалізації методу put()
:
/**
* Связывает определенное значення с определенным ключом в этой карте(map).
* Если карта перед этим содержала значення для данного ключа, это значення
* заменится на новое.
*
* @param key
* ключ с которым указанное значення должно быть связано.
* @param value
* значення которое должно быть связано с ключом.
* @return вернет предыдущее значення связанное с key, або null
* если не было значений связанных с key. (Вернет null
* так же, если перед этим key был связан со значенням null)
*/
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;
}
Давайте розберемося з цим крок за кроком:
- Насамперед, перевіряємо чи існує ключ. Якщо ключ не існує (
null
), значення міститься в таблиці на нульову позицію, тому що хеш-код для значенняnull
,это – всегда 0
. - На наступному кроці, розраховується хеш-значення, використовуючи хеш-код ключа, що отримується викликом методу
hashCode()
. Це хеш-значення використовується для обчислення позиції в масиві, куди буде розміщено об'єктEntry
. Дизайнери JDK припускали, що погано написана функціяhashCode()
може повернути надто високе чи надто низьке значення хеш-коду. Для вирішення цієї проблеми, вони ввели іншуhash()
функцію, і передали в неї значення хеш-коду об'єкта, щоб привести хеш-значення у відповідність до розміру масиву. - Тепер викликається функція
indexFor(hash, table.length)
для обчислення точної позиції, куди буде поміщений об'єктEntry
. - Тут розпочинається головна частина. Тепер, виходячи з того, що нам відомо, що – два не рівні об'єкти можуть мати рівні значення хеш-кодів, поставимо запитання: Чи будуть два різні об'єкти поміщатися в однакову позицію в масиві [кошик]? Відповіддю є
LinkedList
. Якщо пам'ятаєте, класEntry
має атрибут «next
». Цей атрибут завжди вказує на наступний об'єкт ланцюга. Це точно відповідає поведінціLinkedList
.
Entry
зберігаються у формі LinkedList
. Коли об'єкт Entry
повинен бути поміщений у певне місце, HashMap перевіряє чи вже немає в цьому місці запису. Якщо запису немає, то об'єкт поміщається у цю позицію. Якщо все ж таки в цій позиції вже є об'єкт, перевіряється наступний атрибут. Якщо він повертає null
і поточний об'єкт Entry
стає наступною ланкою LinkedList
. Якщо наступна змінна не null
, процедура повторюється для наступної, доки знайде null
. Що якщо ми помістимо інший об'єкт з іншим значенням, але з тим же ключем, що був раніше? Логічно це має призвести до заміни старого значення. Як це відбувається? Загалом, після визначення позиції об'єкта Entry
, під час проходу до LinkedList
розрахункової позиції,HashMap
викликає метод порівняння ключа кожному за об'єкта Entry
. Всі ці Entry
об'єкти LinkedList
можуть мати аналогічні хеш-коди, але метод equals()
перевірить їх на справжню подібність. Це призведе до заміни значення лише всередині об'єкта Entry
. Таким чином HashMap гарантує унікальність усіх ключів.
Як працює Java метод get()
Тепер ми маємо уявлення про те, як пари ключ-значення зберігаються вHashMap
. Наступним великим питанням буде: Що відбувається, коли об'єкт передається з HashMap методом get()
? Як визначається значення об'єкта? Відповідь ми вже повинні знати, тому що спосіб, яким визначається унікальність ключа в методі, put()
має ту ж логіку, яку застосовує метод get()
. Як тільки HashMap
визначає ключ об'єкта, переданого в аргументі, він просто повертає значення відповідного об'єкта Entry
. Якщо збігів не знайдено, метод get()
поверне null
. Давайте поглянемо на код:
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()
до цього місця if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
, після цього просто повертає значення об'єкта.
Примітки
- Структура даних для зберігання в об'єкті
Entry
це масив з ім'ямtable
та типомEntry
. - Кожна індивідуальна позиція в масиві називається кошиком, тому що вона може містити перший елемент
LinkedList
об'єктівEntry
. hashCode()
Ключа потрібно обчислити позиції об'єктаEntry
.equals()
Ключ використовується для перевірки унікальності ключа в карті(map
).hashCode()
таequals()
Значення не використовується в методахget()
таset()
вHashMap
.- Хеш-код для ключів зі значенням
null
це завжди 0. І такий об'єктEntry
завжди зберігатиметься в нульовій позиції масиву.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ