Mapa posortowana

posortowana mapa

W tym wykładzie przyjrzymy się interfejsowi SortedMap . Rozważ nowe metody obecne w tym interfejsie, a także cechy jednej z implementacji SortedMap - TreeMap i ich różnice, a także zalety w stosunku do HashMap .

Zobaczmy, jak działa hierarchia map. Zwróć szczególną uwagę na interfejs SortedMap i jego implementację TreeMap , o której dzisiaj mówimy:

Interfejs SortedMap jest rozszerzeniem interfejsu Map . Pod wieloma względami jest podobny do SortedSet (który z kolei rozszerza Set ), ponieważ obie opisują podobną funkcjonalność do przechowywania i używania posortowanych wartości.

SortedSet działa i przechowuje<TValue>, SortedMap SortedMap -<TKey, TValue>. To jest mapa, na której wszystkie elementy są posortowane rosnąco według ich kluczy.

Interfejs SortedMap rozszerza Map . Dodatkowo deklaruje następujące metody:

Klasa TreeMap

Klasa TreeMap jest implementacją interfejsu SortedMap . Oznacza to, że TreeMap implementuje wszystkie dodatkowe metody SortedMap oraz standardowe z interfejsu Map .

Możesz utworzyć obiekt typu TreeMap za pomocą poleceń w postaci:

• TreeMap() : tworzy pustą mapę w postaci drzewa;

• TreeMap(Map<? extends TKey,​? extends TValue> map) : tworzy drzewo, do którego dodaje wszystkie elementy z mapy

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : tworzy drzewo, do którego dodawane są wszystkie elementy ze smapa;

• TreeMap(Comparator<?super TKey>comparator) : Tworzy puste drzewo, w którym wszystkie dodane elementy zostaną następnie posortowane według komparatora.

Gdzie TKey to typ kluczy w parze elementów, TValue to typ wartości w parze elementów, które będą przechowywane w TreeMap .

Komparator jest dość ważną rzeczą dla SortedMap / TreeMap . Dostarcza informacji o tym, według jakich reguł musimy sortować - czyli budować porządek na naszej mapie. Jeśli nie zostanie podany podczas tworzenia SortedMap , to zostanie zastosowana naturalna kolejność naszego klucza.

Dodawanie elementów do TreeMap

Elementy są dodawane do mapy w parach na raz: służy do tego metoda put() . Klucz jest przekazywany jako pierwszy, wartość jako druga. Na przykład chcemy utworzyć listę uczniów i ich ocen.

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

Wynik:

Jeśli podczas dodawania elementu okaże się, że istnieje już element z takim samym kluczem, stara wartość klucza zostanie zastąpiona nową. Ilustruje to przykład dwóch par elementów - („Oleg”,3) i („Oleg”,5) .

Rozważmy przykład z utworzonym Comparatorem . Powiedzmy, że musimy przechowywać elementy posortowane według długości łańcucha klucza. Jeśli długość klawiszy jest równa, to porównanie przebiega według kolejności alfabetycznej (kolejność naturalna dla napisów):

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

Sekwencja będzie następująca:

To zachowanie sprawia, że ​​TreeMap wygląda jak posortowana tablica lub lista, jeśli mają słowa ( String ) jako indeksy zamiast liczb.

Metody SortedMap na przykładzie klasy TreeMap

1. Jeśli chcesz zdobyć klucz pierwszego ucznia, możesz użyć metody firstKey() :

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

   Wynik: Pierwszy klawisz → Anton

2. Jeśli chcesz uzyskać klucz ostatniego ucznia, możesz użyć metody lastKey() :

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

   Wynik: Ostatni klucz → Yuri

3. Zdobądź wszystkie przedmioty, które pojawiają się po obiekcie za pomocą klawisza „ Siergiej ”:

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

   Wynik: mapa ogona: {Sergei=5, Yuri=4}

4. Zdobądź wszystkie obiekty, które znajdują się przed obiektem za pomocą klawisza „ Nikolai ”:

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

   Wynik: headMap: {Anton=5}

5. Zdobądź wszystkie obiekty, które znajdują się za obiektem z kluczem „ Oleg ”, ale przed obiektem z kluczem „ Siergiej ”:

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

   Wynik: mapa podrzędna: {Oleg=5, Rusłan=5}

Porównanie HashMap i SortedMap/TreeMap

Porozmawiajmy o kolejności i kolejności przechowywania elementów:

• Ponieważ HashMap nie daje nam żadnych gwarancji co do kolejności iteracji, zmieni się ona całkowicie po dodaniu nowych elementów.

• W TreeMap kolejność będzie zgodna z „naturalną kolejnością” kluczy zgodnie z ich metodą CompareTo() (lub zewnętrznie dostarczonym Comparator ). Nie zapominaj również, że TreeMap implementuje interfejs SortedMap , który zawiera metody zależne od tego porządku sortowania.

Pod względem wydajności i szybkości:

• HashMap to mapa oparta na kluczach mieszających. Obsługuje operacje wstawiania i pobierania w ustalonymO(1). Aby to zrobić, klucze muszą mieć implementacjehashCode()iequals().

• TreeMap to mapa oparta na drzewie. Jego operacje insert i get zajmują czas logarytmiczny, który zależy od liczby elementów w mapieO(log n). Jest to konieczne, aby elementy miały jakiś mechanizm porównania zapewniany przez nasz klucz lub zewnętrzny komparator. Kolejność iteracji jest określana przez ten mechanizm.

Czynniki te są podstawą naszej decyzji o tym, co i kiedy użyć.

Jeśli musimy przechowywać wartości w jakiejś kolejności, wybór jest oczywisty – potrzebujemy SortedMap . Chociaż jest nieco wolniejszy niż HashMap , wykonuje to, co jest dla nas ważne.

Jak wspomniano wcześniej, dzięki SortedMap możemy uzyskać pierwszy (lub ostatni) klucz, wartość lub parę klucz-wartość na naszej mapie, niezależnie od tego, kiedy ta wartość została dodana. Nie możemy tego zrobić z implementacją HashMap .

Rozważ to na przykładzie, w którym mamy mapę z kluczami (imionami uczniów) i wartościami (ich ocenami). Powiedzmy, że chcemy pracować z listą w odwrotnej kolejności alfabetycznej.

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

Przykład pokazuje, że przy użyciu HashMap zadanie wygląda na bardziej skomplikowane, ponieważ HashMap nie gwarantuje nam ani kolejności przechowywania, ani kolejności pobierania elementów z mapy.