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);

Результат:

Если при добавлении элемента выяснится, что элемент с таким ключом уже есть, старое значение ключа заменится на новое. Это показано на примере двух пар элементов — ("Олег",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

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. Получить все объекты, которые стоят до объекта с ключом “Николай”:

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

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

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 не гарантирует нам ни порядка хранения, ни порядка получения элементов с карты.

19

Задача

Java Syntax Pro, 19 уровень, 2 лекция

Недоступна

Знакомство с foreach

В классе Solution публичный метод print(ArrayList<Integer>) выводит в консоли все элементы списка по порядку. Сейчас метод реализован с использованием оператора for. Необходимо переписать реализацию метода print(ArrayList<Integer>), используя метод списка forEach(), принимающий лямбда-выражение. Лог

Открыть

19

Задача

Java Syntax Pro, 19 уровень, 2 лекция

Недоступна

Прощание с foreach

В классе Solution публичный метод print(ArrayList<String>) выводит в консоли все элементы списка по порядку. Сейчас метод реализован с использованием метода списка forEach(). Необходимо переписать реализацию метода print(ArrayList<String>), используя оператор for, не меняя логику работы метода. Мето

Открыть

19

Задача

Java Syntax Pro, 19 уровень, 2 лекция

Недоступна

Знакомство со ссылками на методы

В классе Solution публичный метод print(ArrayList<String>) выводит в консоли все элементы списка по порядку. Сейчас метод реализован с использованием метода списка forEach(), который принимает лямбда-выражение. Необходимо переписать реализацию метода print(ArrayList<String>), чтобы метод списка forE

Открыть

19

Задача

Java Syntax Pro, 19 уровень, 2 лекция

Недоступна

Прощание со ссылками на методы

В классе Solution публичный метод print(ArrayList<Integer>) выводит в консоли все элементы списка по порядку. Сейчас метод реализован с использованием метода списка forEach(), который принимает ссылку на метод. Необходимо переписать реализацию метода print(ArrayList<Integer>), чтобы метод списка for

Открыть

19

Задача

Java Syntax Pro, 19 уровень, 2 лекция

Недоступна

Преобразование списка в массив

В классе Solution есть два публичных статических метода: - String[] toStringArray(ArrayList<String>), в котором нужно преобразовать список строк в массив строк и вернуть его; - Integer[] toIntegerArray(ArrayList<Integer>), в котором нужно преобразовать список чисел в массив чисел и вернуть его; Для

Открыть