K implementaci se používá TreeMap v Javě Mapové rozhraní a NavigableMap spolu s třídou AbstractMap. Mapa je řazena podle přirozeného řazení svých klíčů nebo podle a Komparátor poskytované v době vytváření mapy v závislosti na použitém konstruktoru. To se ukazuje jako efektivní způsob třídění a ukládání párů klíč-hodnota. Pořadí ukládání udržované stromovou mapou musí být konzistentní s rovností stejně jako jakákoli jiná seřazená mapa, bez ohledu na explicitní komparátory. Implementace stromové mapy není synchronizována v tom smyslu, že pokud k mapě přistupuje více vláken, současně a alespoň jedno z vláken strukturálně upravuje mapu, musí být synchronizována externě.
TreeMap v Javě je konkrétní implementace rozhraní java.util.SortedMap. Poskytuje uspořádanou kolekci párů klíč-hodnota, kde jsou klíče seřazeny na základě jejich přirozeného pořadí nebo vlastního komparátoru předaného konstruktoru.
TreeMap je implementována pomocí Red-Black stromu, což je typ samovyvažujícího binárního vyhledávacího stromu. To poskytuje efektivní výkon pro běžné operace, jako je přidávání, odebírání a načítání prvků, s průměrnou časovou složitostí O(log n).
Zde je příklad, jak používat třídu TreeMap:
Jáva
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));> >}> >}> }> |
>
>Výstup
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
Vlastnosti stromové mapy
Některé důležité vlastnosti stromové mapy jsou následující:
- Tato třída je členem Kolekce Java Rámec.
- Třída implementuje Mapová rozhraní včetně NavigableMap , SortedMap a rozšiřuje třídu AbstractMap.
- TreeMap v Javě neumožňuje nulové klíče (jako Map), a proto je vyvolána výjimka NullPointerException. K různým klíčům však může být přiřazeno více hodnot null.
- Vstupní páry vrácené metodami v této třídě a její pohledy představují snímky mapování v době, kdy byly vytvořeny. Nepodporují metodu Entry.setValue.
Nyní pojďme kupředu a pojďme diskutovat o synchronizované stromové mapě. Implementace stromové mapy není synchronizována. To znamená, že pokud k sadě stromu přistupuje více vláken současně a alespoň jedno z nich sadu upravuje, musí být synchronizována externě. Toho se obvykle dosáhne pomocí metody Collections.synchronizedSortedMap. To se nejlépe provádí v době vytvoření, aby se zabránilo náhodnému nesynchronizovanému přístupu k sadě. To lze provést takto:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geekové, teď se musíte divit, jak funguje TreeMap interně?
Metody ve stromové mapě při získávání sady klíčů a hodnot vracejí Iterátor, který je svou povahou rychlý. Jakákoli souběžná úprava tedy vyvolá ConcurrentModificationException . Stromová mapa je založena na červeno-černé stromové struktuře dat.
Každý uzel ve stromu má:
- 3 proměnné ( Klíč K = klíč, hodnota V = hodnota, logická barva = barva )
- 3 reference ( Vstup vlevo = Levý, Vstup vpravo = Pravý, Vstup rodič = Rodič )
Konstruktoři v TreeMap
Abychom mohli vytvořit TreeMap, musíme vytvořit objekt třídy TreeMap. Třída TreeMap se skládá z různých konstruktorů, které umožňují možné vytvoření TreeMap. V této třídě jsou k dispozici následující konstruktory:
- TreeMap()
- TreeMap (Comparator comp)
- Stromová mapa (Mapa M)
- Stromová mapa (SortedMap sm)
Proberme je jednotlivě spolu s implementací každého konstruktoru takto:
Konstruktor 1: TreeMap()
Tento konstruktor se používá k vytvoření prázdné stromové mapy, která bude setříděna pomocí přirozeného pořadí svých klíčů.
Příklad
Jáva
// 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();> >}> }> |
>
>Výstup
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktor 2: TreeMap (Comparator comp)
Tento konstruktor se používá k vytvoření prázdného objektu TreeMap, ve kterém budou prvky potřebovat externí specifikaci pořadí řazení.
Příklad
Jáva
// 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();> >}> }> |
>
>Výstup
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Konstruktor 3: Stromová mapa (Mapa M)
Tento konstruktor se používá k inicializaci TreeMap se záznamy z dané mapy M, které budou seřazeny podle přirozeného pořadí kláves.
Příklad
Jáva
// 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();> >}> }> |
>
>Výstup
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Konstruktor 4: Stromová mapa (SortedMap sm)
Tento konstruktor se používá k inicializaci TreeMap se záznamy z dané seřazené mapy, které budou uloženy ve stejném pořadí jako daná seřazená mapa.
Příklad
Jáva
// 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();> >}> }> |
>
>Výstup
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metody ve třídě TreeMap
| Metoda | Akce provedena |
|---|---|
| Průhledná() | Metoda odstraní všechna mapování z této stromové mapy a vymaže mapu. |
| klon() | Metoda vrací mělkou kopii této stromové mapy. |
| obsahuje klíč (objektový klíč) | Vrátí hodnotu true, pokud tato mapa obsahuje mapování pro zadaný klíč. |
| obsahujeValue(hodnota objektu) | Vrátí hodnotu true, pokud tato mapa mapuje jeden nebo více klíčů na zadanou hodnotu. |
| entrySet() | Vrátí nastavený pohled na mapování obsažená v této mapě. |
| firstKey() | Vrátí první (nejnižší) klíč aktuálně v této tříděné mapě. |
| get (klíč objektu) | Vrátí hodnotu, na kterou tato mapa mapuje zadaný klíč. |
| headMap (hodnota klíče objektu) | Metoda vrací pohled na část mapy striktně menší než parametr key_value. |
| keySet() | Metoda vrací zobrazení Set klíčů obsažených ve stromové mapě. |
| lastKey() | Vrátí poslední (nejvyšší) klíč aktuálně v této tříděné mapě. |
| put (klíč objektu, hodnota objektu) | Metoda se používá k vložení mapování do mapy. |
| putAll (mapa mapy) | Zkopíruje všechna mapování ze zadané mapy do této mapy. |
| odstranit (klíč objektu) | Odstraní mapování tohoto klíče z této stromové mapy, pokud je přítomno. |
| velikost() | Vrátí počet mapování párů klíč–hodnota v této mapě. |
| subMap((K startKey, K endKey) | Metoda vrací část této mapy, jejíž klíče jsou v rozsahu od startKey včetně, do endKey, exkluzivní. |
| hodnoty() | Vrátí zobrazení kolekce hodnot obsažených v této mapě. |
Implementace: Následující programy níže lépe ukáží, jak vytvořit, vložit a procházet stromovou mapu.
Ilustrace:
Jáva
// 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();> >}> }> |
>
>Výstup
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> Provádění různých operací na TreeMap
Po zavedení Generics v Javě 1.5 je možné omezit typ objektu, který lze uložit do TreeMap. Nyní se podívejme, jak provést několik často používaných operací na stromové mapě.
Operace 1: Přidávání prvků
Abychom přidali prvek do TreeMap, můžeme použít metodu put() . Pořadí vložení však není ve stromové mapě zachováno. Interně jsou klíče pro každý prvek porovnány a seřazeny ve vzestupném pořadí.
Příklad
Jáva
// 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);> >}> }> |
>
>Výstup
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operace 2: Výměna prvků
Po přidání prvků, pokud chceme prvek změnit, to lze provést opětovným přidáním prvku pomocí metody put() . Vzhledem k tomu, že prvky ve stromové mapě jsou indexovány pomocí klíčů, hodnotu klíče lze změnit jednoduchým vložením aktualizované hodnoty klíče, který chceme změnit.
Příklad
Jáva
// 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);> >}> }> |
>
>Výstup
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operace 3: Odebírání prvku
Abychom odstranili prvek ze stromové mapy, můžeme použít metodu remove() . Tato metoda převezme hodnotu klíče a odstraní mapování pro klíč z této stromové mapy, pokud je v mapě přítomen.
Příklad
Jáva
css pozadí
// 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);> >}> }> |
>
>Výstup
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operace 4: Iterace přes TreeMap
Mapu lze iterovat několika způsoby. Nejznámějším způsobem je použití a pro každou smyčku a získat klíče. Hodnota klíče se zjistí pomocí metoda getValue(). .
Příklad
Jáva
// 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);> >}> >}> }> |
>
>Výstup
1 : Geeks 2 : For 3 : Geeks>
Výhody TreeMap:
- Seřazené pořadí: Stromová mapa poskytuje seřazené pořadí svých prvků na základě přirozeného pořadí svých klíčů nebo vlastního komparátoru předaného konstruktoru. To je užitečné v situacích, kdy potřebujete načíst prvky v určitém pořadí.
- Předvídatelné pořadí iterací: Protože jsou prvky ve stromové mapě uloženy v seřazeném pořadí, můžete předvídat pořadí, ve kterém budou vráceny během iterace, což usnadňuje psaní algoritmů, které zpracovávají prvky v určitém pořadí.
- Výkon vyhledávání: TreeMap poskytuje efektivní implementaci rozhraní mapy, která vám umožňuje získávat prvky v logaritmickém čase, což je užitečné ve vyhledávacích algoritmech, kde potřebujete prvky rychle načíst.
- Self-balancing: TreeMap je implementován pomocí Red-Black stromu, což je typ samovyvažujícího binárního vyhledávacího stromu. To poskytuje efektivní výkon pro přidávání, odebírání a načítání prvků a také udržování setříděného pořadí prvků.
Nevýhody TreeMap:
- Pomalé vkládání prvků: Vkládání prvků do stromové mapy může být pomalejší než vkládání prvků do běžné mapy, protože stromová mapa musí udržovat seřazené pořadí svých prvků.
- Omezení klíče: Klíče ve stromové mapě musí implementovat rozhraní java.lang.Comparable nebo musí být poskytnut vlastní komparátor. To může být omezení, pokud potřebujete použít vlastní klíče, které neimplementují toto rozhraní.
Referenční knihy:
Java Collections od Maurice Naftalina a Philipa Wadlera. Tato kniha poskytuje komplexní přehled o frameworku Java Collections, včetně TreeMap.
Java v kostce od Davida Flanagana. Tato kniha poskytuje rychlý odkaz na základní funkce Javy, včetně stromové mapy.
Java Generics and Collections od Maurice Naftalina a Philipa Wadlera. Tato kniha poskytuje komplexního průvodce generikami a kolekcemi v Javě, včetně stromové mapy.