SortedMap
В этой лекции мы изучим интерфейс SortedMap. Рассмотрим новые методы, которые присутствуют в этом интерфейсе, а также особенности одной из имплементаций SortedMap — TreeMap и их отличия, а также преимущества по сравнению с HashMap.
Давай посмотрим, как устроена иерархия карт. Обрати особое внимание на интерфейс SortedMap и его реализацию TreeMap, о которых мы говорим сегодня:
Интерфейс SortedMap — это расширение интерфейса Map. Он во многом похож на SortedSet (который в свою очередь расширяет Set), так они оба описывают аналогичную функциональность по хранению и использованию отсортированных значений.
SortedSet работает и хранит <TЗначение>, SortedMap SortedMap — пары <TКлюч, TЗначение>. Это карта, в которой все элементы отсортированы в порядке возрастания их ключей.
Интерфейс SortedMap расширяет Map. Дополнительно в нем объявлены такие методы:
| Метод | Описание |
|---|---|
| TКлюч firstKey() | Возвращает ключ первого элемента карты |
| TКлюч lastKey() | Возвращает ключ последнего элемента карты |
| SortedMap<TКлюч, TЗначение> headMap(TКлюч end) | Возвращает карту SortedMap, которая содержит все элементы оригинального SortedMap вплоть (т.е, не включительно) до элемента с ключом end |
| SortedMap<TКлюч, TЗначение> tailMap(K start) | Возвращает карту SortedMap, которая содержит все элементы оригинального SortedMap, начиная с элемента с ключом start (включительно) |
| SortedMap<TКлюч, TЗначение> subMap(TКлюч start, TКлюч end) | Возвращает карту SortedMap, которая содержит все элементы оригинального SortedMap вплоть от элемента с ключом start до элемента с ключом end (end — не включительно) |
Класс 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);
Результат:
Если при добавлении элемента выяснится, что элемент с таким ключом уже есть, старое значение ключа заменится на новое. Это показано на примере двух пар элементов — ("Олег",3) и ("Олег",5).
Рассмотрим пример с созданным 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
-
Если тебе нужно получить ключ первого ученика, можно воспользоваться методом firstKey():
String firstKey = map.firstKey(); System.out.println("Первый ключ → " + firstKey);Результат: Первый ключ → Антон
-
Если тебе нужно получить ключ последнего ученика, можно воспользоваться методом lastKey():
String lastKey = map.lastKey(); System.out.println("Последний ключ → " + lastKey);Результат: Последний ключ → Юрий
-
Получить все объекты, которые стоят после объекта с ключом “Сергей”:
Map<String, Integer> tailMap = map.tailMap("Сергей"); System.out.println("tailMap: " + tailMap);Результат: tailMap: {Сергей=5, Юрий=4}
-
Получить все объекты, которые стоят до объекта с ключом “Николай”:
System.out.println("headMap: " + headMap); Map<String, Integer> headMap = map.headMap("Николай");Результат: headMap: {Антон=5}
-
Получить все объекты, которые стоят после объекта с ключом “Олег”, но которые стоят до объекта с ключом “Сергей”:
Map<String, Integer> subMap = map.subMap("Олег", "Сергей"); System.out.println("subMap: " + subMap);Результат: subMap: {Олег=5, Руслан=5}
СравнениеHashMap и 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 не гарантирует нам ни порядка хранения, ни порядка получения элементов с карты.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ