Тепер розглянемо детальніше клас, що реалізує інтерфейс 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.

Навіщо це знати?

Це теорія низькорівневого програмування, яка важлива, оскільки при роботі з великими наборами даних структури даних можуть суттєво впливати на продуктивність застосунку. Це трапляється, коли ці структури даних використовуються неправильно.

Неправильне використання структур даних виникає через те, що програмісти не розуміють, як ці структури працюють. Адже ви ж хочете стати хорошим програмістом, чи не так?

Крім того, питання про структури даних часто ставлять на співбесідах.

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

У IntelliJ IDEA утримуйте Ctrl (Windows/Linux) або Command (macOS) і натисніть на назву класу, щоб перейти до його визначення та переглянути всі доступні методи.

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

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

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

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

Секція 3. Розділ 2

Запитати АІ

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

Suggested prompts:

Can you explain more about how hash codes are generated in Java?

What happens if two objects have the same hash code in a HashMap?

Why is it important to override the hashCode() method in custom classes?

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

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

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

Хеш-код

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);
    }
}

Main.java


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

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());
    }
}

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

HashMap

Колізія

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

Як HashMap справляється з колізіями?

Навіщо це знати?

Крім того, питання про структури даних часто ставлять на співбесідах.

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

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

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

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

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

Секція 3. Розділ 2

Робота з HashMap у Java

Хеш-код

HashMap

Колізія

Як HashMap справляється з колізіями?

Навіщо це знати?

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

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

Робота з HashMap у Java

Хеш-код

HashMap

Колізія

Як HashMap справляється з колізіями?

Навіщо це знати?

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

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

Робота з HashMap у Java

Хеш-код

HashMap

Колізія

Як HashMap справляється з колізіями?

Навіщо це знати?

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

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

Робота з HashMap у Java

Хеш-код

HashMap

Колізія

Як HashMap справляється з колізіями?

Навіщо це знати?

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

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

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

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