SortedMap

SortedMap

У цій лекції ми вивчимо інтерфейс SortedMap. Розглянемо нові методи, які є в цьому інтерфейсі, а також особливості однієї з імплементацій SortedMap — TreeMap та їхні відмінності, а також переваги порівняно з HashMap.

Давай подивимося, як влаштована ієрархія карт. Зверніть особливу увагу на інтерфейс SortedMap та його реалізацію TreeMap, про які ми говоримо сьогодні:

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

SortedSet працює і зберігає <TЗначення>, SortedMap SortedMap — пари <TКлюч, TЗначення>. Це карта, в якій всі елементи відсортовані у порядку зростання їхніх ключів.

Інтерфейс SortedMap розширює Map. Додатково в ньому оголошено такі методи:

Клас TreeMap

Клас TreeMap — це імплементація інтерфейсу SortedMap. Тобто в TreeMap реалізовані всі додаткові методи SortedMap і стандартні з інтерфейсу Map.

Створити об’єкт типу TreeMap можна за допомогою команд виду:

• TreeMap(): створює порожню карту у вигляді дерева;

• TreeMap(Map<? extends TКлюч,​? extends TЗначення> map): створює дерево, в яке додає всі елементи з карти map;

• TreeMap(SortedMap<TКлюч, ? extends TЗначення> smap): створює дерево, до якого додає всі елементи з карти smap;

• TreeMap(Comparator<? super TКлюч> comparator): створює порожнє дерево, де всі елементи, що додаються, згодом будуть відсортовані компаратором.

Де TКлюч — це тип ключів із пари елементів, TЗначення — тип значень у парі елементів, які зберігатимуться у карті TreeMap.

Comparator — досить важлива річ для SortedMap/TreeMap. Він надає інформацію про те, за якими правилами нам потрібно сортувати, тобто вибудовувати порядок у нашій карті. Якщо його не надано під час створення SortedMap, то буде використовуватися природний порядок нашого ключа.

Додавання елементів у TreeMap

Елементи додаються в карту відразу парами: для цього використовується метод put(). Першим до нього передається ключ, другим – значення. Наприклад, ми хочемо створити список учнів та їхніх оцінок.

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Антон", 5);
map.put("Сергій", 5);
map.put("Руслан", 5);
map.put("Юрій", 4);
map.put("Микола", 4);
map.put("Олег", 3);
map.put("Олег", 5);

System.out.println(map);

Результат:

Якщо у процесі додавання елемента з’ясується, що елемент із таким ключем вже є, старе значення ключа заміниться на нове. Це показано на прикладі двох пар елементів — ("Олег",5) i ("Олег",4).

Розглянемо приклад зі створеним Comparator-ом. Припустимо, нам потрібно зберігати елементи у відсортованому вигляді за довжиною ключа-рядка. Якщо довжина ключів однакова, далі йде порівняння, ґрунтуючись на алфавітному порядку (натуральний порядок для рядків):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComaredMap = new TreeMap<String,Integer>(new LengthComparator());

lengthComaredMap.put("Юрій",4);
lengthComaredMap.put("Олег",5);
lengthComaredMap.put("Руслан",4);
lengthComaredMap.put("Ян",4);

Послідовність буде такою:

Така поведінка робить TreeMap схожим на відсортований масив або список, якби у них як індекси виступали слова (String), а не числа.

Методи SortedMap на прикладі класу TreeMap

1. Якщо тобі потрібно отримати ключ першого учня, можна скористатися методом firstKey():

   String firstKey = map.firstKey();
   	System.out.println("Перший ключ → " + firstKey);

   Результат: Перший ключ → Антон

2. Якщо тобі потрібно отримати ключ останнього учня, можна скористатися методом lastKey():

   String lastKey = map.lastKey();
   System.out.println("Останній ключ → " + lastKey);

   Результат: Останній ключ → Юрій

3. Отримати всі об’єкти, які стоять після об’єкта із ключем “Сергій”:

   Map<String, Integer> tailMap = map.tailMap("Сергій");
            	System.out.println("tailMap: " + tailMap);

   Результат: tailMap: {Сергій=5, Юрій=4}

4. Отримати всі об’єкти, які стоять до об’єкта із ключем “Микола”:

   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Микола");

   Результат: headMap: {Антон=5}

5. Отримати всі об’єкти, які стоять після об’єкта із ключем “Олег”, але які стоять до об’єкта із ключем “Сергій”:

   Map<String, Integer> subMap = map.subMap("Олег", "Сергій");
   System.out.println("subMap: " + subMap);

   Результат: subMap: {Олег=5, Руслан=5}

Порівняння HashMap i SortedMap/TreeMap

Давай поговоримо про послідовність та порядок зберігання елементів:

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

• У TreeMap порядок буде відповідно до “natural order” ключів відповідно до їхнього методу compareTo() (або Comparator, що поставляється зовні). Також не слід забувати, що TreeMap реалізує інтерфейс SortedMap, який містить методи, що залежать від цього порядку сортування.

Якщо йдеться про продуктивність та швидкодію:

• HashMap — карта, заснована на хешуванні ключів. Вона підтримує операції вставлення та отримання елементів за фіксований час O(1). Для цього ключі повинні мати реалізації hashCode() та equals().

• TreeMap — карта, побудована на основі дерева. Її операції вставлення та отримання займають логарифмічний час, який залежить від кількості елементів у карті O(log n). Це необхідно, щоб елементи мали певний механізм порівняння, наданий або нашим ключем, або зовнішнім Компаратором. Порядок ітерацій визначається цим механізмом.

На цих факторах і базується наше рішення про те, що і коли краще використовувати.

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

Як уже сказано раніше, з SortedMap ми можемо отримати перший (чи останній) ключ або значення, або пару ключ-значення в нашій карті, незалежно від того, коли це значення додали. З реалізацією HashMap ми цього зробити не можемо.

Розглянемо це на прикладі, коли ми маємо карту з ключами (Імена студентів) і значеннями (їх оцінки за залік). Припустимо, нам бажано працювати зі списком у зворотному алфавітному порядку.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Антон", 5);
sorted.put("Сергій", 5);
sorted.put("Юрій", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Антон", 5);
hash.put("Сергій", 5);
hash.put("Юрій", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Або сортувати вручну, зберігаючи елементи в масив або список (зі збереженням порядку вставки)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

На прикладі видно: у разі використання HashMap завдання виглядає складніше, оскільки HashMap не гарантує нам ані порядку зберігання, ані порядку отримання елементів із карти.