Інтерфейси 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 є потужною реалізацією цих інтерфейсів і використовується, коли потрібна сортування ключів та навігація по них.