Інтерфейси SortedMap та NavigableMap. Клас TreeMap

В Java інтерфейси SortedMap та NavigableMap забезпечують зберігання пар “ключ-значення” в сортованому порядку, а також додають можливість навігації по ключах. Клас TreeMap є реалізацією цих інтерфейсів і використовує бінарне дерево для зберігання даних.

1. Інтерфейс SortedMap

SortedMap — це підінтерфейс Map, який гарантує, що ключі зберігаються в сортованому порядку. Сортування може виконуватися або відповідно до природного порядку (якщо ключі реалізують інтерфейс Comparable), або з використанням користувацького компаратора (Comparator), переданого під час створення мапи.

Основні методи SortedMap:

• firstKey(): Повертає найменший ключ у мапі.
• lastKey(): Повертає найбільший ключ.
• headMap(K toKey): Повертає частину мапи, що містить ключі, менші за toKey.
• tailMap(K fromKey): Повертає частину мапи, що містить ключі, більші або рівні fromKey.
• subMap(K fromKey, K toKey): Повертає частину мапи, що містить ключі в діапазоні від fromKey до toKey.

Приклад використання SortedMap:

import java.util.SortedMap;
import java.util.TreeMap;

public class Main {
public static void main(String[] args) {
SortedMap<String, Integer> map = new TreeMap<>();
map.put(“Київ”, 2800000);
map.put(“Львів”, 721301);
map.put(“Одеса”, 1014000);

// Виводимо мапу у відсортованому порядку
System.out.println(map);

// Найменший і найбільший ключі
System.out.println(“Найменший ключ: ” + map.firstKey());
System.out.println(“Найбільший ключ: ” + map.lastKey());

// Підмножини карти
System.out.println(“Підмножина до ‘Львів’: ” + map.headMap(“Львів”));
System.out.println(“Підмножина від ‘Львів’: ” + map.tailMap(“Львів”));
}
}

2. Інтерфейс NavigableMap

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

Основні методи NavigableMap:

• lowerKey(K key): Повертає найбільший ключ, який менший за вказаний.
• floorKey(K key): Повертає найбільший ключ, який менший або рівний вказаному.
• ceilingKey(K key): Повертає найменший ключ, який більший або рівний вказаному.
• higherKey(K key): Повертає найменший ключ, який більший за вказаний.
• descendingMap(): Повертає мапу, впорядковану в зворотному порядку.
• pollFirstEntry(): Видаляє і повертає перший (найменший) елемент.
• pollLastEntry(): Видаляє і повертає останній (найбільший) елемент.

Приклад використання NavigableMap:

import java.util.NavigableMap;
import java.util.TreeMap;

public class Main {
public static void main(String[] args) {
NavigableMap<String, Integer> map = new TreeMap<>();
map.put(“Київ”, 2800000);
map.put(“Львів”, 721301);
map.put(“Одеса”, 1014000);

// Навігація по ключах
System.out.println(“Найменший ключ, більший або рівний ‘Львів’: ” + map.ceilingKey(“Львів”));
System.out.println(“Найбільший ключ, менший за ‘Львів’: ” + map.lowerKey(“Львів”));

// Мапа у зворотному порядку
System.out.println(“Мапа у зворотному порядку: ” + map.descendingMap());

// Видалення і повернення найменшого і найбільшого елементів
System.out.println(“Перший елемент: ” + map.pollFirstEntry());
System.out.println(“Останній елемент: ” + map.pollLastEntry());
}
}

3. Клас TreeMap

TreeMap — це реалізація інтерфейсів NavigableMap та SortedMap, яка зберігає ключі в відсортованому порядку. Вона використовує бінарне дерево (зазвичай червоно-чорне дерево) для зберігання елементів, забезпечуючи швидкий пошук, вставку та видалення за час O(log n).

Особливості TreeMap:

• Сортування: Ключі автоматично зберігаються у відсортованому порядку.
• Підтримка навігації: Додає можливість легко шукати найближчі ключі до вказаного.
• Швидкий доступ: Операції вставки, видалення та пошуку виконуються за час O(log n).
• Не підтримує null ключі: TreeMap не дозволяє використовувати null як ключі, але дозволяє null як значення.

Приклад використання TreeMap:

import java.util.TreeMap;

public class Main {
public static void main(String[] args) {
TreeMap<String, Integer> treeMap = new TreeMap<>();

// Додавання елементів
treeMap.put(“Яблуко”, 10);
treeMap.put(“Банан”, 20);
treeMap.put(“Груша”, 15);

// Виведення у відсортованому порядку
System.out.println(treeMap);

// Отримання підмножини
System.out.println(“Підмножина від ‘Банан’ до ‘Яблуко’: ” + treeMap.subMap(“Банан”, “Яблуко”));
}
}

Переваги TreeMap:

• Автоматичне сортування: Ключі автоматично зберігаються у відсортованому порядку.
• Швидкий пошук і навігація: Завдяки бінарному дереву, операції пошуку та навігації виконуються швидко.
• Можливість навігації: Доступні операції для знаходження найближчих елементів, підмножин і роботи зі зворотними множинами.

Недоліки:

• Повільніший доступ, ніж у HashMap: Виконання операцій за час O(log n) повільніше, ніж O(1) у HashMap.
• Не підтримує null ключі: Це може бути проблемою в деяких випадках.

Висновок

• SortedMap гарантує, що ключі будуть зберігатися у відсортованому порядку.
• NavigableMap розширює можливості навігації по ключах, надаючи додаткові методи для пошуку найближчих ключів.
• TreeMap є потужною реалізацією цих інтерфейсів і використовується, коли потрібна сортування ключів та навігація по них.

Інтерфейси SortedMap та NavigableMap. Клас TreeMap