Сортирана карта

Сортирана карта

В този урок ще изучаваме интерфейса SortedMap . Ще проучим новите методи, които се появяват в този интерфейс, Howто и характеристиките на една реализация на SortedMap — TreeMap — и разликите между реализациите, Howто и техните предимства в сравнение с HashMap .

Нека да видим How изглежда йерархията на картите. Обърнете специално внимание на интерфейса SortedMap и неговата реализация TreeMap — те са нашият фокус днес:

Интерфейсът SortedMap разширява интерфейса на Map . В много отношения той е подобен на SortedSet (което от своя страна разширява Set ), тъй като и двата описват подобна функционалност за съхраняване и използване на сортирани стойности.

SortedSet работи с и съхранява<TValue>обекти, но SortedMap съхранява<TKey, TValue>двойки. Това е карта, която съхранява всички свои елементи във възходящ ред на техните ключове.

Интерфейсът SortedMap разширява Map . Той добавя следните методи:

Клас TreeMap

Класът TreeMap е реализация на интерфейса SortedMap . Тоест TreeMap имплементира всички методи, добавени от SortedMap , Howто и стандартните от интерфейса на Map .

Можете да създадете обект TreeMap , като използвате конструктори като тези:

• TreeMap() : създава празна карта, реализирана като дърво;

• TreeMap(Map<? extends TKey, ? extends TValue> map) : създава дърво и добавя всички елементи от входната карта;

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : създава дърво и добавя всички елементи от въведената сортирана карта;

• TreeMap(Comparator<? super TKey> comparator) : създава празно дърво — компараторът ще се използва за сортиране на всички елементи, когато бъдат добавени впоследствие.

Тук TKey е типът на ключовете в съхранените двойки, а TValue е типът на стойностите в двойките, съхранени в TreeMap .

Comparator е доста важен за SortedMap / TreeMap . Той установява правилата за сортиране or подреждане на нашата карта. Ако не предоставим компаратор, тогава ще се използва естественото подреждане на нашите ключове, когато създаваме SortedMap .

Добавяне на елементи към TreeMap

Елементите се добавят към карта като двойки с помощта на метода put() . Ключът се предава като първи аргумент, а стойността се предава като втори. Да предположим например, че искаме да създадем списък със студенти и техните оценки.

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

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Резултат:

Когато добавим двойка ключ-стойност, ако ключът вече съществува в колекцията, тогава старата стойност се заменя с новата стойност. Това поведение е илюстрирано в нашия пример с две двойки, които имат един и същ ключ — ("Oliver", 3) и ("Oliver", 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> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Ето получената последователност:

Това поведение прави TreeMap като сортиран масив or списък, чиито индекси са думи ( String ) instead of числа.

Методи SortedMap в класа TreeMap

1. Ако трябва да получите ключа на първия ученик, можете да използвате метода firstKey() :

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   Резултат: Първи клавиш → Антъни

2. Ако трябва да получите ключа на последния ученик, можете да използвате метода lastKey() :

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   Резултат: Последен ключ → Джеф

3. Вземете всички обекти, които идват след обекта с ключа " Sara ":

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   Резултат: tailMap: {Sara=5, Jeff=4}

4. Вземете всички обекти, които идват преди обекта с ключа " Ник ":

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   Резултат: headMap: {Anthony=5}

5. Вземете всички обекти, които идват след обекта с ключа " Oliver " и идват преди обекта с ключа " Sara ":

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   Резултат: подкарта: {Oliver=5, Roxy=5}

Сравнение на HashMap и SortedMap/TreeMap

Нека поговорим за това How елементите се подреждат и съхраняват:

• Тъй като HashMap не ни дава ниHowви гаранции относно реда при повторение, редът може напълно да се промени, когато се добавят нови елементи.

• В TreeMap редът се основава на "естественото подреждане" на ключовете според техния метод compareTo() (or Comparator , който предоставяме). Също така, не забравяйте, че TreeMap имплементира интерфейса SortedMap , който съдържа методи, които зависят от този ред на сортиране.

Сега се обръщаме към разглеждане на производителността и скоростта:

• HashMap е карта, базирана на ключове за хеширане. Може да вмъква и получава елементи вO(1), постоянно време. За да поддържат това, ключовете трябва да имплементиратhashCode()иequals().

• TreeMap е дървовидна карта. Неговите операции по вмъкване и извличане отнемат логаритмично време, т.е.O(log n), което зависи от броя на елементите в картата. Това е необходимо, така че елементите да имат няHowъв механизъм за сравнение, предоставен or от нашия ключ, or от външен Comparator. Този механизъм определя реда на повторение.

И тези фактори ни помагат да решим кои колекции да използваме и кога.

Ако трябва да съхраняваме стойности в определен ред, изборът е очевиден – имаме нужда от SortedMap . Въпреки че е малко по-бавен от HashMap , той изпълнява важни задачи за нас.

Както споменахме по-рано, SortedMap може да ни даде първия (or последния) ключ, or стойност, or двойка ключ-стойност в нашата карта, независимо кога е добавена тази стойност. Реализацията на HashMap не може да направи това.

Например, помислете за карта с ключове (имена на ученици) и стойности (техните оценки). Да кажем, че искаме да работим със списък в обратен азбучен ред.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 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("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


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

Примерът показва, че използването на HashMap прави задачата по-сложна, тъй като HashMap не гарантира нито реда на съхранение, нито реда на получаване на елементи от картата.