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

Це процес перетворення об’єкта в ціле число. Ціле число допомагає в індексації та швидшому пошуку.

Що таке HashMap

HashMap є частиною фреймворку колекції Java. Він використовує техніку під назвою хешування. Він реалізує інтерфейс карти. Він зберігає дані в парі ключ і значення. HashMap містить масив вузлів, і вузол представлений як клас. Для внутрішнього зберігання ключа та значення він використовує масив і структуру даних LinkedList. У HashMap є чотири поля.

Перш ніж зрозуміти внутрішню роботу HashMap, ви повинні знати про метод hashCode() і equals().

unix проти windows

дорівнює():Він перевіряє рівність двох об'єктів. Він порівнює ключ, незалежно від того, рівні вони чи ні. Це метод класу Object. Його можна перевизначити. Якщо ви перевизначаєте метод equals(), то обов’язково перевизначаєте метод hashCode().hashCode():Це метод класу об'єктів. Він повертає посилання на пам’ять об’єкта в цілочисельній формі. Значення, отримане від методу, використовується як номер сегмента. Номер сегмента — це адреса елемента всередині карти. Хеш-код нульового ключа дорівнює 0.Відра:Масив вузла називається бакетами. Кожен вузол має структуру даних, як LinkedList. Більш ніж один вузол може спільно використовувати одне відро. Він може бути різним за місткістю.

Вставте пару «Ключ, значення» в HashMap

Ми використовуємо метод put(), щоб вставити пару ключів і значень у HashMap. Розмір HashMap за замовчуванням становить 16 (від 0 до 15).

приклад

У наступному прикладі ми хочемо вставити три пари (ключ, значення) у HashMap.

 HashMap map = new HashMap(); map.put('Aman', 19); map.put('Sunny', 29); map.put('Ritesh', 39); 

Давайте подивимося, з яким індексом буде збережена пара «Ключ-значення» в HashMap. Коли ми викликаємо метод put(), він обчислює хеш-код ключа 'Aman'. Припустимо, хеш-код «Aman» дорівнює 2657860. Щоб зберегти ключ у пам’яті, нам потрібно обчислити індекс.

Розрахунок індексу

Індекс мінімізує розмір масиву. Формула для розрахунку індексу така:

 Index = hashcode(Key) & (n-1) 

Де n – розмір масиву. Отже, значення індексу для «Амана» таке:

 Index = 2657860 & (16-1) = 4 

Значення 4 — це обчислене значення індексу, де ключ і значення зберігатимуться в HashMap.

декодування base64 у js

Хеш-колізія

Це випадок, коли обчислене значення індексу однакове для двох або більше ключів. Давайте розрахуємо хеш-код для іншого ключа «Sunny». Припустимо, хеш-код для «Sunny» — 63281940. Щоб зберегти ключ у пам’яті, нам потрібно обчислити індекс за допомогою формули індексу.

 Index=63281940 & (16-1) = 4 

Значення 4 — це обчислене значення індексу, де ключ зберігатиметься в HashMap. У цьому випадку метод equals() перевіряє, чи рівні обидва ключі. Якщо ключі однакові, замініть значення на поточне значення. В іншому випадку підключіть цей об’єкт вузла до існуючого об’єкта вузла через LinkedList. Тому обидва ключі зберігатимуться під індексом 4.

Так само ми будемо зберігати ключ «Ritesh». Припустимо, хеш-код для ключа 2349873. Значення індексу буде 1. Отже, цей ключ зберігатиметься під індексом 1.

метод get() у HashMap

Метод get() використовується для отримання значення за його ключем. Він не отримає значення, якщо ви не знаєте ключа. Коли викликається метод get(K Key), він обчислює хеш-код ключа.

Припустімо, ми повинні отримати ключ «Аман». Буде викликаний наступний метод.

конвертувати з рядка в ціле число java

 map.get(new Key('Aman')); 

Він генерує хеш-код як 2657860. Тепер обчисліть значення індексу 2657860 за допомогою формули індексу. Значення індексу буде 4, як ми розрахували вище. метод get() шукає значення індексу 4. Він порівнює перший елемент Key із заданим Key. Якщо обидва ключі рівні, тоді повертається значення else check для наступного елемента у вузлі, якщо він існує. У нашому сценарії він знайдений як перший елемент вузла та повертає значення 19.

Давайте принесемо ще один ключ 'Сонячний'.

Хеш-код ключа «Sunny» — 63281940. Розраховане значення індексу 63281940 дорівнює 4, як ми розрахували для методу put(). Перейдіть до індексу 4 масиву та порівняйте ключ першого елемента з заданим ключем. Він також порівнює ключі. У нашому сценарії вказаний ключ є другим елементом, а наступний вузол має значення null. Він порівнює другий елемент Key з указаним Key і повертає значення 29. Він повертає null, якщо наступний вузол має значення null.