Do implementacji służy TreeMap w Javie Interfejs mapy i NavigableMap wraz z klasą AbstractMap. Mapa jest posortowana według naturalnego porządku klawiszy lub według: Komparator podawane w czasie tworzenia mapy, w zależności od użytego konstruktora. Okazuje się, że jest to skuteczny sposób sortowania i przechowywania par klucz-wartość. Porządek przechowywania utrzymywany przez mapę drzewa musi być spójny z równościami, tak jak każda inna posortowana mapa, niezależnie od jawnych komparatorów. Implementacja mapy drzewa nie jest zsynchronizowana w tym sensie, że jeśli dostęp do mapy ma wiele wątków jednocześnie i co najmniej jeden z wątków modyfikuje mapę strukturalnie, należy ją zsynchronizować zewnętrznie.
TreeMap w Javie jest konkretną implementacją interfejsu java.util.SortedMap. Zapewnia uporządkowaną kolekcję par klucz-wartość, gdzie klucze są uporządkowane na podstawie ich naturalnej kolejności lub niestandardowego komparatora przekazanego konstruktorowi.
TreeMap jest implementowany przy użyciu drzewa czerwono-czarnego, które jest rodzajem samobalansującego drzewa wyszukiwania binarnego. Zapewnia to wydajną wydajność typowych operacji, takich jak dodawanie, usuwanie i pobieranie elementów, przy średniej złożoności czasowej O (log n).
Oto przykład użycia klasy TreeMap:
Jawa
import> java.util.Map;> import> java.util.TreeMap;> public> class> Main {> >public> static> void> main(String[] args) {> >Map treeMap =>new> TreeMap();> >// Adding elements to the tree map> >treeMap.put(>'A'>,>1>);> >treeMap.put(>'C'>,>3>);> >treeMap.put(>'B'>,>2>);> >// Getting values from the tree map> >int> valueA = treeMap.get(>'A'>);> >System.out.println(>'Value of A: '> + valueA);> >// Removing elements from the tree map> >treeMap.remove(>'B'>);> >// Iterating over the elements of the tree map> >for> (String key : treeMap.keySet()) {> >System.out.println(>'Key: '> + key +>', Value: '> + treeMap.get(key));> >}> >}> }> |
>
>Wyjście
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Funkcje TreeMap
Niektóre ważne funkcje mapy drzewa są następujące:
- Ta klasa jest członkiem Kolekcje Javy Struktura.
- Klasa implementuje Interfejsy map w tym NavigableMap , SortedMap i rozszerza klasę AbstractMap.
- TreeMap w Javie nie zezwala na klucze zerowe (takie jak Map), dlatego zgłaszany jest wyjątek NullPointerException. Jednak z różnymi kluczami można powiązać wiele wartości null.
- Pary wpisów zwracane przez metody w tej klasie i jej widoki reprezentują migawki mapowań w momencie ich utworzenia. Nie obsługują metody Entry.setValue.
Przejdźmy teraz dalej i omówmy Synchronized TreeMap. Implementacja TreeMap nie jest zsynchronizowana. Oznacza to, że jeśli wiele wątków jednocześnie uzyskuje dostęp do zestawu drzewa i co najmniej jeden z wątków modyfikuje zestaw, musi on zostać zsynchronizowany zewnętrznie. Zwykle osiąga się to za pomocą metody Collections.synchronizedSortedMap. Najlepiej zrobić to w momencie tworzenia, aby zapobiec przypadkowemu, niezsynchronizowanemu dostępowi do zestawu. Można to zrobić w następujący sposób:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geekowie, teraz pewnie zastanawiacie się, jak TreeMap działa wewnętrznie?
Metody w TreeMap podczas pobierania zestawu kluczy i wartości zwracają Iterator, który jest z natury niezawodny. Zatem każda współbieżna modyfikacja spowoduje zgłoszenie ConcurrentModificationException . TreeMap opiera się na czerwono-czarnej strukturze danych drzewa.
Każdy węzeł w drzewie ma:
- 3 zmienne ( Klawisz K=Klucz, wartość V=Wartość, kolor logiczny=Kolor )
- 3 referencje ( Wejście z lewej = z lewej, wejście z prawej = z prawej, wejście nadrzędne = nadrzędne )
Konstruktory w TreeMap
Aby stworzyć TreeMap musimy stworzyć obiekt klasy TreeMap. Klasa TreeMap składa się z różnych konstruktorów, które umożliwiają ewentualne utworzenie TreeMap. Poniżej znajdują się konstruktory dostępne w tej klasie:
- Mapa Drzewa()
- TreeMap (komparator komparatora)
- Mapa Drzewa (Mapa M)
- TreeMap (SortedMap sm)
Omówmy je indywidualnie wraz z implementacją każdego konstruktora w następujący sposób:
Konstruktor 1: Mapa Drzewa()
Ten konstruktor służy do zbudowania pustej mapy drzewa, która zostanie posortowana przy użyciu naturalnej kolejności kluczy.
Przykład
Jawa
// Java Program to Demonstrate TreeMap> // using the Default Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // TreeMapImplementation> public> class> GFG {> >// Method 1> >// To show TreeMap constructor> >static> void> Example1stConstructor()> >{> >// Creating an empty TreeMap> >TreeMap tree_map> >=>new> TreeMap();> >// Mapping string values to int keys> >// using put() method> >tree_map.put(>10>,>'Geeks'>);> >tree_map.put(>15>,>'4'>);> >tree_map.put(>20>,>'Geeks'>);> >tree_map.put(>25>,>'Welcomes'>);> >tree_map.put(>30>,>'You'>);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap() constructor:
'>);> >// Calling constructor> >Example1stConstructor();> >}> }> |
>
>Wyjście
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktor 2: TreeMap (komparator komparatora)
Konstruktor ten służy do zbudowania pustego obiektu TreeMap, w którym elementy będą wymagały zewnętrznej specyfikacji kolejności sortowania.
Przykład
Jawa
// Java Program to Demonstrate TreeMap> // using Comparator Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Class 1> // Helper class representing Student> class> Student {> >// Attributes of a student> >int> rollno;> >String name, address;> >// Constructor> >public> Student(>int> rollno, String name, String address)> >{> >// This keyword refers to current object itself> >this>.rollno = rollno;> >this>.name = name;> >this>.address = address;> >}> >// Method of this class> >// To print student details> >public> String toString()> >{> >return> this>.rollno +>' '> +>this>.name +>' '> >+>this>.address;> >}> }> // Class 2> // Helper class - Comparator implementation> class> Sortbyroll>implements> Comparator {> >// Used for sorting in ascending order of> >// roll number> >public> int> compare(Student a, Student b)> >{> >return> a.rollno - b.rollno;> >}> }> // Class 3> // Main class> public> class> GFG {> >// Calling constructor inside main()> >static> void> Example2ndConstructor()> >{> >// Creating an empty TreeMap> >TreeMap tree_map> >=>new> TreeMap(> >new> Sortbyroll());> >// Mapping string values to int keys> >tree_map.put(>new> Student(>111>,>'bbbb'>,>'london'>),>2>);> >tree_map.put(>new> Student(>131>,>'aaaa'>,>'nyc'>),>3>);> >tree_map.put(>new> Student(>121>,>'cccc'>,>'jaipur'>),>1>);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(Comparator)'> >+>' constructor:
'>);> >Example2ndConstructor();> >}> }> |
>
>Wyjście
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Konstruktor 3: Mapa Drzewa (Mapa M)
Konstruktor ten służy do inicjowania TreeMap wpisami z danej mapy M, które zostaną posortowane przy użyciu naturalnej kolejności kluczy.
Przykład
Jawa
// Java Program to Demonstrate TreeMap> // using the Default Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> public> class> TreeMapImplementation {> >// Method 1> >// To illustrate constructor> >static> void> Example3rdConstructor()> >{> >// Creating an empty HashMap> >Map hash_map> >=>new> HashMap();> >// Mapping string values to int keys> >// using put() method> >hash_map.put(>10>,>'Geeks'>);> >hash_map.put(>15>,>'4'>);> >hash_map.put(>20>,>'Geeks'>);> >hash_map.put(>25>,>'Welcomes'>);> >hash_map.put(>30>,>'You'>);> >// Creating the TreeMap using the Map> >TreeMap tree_map> >=>new> TreeMap(hash_map);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(Map)'> >+>' constructor:
'>);> >Example3rdConstructor();> >}> }> |
>
>Wyjście
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktor 4: TreeMap (SortedMap sm)
Ten konstruktor służy do inicjowania TreeMap wpisami z danej posortowanej mapy, które będą przechowywane w tej samej kolejności, co podana posortowana mapa.
Przykład
Jawa
// Java Program to Demonstrate TreeMap> // using the SortedMap Constructor> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // TreeMapImplementation> public> class> GFG {> >// Method> >// To show TreeMap(SortedMap) constructor> >static> void> Example4thConstructor()> >{> >// Creating a SortedMap> >SortedMap sorted_map> >=>new> ConcurrentSkipListMap();> >// Mapping string values to int keys> >// using put() method> >sorted_map.put(>10>,>'Geeks'>);> >sorted_map.put(>15>,>'4'>);> >sorted_map.put(>20>,>'Geeks'>);> >sorted_map.put(>25>,>'Welcomes'>);> >sorted_map.put(>30>,>'You'>);> >// Creating the TreeMap using the SortedMap> >TreeMap tree_map> >=>new> TreeMap(sorted_map);> >// Printing the elements of TreeMap> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 2> >// Main driver method> >public> static> void> main(String[] args)> >{> >System.out.println(>'TreeMap using '> >+>'TreeMap(SortedMap)'> >+>' constructor:
'>);> >Example4thConstructor();> >}> }> |
>
>Wyjście
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metody w klasie TreeMap
| metoda | Przedsięwzięcie wykonane |
|---|---|
| jasne() | Metoda usuwa wszystkie mapowania z tego TreeMap i czyści mapę. |
| klon() | Metoda zwraca płytką kopię tej TreeMap. |
| zawieraKey (klucz obiektu) | Zwraca wartość true, jeśli ta mapa zawiera mapowanie dla określonego klucza. |
| zawieraWartość (wartość obiektu) | Zwraca wartość true, jeśli ta mapa odwzorowuje jeden lub więcej kluczy na określoną wartość. |
| zestaw wpisów() | Zwraca ustawiony widok mapowań zawartych na tej mapie. |
| pierwszyKlucz() | Zwraca pierwszy (najniższy) klucz aktualnie na tej posortowanej mapie. |
| pobierz (klucz obiektu) | Zwraca wartość, na którą ta mapa odwzorowuje określony klucz. |
| headMap (wartość klucza obiektu) | Metoda zwraca widok części mapy znacznie mniejszy niż parametr wartość_klucza. |
| zestaw kluczy() | Metoda zwraca widok zestawu kluczy zawartych w mapie drzewa. |
| ostatniKlucz() | Zwraca ostatni (najwyższy) klucz aktualnie na tej posortowanej mapie. |
| put(klucz obiektu, wartość obiektu) | Metoda ta służy do wstawiania mapowania na mapę. |
| putAll(mapa mapy) | Kopiuje wszystkie odwzorowania z określonej mapy na tę mapę. |
| usuń (klucz obiektu) | Usuwa mapowanie tego klucza z tej TreeMap, jeśli jest obecna. |
| rozmiar() | Zwraca liczbę mapowań klucz-wartość na tej mapie. |
| subMap((K klucz początkowy, K klucz końcowy) | Metoda zwraca część tej mapy, której zakres kluczy obejmuje zakres od startKey włącznie do endKey wyłącznie. |
| wartości() | Zwraca widok kolekcji wartości zawartych na tej mapie. |
Realizacja: Poniższe programy pokażą lepiej, jak tworzyć, wstawiać i przeglądać TreeMap.
Ilustracja:
Jawa
// Java Program to Illustrate Operations in TreeMap> // Such as Creation, insertion> // searching, and traversal> // Importing required classes> import> java.util.*;> import> java.util.concurrent.*;> // Main class> // Implementation of TreeMap> public> class> GFG {> >// Declaring a TreeMap> >static> TreeMap tree_map;> >// Method 1> >// To create TreeMap> >static> void> create()> >{> >// Creating an empty TreeMap> >tree_map =>new> TreeMap();> >// Display message only> >System.out.println(>'TreeMap successfully'> >+>' created'>);> >}> >// Method 2> >// To Insert values in the TreeMap> >static> void> insert()> >{> >// Mapping string values to int keys> >// using put() method> >tree_map.put(>10>,>'Geeks'>);> >tree_map.put(>15>,>'4'>);> >tree_map.put(>20>,>'Geeks'>);> >tree_map.put(>25>,>'Welcomes'>);> >tree_map.put(>30>,>'You'>);> >// Display message only> >System.out.println(>'
Elements successfully'> >+>' inserted in the TreeMap'>);> >}> >// Method 3> >// To search a key in TreeMap> >static> void> search(>int> key)> >{> >// Checking for the key> >System.out.println(>'
Is key ''> + key> >+>'' present? '> >+ tree_map.containsKey(key));> >}> >// Method 4> >// To search a value in TreeMap> >static> void> search(String value)> >{> >// Checking for the value> >System.out.println(>'
Is value ''> + value> >+>'' present? '> >+ tree_map.containsValue(value));> >}> >// Method 5> >// To display the elements in TreeMap> >static> void> display()> >{> >// Displaying the TreeMap> >System.out.println(>'
Displaying the TreeMap:'>);> >System.out.println(>'TreeMap: '> + tree_map);> >}> >// Method 6> >// To traverse TreeMap> >static> void> traverse()> >{> >// Display message only> >System.out.println(>'
Traversing the TreeMap:'>);> >for> (Map.Entry e :> >tree_map.entrySet())> >System.out.println(e.getKey() +>' '> >+ e.getValue());> >}> >// Method 6> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Calling above defined methods inside main()> >// Creating a TreeMap> >create();> >// Inserting the values in the TreeMap> >insert();> >// Search key '50' in the TreeMap> >search(>50>);> >// Search value 'Geeks' in the TreeMap> >search(>'Geeks'>);> >// Display the elements in TreeMap> >display();> >// Traversing the TreeMap> >traverse();> >}> }> |
>
>Wyjście
TreeMap successfully created Elements successfully inserted in the TreeMap Is key '50' present? false Is value 'Geeks' present? true Displaying the TreeMap: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You} Traversing the TreeMap: 10 Geeks 15 4 20 Geeks 25 Welcomes 30 You> Wykonywanie różnych operacji na TreeMap
Po wprowadzeniu Generics w Javie 1.5 możliwe jest ograniczenie typu obiektu, który może być przechowywany w TreeMap. Zobaczmy teraz, jak wykonać kilka często używanych operacji na TreeMap.
Operacja 1: Dodawanie elementów
Aby dodać element do TreeMap możemy skorzystać z metody put(). Jednakże kolejność wstawiania nie jest zachowywana w TreeMap. Wewnętrznie dla każdego elementu klucze są porównywane i sortowane w kolejności rosnącej.
Przykład
Jawa
// Java Program to Illustrate Addition of Elements> // in TreeMap using put() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Default Initialization of a TreeMap> >TreeMap tm1 =>new> TreeMap();> >// Inserting the elements in TreeMap> >// using put() method> >tm1.put(>3>,>'Geeks'>);> >tm1.put(>2>,>'For'>);> >tm1.put(>1>,>'Geeks'>);> >// Initialization of a TreeMap using Generics> >TreeMap tm2> >=>new> TreeMap();> >// Inserting the elements in TreeMap> >// again using put() method> >tm2.put(>new> Integer(>3>),>'Geeks'>);> >tm2.put(>new> Integer(>2>),>'For'>);> >tm2.put(>new> Integer(>1>),>'Geeks'>);> >// Printing the elements of both TreeMaps> >// Map 1> >System.out.println(tm1);> >// Map 2> >System.out.println(tm2);> >}> }> |
>
>Wyjście
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operacja 2: Zmiana elementów
Jeżeli po dodaniu elementów chcemy zmienić element, można to zrobić poprzez ponowne dodanie elementu metodą put(). Ponieważ elementy mapy drzewa są indeksowane za pomocą kluczy, wartość klucza można zmienić, po prostu wstawiając zaktualizowaną wartość klucza, dla którego chcemy zmienić.
Przykład
Jawa
// Java program to Illustrate Updation of Elements> // in TreeMap using put() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements in Map> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'Geeks'>);> >tm.put(>1>,>'Geeks'>);> >// Print all current elements in map> >System.out.println(tm);> >// Inserting the element at specified> >// corresponding to specified key> >tm.put(>2>,>'For'>);> >// Printing the updated elements of Map> >System.out.println(tm);> >}> }> |
>
>Wyjście
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operacja 3: Usuwanie elementu
W celu usunięcia elementu z TreeMap możemy skorzystać z metody usuwania(). Ta metoda pobiera wartość klucza i usuwa mapowanie klucza z tej mapy drzewa, jeśli jest on obecny na mapie.
Przykład
Jawa
wyjątki Javy
// Java program to Illustrate Removal of Elements> // in TreeMap using remove() Method> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'Geeks'>);> >tm.put(>1>,>'Geeks'>);> >tm.put(>4>,>'For'>);> >// Printing all elements of Map> >System.out.println(tm);> >// Removing the element corresponding to key> >tm.remove(>4>);> >// Printing updated TreeMap> >System.out.println(tm);> >}> }> |
>
>Wyjście
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operacja 4: Iteracja po TreeMap
Istnieje wiele sposobów iteracji po mapie. Najbardziej znanym sposobem jest użycie a dla każdej pętli i odbierz klucze. Wartość klucza można znaleźć za pomocą metody metoda getValue(). .
Przykład
Jawa
// Java Program to Illustrate Iterating over TreeMap> // using> // Importing required classes> import> java.util.*;> // Main class> class> GFG {> >// Main driver method> >public> static> void> main(String args[])> >{> >// Initialization of a TreeMap> >// using Generics> >TreeMap tm> >=>new> TreeMap();> >// Inserting the elements> >// using put() method> >tm.put(>3>,>'Geeks'>);> >tm.put(>2>,>'For'>);> >tm.put(>1>,>'Geeks'>);> >// For-each loop for traversal over Map> >// via entrySet() Method> >for> (Map.Entry mapElement : tm.entrySet()) {> >int> key = (>int>)mapElement.getKey();> >// Finding the value> >String value = (String)mapElement.getValue();> >// Printing the key and value> >System.out.println(key +>' : '> + value);> >}> >}> }> |
>
>Wyjście
1 : Geeks 2 : For 3 : Geeks>
Zalety TreeMap:
- Porządek sortowania: TreeMap zapewnia posortowaną kolejność swoich elementów w oparciu o naturalną kolejność kluczy lub niestandardowy komparator przekazany konstruktorowi. Dzięki temu jest przydatny w sytuacjach, gdy trzeba pobrać elementy w określonej kolejności.
- Przewidywalna kolejność iteracji: Ponieważ elementy w TreeMap są przechowywane w posortowanej kolejności, możesz przewidzieć kolejność, w jakiej zostaną zwrócone podczas iteracji, co ułatwia pisanie algorytmów przetwarzających elementy w określonej kolejności.
- Wydajność wyszukiwania: TreeMap zapewnia wydajną implementację interfejsu Map, umożliwiając pobieranie elementów w czasie logarytmicznym, co czyni go użytecznym w algorytmach wyszukiwania, w których konieczne jest szybkie pobieranie elementów.
- Samobalansowanie: TreeMap jest zaimplementowany przy użyciu czerwono-czarnego drzewa, które jest rodzajem samobalansującego drzewa wyszukiwania binarnego. Zapewnia to wydajną wydajność dodawania, usuwania i pobierania elementów, a także utrzymywania posortowanej kolejności elementów.
Wady TreeMap:
- Powolne wstawianie elementów: Wstawianie elementów do TreeMap może być wolniejsze niż wstawianie elementów do zwykłej mapy, ponieważ TreeMap musi zachować posortowaną kolejność swoich elementów.
- Ograniczenie dotyczące klucza: klucze w TreeMap muszą implementować interfejs java.lang.Comparable lub należy udostępnić niestandardowy komparator. Może to stanowić ograniczenie, jeśli konieczne jest użycie kluczy niestandardowych, które nie implementują tego interfejsu.
Leksykony:
Kolekcje Java autorstwa Maurice'a Naftalina i Philipa Wadlera. Ta książka zawiera kompleksowy przegląd frameworku Java Collections, w tym TreeMap.
Java w pigułce Davida Flanagana. Książka ta zawiera krótkie omówienie podstawowych funkcji języka Java, w tym TreeMap.
Generics and Collections w języku Java autorstwa Maurice'a Naftalina i Philipa Wadlera. Ta książka zawiera obszerny przewodnik po generykach i kolekcjach w Javie, w tym TreeMap.