Як працює HashMap у Java

Більшість з вас погодяться, що HashMapна сьогоднішній день є найулюбленішою темою для дискусій на співбесідах. Іноді я проводив подібні дискусії зі своїми колегами, і це справді допомогло. Тепер я зроблю таку дискусію з вами. Я вважаю, що якщо ви цікавитеся внутрішнім пристроєм та роботою HashMap, то ви вже знайомі з основами HashMap , тому я пропущу цю частину. Але якщо ви новачок у цій справі, раджу вам проїхати на сайт Java Docs . Перш ніж ми рушимо далі, я настійно рекомендую вам ознайомитися з моєю попередньою статтею: Робота з hashCode та методом equals у Java. Зміст цієї статті:

1. Єдина можлива відповідь.
2. Що таке хешування.
3. Трохи про клас Entry.
4. Що робить метод put().
5. Як працює метод get().
6. Примітки

Єдина можлива відповідь

Якщо хтось попросить мене пояснити « Як працює HashMap? », Я просто відповім: « За принципами Хешування ». Простіше нікуди. Щоб зрозуміти це та отримати розширену відповідь, треба бути впевненим, що ви знаєте основи Хешування. Правильно?

Що таке Хешування

Хешування в найпростішому поданні, це спосіб перетворення будь-якої змінної/об'єкта в унікальний код після застосування будь-якої формули/алгоритму до їх властивостей. Дана функція хешування повинна дотримуватися наступного правила: Хеш-функція повинна повертати однаковий хеш-код кожного разу, коли вона застосована до однакових або рівних об'єктів. Іншими словами, два однакові об'єкти повинні повертати однакові хеш-коди по черзі. Більше про це ви можете прочитати тут: Робота з hashCode та методом equals у Java

Трохи про клас 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завжди зберігатиметься в нульовій позиції масиву.

Я сподіваюся, що коректно передав свої думки у цій статті. Якщо ви знайшли помилки або у вас є питання, будь ласка залишайте їх у коментарях. Щасливого навчання!