Як працює HashMap в Java: основи та принципи використання

HashMap Java — це одна з найпопулярніших структур даних, яка дозволяє зберігати пари “ключ-значення” та забезпечує швидкий доступ до значень за допомогою ключів. Коротенько нагадаю про курси Java start як стартовий курс для напрацювання базових знань та JAVA – для виходу на рівень Junior. Приєднуйтесь, друзі. А поки-що – рухаємось далі:

Внутрішня структура HashMap

HashMap працює за допомогою масиву, який містить так звані “бакети” (buckets) — це своєрідні комірки, де зберігаються елементи. Якщо подивитися на код HashMap, то можна побачити, що він містить у собі масив Node<K,V>[]. Node — це клас, який реалізує інтерфейс Map.Entry та містить чотири основні поля:

hash: зберігає попередньо обчислений хеш-код ключа.
key: сам ключ, за яким відбувається пошук значення.
value: значення, асоційоване з ключем.
next: посилання на наступний елемент у разі колізії (ланцюжок елементів).

Внутрішня будова класу HashMap:

static class Node<K,V> implements Map.Entry<K,V> {

   final int hash;

   final K key;

   V value;

   Node<K,V> next;

   Node(int hash, K key, V value, Node<K,V> next) {

       this.hash = hash;

       this.key = key;

       this.value = value;

       this.next = next;

   }

   public final K getKey()        { return key; }

   public final V getValue()      { return value; }

   public final String toString() { return key + "=" + value; }

   public final int hashCode() {

       return Objects.hashCode(key) ^ Objects.hashCode(value);

   }

   public final V setValue(V newValue) {

       V oldValue = value;

       value = newValue;

       return oldValue;

   }

   public final boolean equals(Object o) {

       if (o == this)

           return true;

       if (o instanceof Map.Entry) {

           Map.Entry<?,?> e = (Map.Entry<?,?>)o;

           if (Objects.equals(key, e.getKey()) &&

               Objects.equals(value, e.getValue()))

               return true;

       }

       return false;

   }

}

Коли виконується додавання елементів до HashMap у Java, обчислюється хеш-код ключа, і на його основі визначається індекс у масиві бакетів, куди цей елемент буде покладений. Якщо бакет з цим індексом порожній, новий Node просто додається в нього. Ця операція дуже швидка, оскільки обчислення індексу масиву з хеш-коду виконується за константний час — O(1).

Вивчити основи Java в короткі терміни ви можете на курсі від Сергія Немчинського Java Start !

Деталі курсу

Колізія

В ідеальному випадку кожений елемент мав би мати свій особистий бакет, але через обмеженість можливих значень хеш-кодів часто виникають колізії, коли різні ключі потрапляють до одного й того ж бакета, бо в них вираховується однаковий хеш-код. Тож якщо бакет вже містить інші елементи, відбувається порівняння ключів за допомогою equals. Якщо вони однакові – іде зміна значення (value). Якщо ключі різні – додається новий елемент до ланцюжку.

У випадку колізій, коли кілька елементів зберігаються в одному бакеті у вигляді ланцюжка (зв’язаного списку), складність пошуку в гіршому випадку збільшується до O(n), де n — кількість елементів у цьому ланцюжку.

Проте в середньому, завдяки рівномірному розподілу хеш-кодів і хорошій реалізації hashCode(), складність пошуку залишається O(1) для більшості випадків.

Розглянемо приклад. Припустимо, що у вас є два ключі, які, після обчислення хеш-коду, мають однаковий індекс у масиві бакетів. Перший ключ (наприклад, “key1”) додається в порожній бакет під номером 2, створюючи новий Node. Коли ви додаєте другий ключ (наприклад, “key2”), який має той самий хеш-код і, відповідно, індекс у масиві, HashMap поміщає цей новий елемент у той самий бакет, але вже у вигляді нового Node, який посилається на попередній.

Node<K,V> firstNode = new Node<>(hash1, key1, value1, null);

Node<K,V> secondNode = new Node<>(hash1, key2, value2, firstNode);

У випадку, коли ви додаєте два елементи із однаковими ключами, проте із різним значення, HashMap просто замінює значення першого елемента на нове значення, тобто перезаписує його.

Допустимо, в хеш мапі вже є елемент із ключем “key1” та значенням “value1”.

Node<K,V> firstNode = new Node<>(hash1, key1, value1, null);

Тож коли ви додаєте другий елемент з таким самим ключем, проте іншим значенням, HashMap знаходить існуючий ключ “key1” у тому ж бакеті (оскільки хеш-коди збігаються) і виконує перевірку equals(), щоб переконатися, що ключі рівні. Оскільки вони рівні, значення value1 замінюється на нове значення “value2”, і ланцюжок не змінюється:

Node<K,V> firstNode = new Node<>(hash1, key1, value2, null);

Дуже важливо, щоб ключі в HashMap були immutable (незмінними). Адже якщо ключ змінюється після того, як він був доданий у HashMap, це може порушити розподіл елементів по бакетам. Адже у нового ключа вже буде вирахуваний новий хеш код, але елемент знаходиться в комірці за старим хеш кодом. Це призведе до того, що об’єкт стане недоступним, або будуть порушені правила порівняння в бакеті.

FoxmindEd – це навчальний центр, що має велику різноманітність напрямків курсів для новачків та програмістів з досвідом!

Тільки починаєте свій шлях в ІТ? Спробуйте курси Start

Вже маєте базові навички програмування? Тоді
курси Junior саме для вас.

Хочете поглибити свої знання в ІТ? Ми маємо курси Middle/Senior

Роль методу hashCode() та equals()

Перевизначення методів hashCode() та equals() і розуміння контракту між ними є критично важливими для коректної роботи із HashMap та інших хешованих структур даних.

Роль hashCode()

Метод hashCode() відповідає за обчислення хеш-коду об’єкта, який використовується для визначення його місця в масиві бакетів. Цей хеш-код потім трансформується в індекс масиву, де зберігатиметься відповідна пара “ключ-значення”. У ідеальному випадку, добре реалізований метод hashCode() рівномірно розподіляє елементи по всьому масиву, зменшуючи кількість колізій і підвищуючи ефективність операцій додавання та пошуку.

Роль equals()

Метод equals() використовується для порівняння ключів під час пошуку або заміни елементів у HashMap. Якщо два ключі мають однаковий хеш-код (тобто потрапляють в один і той же бакет), equals() визначає, чи є ці ключі дійсно однаковими, і чи слід замінити існуюче значення або додати новий елемент у ланцюжок.

Підпишіться на наш Ютуб-канал! Корисні відео для програмістів чекають на вас! YouTube

Оберіть свій курс програмування! Шлях до кар’єри програміста починається тут! Подивитись

Основні операції в HashMap

HashMap надає кілька ключових операцій, які дозволяють ефективно працювати з даними, організованими у вигляді пар “ключ-значення”. Розглянемо основні операції та їхні особливості:

Додавання елементів: метод put(K key, V value):

Цей метод використовується для додавання нової пари “ключ-значення” до HashMap або для оновлення значення існуючого ключа. Якщо ключ уже існує в мапі, старе значення замінюється новим. У випадку колізії, коли кілька ключів мають однаковий хеш-код і, відповідно, потрапляють до одного бакета, новий елемент додається до ланцюжка всередині цього бакета.

Отримання значень: метод get(Object key):

Цей метод повертає значення за ключем. Якщо ключ присутній у мапі, повертається відповідне значення. Якщо ж ключа немає в мапі, метод повертає null. Важливо зазначити, що повернення null може означати як відсутність ключа, так і те, що значення, асоційоване з цим ключем, дорівнює null.

Видалення елементів: метод remove(Object key):

Цей метод видаляє з HashMap пару “ключ-значення” за заданим ключем. Якщо ключ присутній, він видаляється разом із відповідним значенням, і структура мапи коригується відповідно. Якщо ж ключа немає, метод нічого не змінює в структурі.

Перевірка наявності ключа: метод containsKey(Object key):

Цей метод перевіряє, чи містить HashMap певний ключ. Повертає true, якщо ключ є в мапі, і false, якщо ключ відсутній.

Перевірка наявності значення: метод containsValue(Object value):

Цей метод перевіряє, чи містить HashMap певне значення.

Отримання розміру: метод size():

Цей метод повертає кількість пар “ключ-значення”, що зберігаються в HashMap.

Перебір значень:

HashMap надає кілька способів перебору пар “ключ-значення”. Найпоширеніші способи включають:

Перебір за допомогою entrySet(): Ви можете використовувати цикл for-each для перебору всіх пар “ключ-значення” в HashMap:

for (Map.Entry<K, V> entry : map.entrySet()) {

   K key = entry.getKey();

   V value = entry.getValue();

   // Виконуйте потрібні дії з ключем і значенням

}

Перебір ключів за допомогою keySet(): Можна перебирати лише ключі

for (K key : map.keySet()) {

   V value = map.get(key);

   // Виконуйте потрібні дії з ключем і значенням

}

Перебір значень за допомогою values(): Можна перебирати лише значення

for (V value : map.values()) {

   // Виконуйте потрібні дії зі значенням

}

Порядок перебору елементів у HashMap не гарантований і може змінюватися. Це пов’язано з тим, що HashMap не зберігає елементи в якомусь визначеному порядку (наприклад, за часом додавання або за порядком ключів). Якщо вам важливий порядок, розгляньте використання інших колекцій, таких як LinkedHashMap.

Висновок

HashMap є однією з найефективніших та найпоширеніших структур даних для зберігання та швидкого доступу до пар “ключ-значення”. Завдяки своїй внутрішній структурі, що базується на масиві бакетів і хешуванні, HashMap забезпечує середню складність операцій O(1) для додавання, отримання та видалення елементів, що робить її незамінною в багатьох застосунках.

Як працює hashmap в Java