В даному матеріали спробуємо зрозуміти як влаштована Map в Java. Дана структура даних стає в нагоді дуже часто при розробці складних додатків.

Коли ми чуємо слово мап, то перше, що спадає на думку – це карта (у мене гугл мапс). Map як структура даних немає нічого спільного з картами гугл.

Ієрархія класів Map в Java

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

Map в java – це структура даних, яка зберігає дані як <Ключ, Значення>. Кожне значення можна знайти за його ключем. Як вашу картку можна знайти за іменем. Вважайте що повне імʼя це ключ, а сама картка це обʼєкт (значення).

Трохи фактів про мап:

• карта не може містити дублікати ключів;
• кожен ключ може відображати лише одне значення (далі ми подивимося реалізації map і що буває, якщо спробувати додати кілька об’єктів з одним ключем);
• Map не розширює інтерфейс Collection.

Ієрархія класів Map трохи схожа на Set:

Як бачимо, у інтерфейсу мап є кілька реалізацій. Найпопулярніші це: HashMap, TreeMap.

HashMap – зберігає ключі у hash-таблиці. Вона має найбільшу продуктивність. Однак, така реалізація не гарантує порядок елементів.

TreeMap – зберігає ключі в відсортованому порядку. Працює повільніше, ніж хешмап.

LinkedHashMap – зберігає ключі в порядку їх вставки в карту. Працює трохи повільніше, ніж HashMap.

WeakHashMap – реалізація інтерфейсу Map на основі хеш-таблиці зі слабкими ключами. Запис WeakHashMap буде автоматично видалено, якщо його ключ більше не використовується звичайним чином.

Розглянемо докладніше HashMap. Швидкість її роботи О(1), а в гіршому випадку O(logn). Щоб зрозуміти, коли буде найгірший випадок давайте розберемося як вона працює. Це, до речі, дуже популярне питання на співбесідах.

Як працює Map

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

Якщо за таким ключем вже є значення в карті, то перевіряється об’єкт, який ми намагаємось додати, якщо він такий самий, як і існуючий, то йде перезапис. Якщо об’єкти різні, а хеш код однаковий (відбулася колізія або ми неправильно перевизначили метод hashCode) об’єкт поміщається в ту саму комірку у вигляді зв’язаного списку. Ось звідки найгірший випадок роботи HashMap. Коли хеш код ключів однаковий ця структура починає працювати як LinkedList швидкість якого O(logn). Ви можете запитати: як потрібно перевизначити метод hashCode, щоб він повертав однакове значення для всіх об’єктів?

Ось вам приклад:

package ua.com.antitutor.main;

public class MapExample {
    private String name;
    private double sum;

    public MapExample(String name, double sum) {
        this.name = name;
        this.sum = sum;
    }

    @Override
    public int hashCode() {
        return 1;
    }

    public static void main(String[] args) {
        MapExample example1 = new MapExample("Some name", 34);
        MapExample example2 = new MapExample("Another name", 12.5);
        System.out.println(example1.hashCode()); //1
        System.out.println(example2.hashCode()); //1
    }
}

Треба постаратися щоб таке зробити, але все ж таки схожі ситуації можуть трапитись.

Приклади з Map

Тепер перейдемо до прикладів з мап. Будуть розглянуті лише найпопулярніші методи. Вони однакові у всіх реалізаціях.

package ua.com.antitutor.main;

import java.util.HashMap;
import java.util.Map;

public class MapExample {

    public static void main(String[] args) {
        Map<Integer, String> users = new HashMap<>();
        users.put(1, "Oleh");//додавання елементів
        users.put(2, "Oksana");
        users.put(3, "Anton");
        System.out.println(users.get(2));//отримання обєкта за його ключем

        System.out.println(users.containsKey(1));//перевірка чи містить мап такий ключ
        users.remove(1);//видалення по ключу
        System.out.println(users.containsKey(1));

        System.out.println(users.size());//розмір

        System.out.println(users.isEmpty());//перевірка на пустоту

        users.forEach((k, v) -> System.out.println(k + ": " + v));//вівід ключа і значення
    }
}

В результаті виконання коду матимемо такий результат:

Що ще хотілося б згадати про Map в java:

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

Ось і все, що стосується інтерфейсу Map та його реалізації. Дана структура даних інколи може стати у великій нагоді.