Свайпніть щоб показати меню

Тепер розглянемо детальніше клас, який реалізує інтерфейс Map — HashMap.

Цей клас широко використовується при роботі з мапами. Ви вже мали можливість працювати з цим класом і вивчати його методи. Але давайте з'ясуємо, як саме працює цей клас.

Спочатку потрібно зрозуміти, що таке хеш-код, оскільки він використовується всередині HashMap.

Хеш-код

Кожен об'єкт має власний хеш-код, який можна отримати за допомогою методу Object класу hashCode(). Розглянемо приклад:

Main.java


              123456789
            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Як видно, об'єкт String з даними "Hello World!" має хеш-код "-969099747". Метод, який визначає, який саме хеш-код буде перевизначено у класі String, виглядає так:

Main.java


              1234567
            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

Об'єкт String розбивається на масив байтів за допомогою методу getBytes(), після чого кожен байт обробляється та додається до хеш-коду. Таким чином, хеш-код стає максимально унікальним, що допомагає програмі ідентифікувати цей об'єкт.

Для об'єктів кастомних класів також можна перевизначити хеш-код, визначивши унікальний спосіб отримання цього числа для об'єктів. Створимо тестовий клас User і перевизначимо для нього метод hash code.

Main.java


              12345678910111213141516171819202122232425262728293031
            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

У класі User є 2 атрибути, які я використав у методі hashCode(). Я обрав випадкові операції у методі hashCode(), щоб отримати максимально випадкове число, роблячи його унікальним для кожного об'єкта User.

Саме це і є хеш-код. Тепер дізнаємося, як він використовується у HashMap.

HashMap

Сам HashMap можна уявити як масив бакетів. Бакет — це список, у якому зберігається елемент. Спочатку HashMap має 16 бакетів, що є значенням DEFAULT_INITIAL_CAPACITY.

Коли ви додаєте елемент у HashMap за допомогою методу put(), HashMap повинен визначити, у який саме бакет помістити цей елемент. Для цього використовується проста формула: keyValue.hashCode() & (n - 1), де n — це розмір масиву бакетів у HashMap. '&' — це побітова операція AND, яка є низькорівневим програмуванням, тому ми не будемо заглиблюватися в деталі.

Важливо розуміти, що HashMap використовує хеш-код значення ключа для пошуку відповідного бакета. Тому важливо створювати максимально унікальний хеш-код, щоб уникати колізій.

Колізія

Яким би унікальним не був хеш-код, все одно може виникнути ситуація, коли HashMap обчислює один і той самий бакет для двох елементів. У таких випадках виникає колізія. Простими словами, колізія — це ситуація, коли два або більше елементів потрапляють в один і той самий бакет. Вони зберігаються там у вигляді SinglyLinkedList, який ви реалізували раніше.

Розглянемо ілюстрацію:

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

Як HashMap обробляє колізії?

HashMap також вирішує проблему колізій шляхом постійного збільшення розміру масиву бакетів. Коли кількість елементів досягає 75% розміру масиву бакетів, HashMap ініціює зміну розміру, подвоюючи розмір масиву бакетів. Після цього елементи розподіляються по нових бакетах з використанням нового значення n у формулі.

Таким чином, HashMap є високоефективною структурою даних і часто використовується як основна реалізація інтерфейсу Map.

1. Яка з наступних реалізацій використовує хеш-таблицю для зберігання пар ключ-значення?

2. Що відбувається у `HashMap`, якщо два ключі мають однаковий хеш-код?

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 1. Розділ 14

Запитати АІ

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Секція 1. Розділ 14

Робота з HashMap у Java

Хеш-код

HashMap

Колізія

Як HashMap обробляє колізії?

1. Яка з наступних реалізацій використовує хеш-таблицю для зберігання пар ключ-значення?

2. Що відбувається у HashMap, якщо два ключі мають однаковий хеш-код?

2. Що відбувається у `HashMap`, якщо два ключі мають однаковий хеш-код?