Įdiegimui naudojamas „TreeMap“ Java programoje Žemėlapio sąsaja ir NavigableMap kartu su AbstractMap klase. Žemėlapis rūšiuojamas pagal natūralią jo klavišų tvarką arba pagal a Palyginimas pateikiama žemėlapio kūrimo metu, priklausomai nuo to, kuris konstruktorius naudojamas. Tai yra veiksmingas būdas rūšiuoti ir saugoti raktų ir reikšmių poras. Medžio schemoje palaikoma saugojimo tvarka turi atitikti lygiaverčius lygius, kaip ir bet kuris kitas surūšiuotas žemėlapis, neatsižvelgiant į aiškius lyginamuosius elementus. Medžio žemėlapio įgyvendinimas nėra sinchronizuotas ta prasme, kad jei žemėlapį pasiekia kelios gijos, vienu metu ir bent viena iš gijų struktūriškai modifikuoja žemėlapį, jis turi būti sinchronizuotas išoriškai.
„TreeMap“ programoje „Java“ yra konkretus java.util.SortedMap sąsajos įgyvendinimas. Jame pateikiamas užsakytas raktų ir reikšmių porų rinkinys, kuriame raktai užsakomi pagal jų natūralią tvarką arba pasirinktinį palyginiklį, perduodamą konstruktoriui.
„TreeMap“ yra įdiegtas naudojant raudonai juodą medį, kuris yra savaime balansuojančio dvejetainio paieškos medžio tipas. Tai užtikrina efektyvų įprastų operacijų, tokių kaip elementų pridėjimas, pašalinimas ir gavimas, našumą, o vidutinis laiko sudėtingumas yra O(log n).
Štai pavyzdys, kaip naudoti TreeMap klasę:
Java
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));> >}> >}> }> |
>
>Išvestis
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
„TreeMap“ ypatybės
Kai kurios svarbios medžio žemėlapio ypatybės yra šios:
- Ši klasė priklauso Java kolekcijos Sistema.
- Klasė įgyvendina Žemėlapio sąsajos įskaitant NavigableMap , SortedMap ir išplečia AbstractMap klasę.
- „TreeMap“ programoje „Java“ neleidžia naudoti nulinių raktų (pvz., „Map“), todėl išmetama NullPointerException. Tačiau kelios nulinės reikšmės gali būti susietos su skirtingais raktais.
- Įrašų poros, grąžintos naudojant šios klasės metodus, ir jos rodiniai atspindi atvaizdų momentines nuotraukas jų sudarymo metu. Jie nepalaiko Entry.setValue metodo.
Dabar judėkime į priekį ir aptarkime sinchronizuotą medžio žemėlapį. „TreeMap“ diegimas nėra sinchronizuotas. Tai reiškia, kad jei kelios gijos vienu metu pasiekia medžio rinkinį ir bent viena iš gijų pakeičia rinkinį, ji turi būti sinchronizuojama išoriškai. Paprastai tai atliekama naudojant Collections.synchronizedSortedMap metodą. Tai geriausia padaryti kuriant, kad būtų išvengta atsitiktinės nesinchronizuotos prieigos prie rinkinio. Tai galima padaryti taip:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeks, dabar jums tikriausiai įdomu, kaip „TreeMap“ veikia viduje?
„TreeMap“ metodai, gaudami raktų rinkinį ir vertes, grąžina iteratorių, kuris iš prigimties yra greitas. Taigi, bet kokia vienu metu atliekama modifikacija išmes ConcurrentModificationException . „TreeMap“ yra pagrįstas raudonai juodo medžio duomenų struktūra.
Kiekvienas medžio mazgas turi:
- 3 kintamieji ( K raktas = raktas, V reikšmė = reikšmė, loginė spalva = spalva )
- 3 nuorodos ( Kairysis įrašas = kairysis, dešinysis įėjimas = dešinysis, pirminis įrašas = tėvas )
„TreeMap“ konstruktoriai
Norėdami sukurti TreeMap, turime sukurti TreeMap klasės objektą. TreeMap klasė susideda iš įvairių konstruktorių, kurie leidžia sukurti TreeMap. Šioje klasėje galimi šie konstruktoriai:
- TreeMap ()
- „TreeMap“ (komparatorius)
- Medžio žemėlapis (M žemėlapis)
- Medžio žemėlapis (SortedMap sm)
Aptarkime juos atskirai kartu su kiekvieno konstruktoriaus įgyvendinimu taip:
1 konstruktorius: TreeMap ()
Šis konstruktorius naudojamas kuriant tuščią medžio žemėlapį, kuris bus rūšiuojamas naudojant natūralią jo klavišų tvarką.
Pavyzdys
Java
// 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();> >}> }> |
>
>Išvestis
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> 2 konstruktorius: „TreeMap“ (komparatorius)
Šis konstruktorius naudojamas tuščiam TreeMap objektui sukurti, kurio elementams reikės išorinės rūšiavimo tvarkos specifikacijos.
Pavyzdys
Java
// 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();> >}> }> |
>
>Išvestis
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> 3 konstruktorius: Medžio žemėlapis (M žemėlapis)
Šis konstruktorius naudojamas TreeMap inicijuoti su nurodyto žemėlapio M įrašais, kurie bus rūšiuojami naudojant natūralią klavišų tvarką.
Pavyzdys
Java
// 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();> >}> }> |
>
>Išvestis
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> 4 konstruktorius: Medžio žemėlapis (SortedMap sm)
Šis konstruktorius naudojamas inicijuoti TreeMap su įrašais iš nurodyto surūšiuoto žemėlapio, kuris bus saugomas ta pačia tvarka kaip ir pateiktas surūšiuotas žemėlapis.
Pavyzdys
Java
// 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();> >}> }> |
>
>Išvestis
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Metodai TreeMap klasėje
| Metodas | Veiksmas atliktas |
|---|---|
| aišku () | Šis metodas pašalina visus žemėlapius iš šio TreeMap ir išvalo žemėlapį. |
| klonas () | Metodas grąžina negilią šio medžio žemėlapio kopiją. |
| includeKey (objekto raktas) | Grąžina true, jei šiame žemėlapyje yra nurodyto rakto atvaizdas. |
| includeValue (objekto vertė) | Grąžina true, jei šis žemėlapis susieja vieną ar daugiau raktų su nurodyta verte. |
| įrašasSet() | Grąžina rinkinį šiame žemėlapyje esančių atvaizdų rodinį. |
| pirmasis raktas () | Grąžina pirmąjį (žemiausią) raktą šiuo metu šiame surūšiuotame žemėlapyje. |
| gauti (objekto raktas) | Grąžina reikšmę, su kuria šis žemėlapis susieja nurodytą raktą. |
| headMap (objekto rakto_vertė) | Metodas grąžina žemėlapio dalies vaizdą, kuris yra griežtai mažesnis nei parametras rakto_vertė. |
| keySet() | Metodas grąžina medžio schemoje esančių raktų rinkinio rodinį. |
| paskutinis raktas () | Grąžina paskutinį (aukščiausią) raktą šiuo metu šiame surūšiuotame žemėlapyje. |
| įdėti (objekto raktas, objekto vertė) | Metodas naudojamas žemėlapiui įterpti į žemėlapį. |
| įdėti viską (žemėlapio žemėlapis) | Nukopijuoja visus žemėlapius iš nurodyto žemėlapio į šį žemėlapį. |
| pašalinti (objekto raktas) | Pašalina šio rakto susiejimą iš šio medžio žemėlapio, jei yra. |
| dydis () | Grąžina šiame žemėlapyje esančių raktų ir reikšmių susiejimo skaičių. |
| subžemėlapis ((K startKey, K endKey) | Metodas grąžina šio žemėlapio dalį, kurios raktai svyruoja nuo startKey imtinai iki endKey, išskirtiniai. |
| reikšmės () | Grąžina šiame žemėlapyje esančių verčių rinkinį. |
Įgyvendinimas: Toliau pateiktos programos geriau parodys, kaip sukurti, įterpti ir pereiti per TreeMap.
Iliustracija:
Java
// 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();> >}> }> |
>
>Išvestis
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> Įvairių operacijų atlikimas „TreeMap“.
Įdiegus Generics Java 1.5, galima apriboti objektų, kurie gali būti saugomi TreeMap, tipą. Dabar pažiūrėkime, kaip atlikti keletą dažnai naudojamų „TreeMap“ operacijų.
1 operacija: Elementų pridėjimas
Norėdami pridėti elementą prie TreeMap, galime naudoti put() metodą . Tačiau įterpimo tvarka „TreeMap“ neišsaugoma. Viduje kiekvieno elemento klavišai lyginami ir rūšiuojami didėjančia tvarka.
Pavyzdys
Java
// 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);> >}> }> |
>
>Išvestis
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> 2 veiksmas: elementų keitimas
Pridėjus elementus, jei norime elementą pakeisti, tai galima padaryti dar kartą pridedant elementą put() metodu . Kadangi medžio schemoje esantys elementai yra indeksuojami naudojant raktus, rakto reikšmę galima pakeisti tiesiog įterpiant atnaujintą rakto, kurį norime pakeisti, reikšmę.
Pavyzdys
Java
// 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);> >}> }> |
>
>Išvestis
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> 3 operacija: Elemento pašalinimas
Norėdami pašalinti elementą iš „TreeMap“, galime naudoti pašalinimo () metodą. Šis metodas paima rakto reikšmę ir pašalina rakto atvaizdavimą iš šio medžio žemėlapio, jei jis yra žemėlapyje.
Pavyzdys
Java
Java inicijavimo masyvas
// 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);> >}> }> |
>
>Išvestis
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> 4 operacija: Iteravimas per TreeMap
Yra keletas būdų, kaip kartoti žemėlapį. Garsiausias būdas yra naudoti a už kiekvieną kilpą ir pasiimk raktus. Rakto reikšmė randama naudojant getValue() metodas .
Pavyzdys
Java
// 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);> >}> >}> }> |
>
>Išvestis
1 : Geeks 2 : For 3 : Geeks>
„TreeMap“ pranašumai:
- Rūšiavimo tvarka: „TreeMap“ pateikia elementų rūšiavimo tvarką, pagrįstą natūralia raktų tvarka arba pasirinktiniu lygintuvu, perduodamu konstruktoriui. Tai naudinga tais atvejais, kai reikia gauti elementus tam tikra tvarka.
- Nuspėjama iteracijos tvarka: kadangi „TreeMap“ elementai saugomi surūšiuota tvarka, galite numatyti, kokia tvarka jie bus grąžinti iteracijos metu, todėl lengviau rašyti algoritmus, apdorojančius elementus tam tikra tvarka.
- Paieškos našumas: „TreeMap“ suteikia efektyvų žemėlapio sąsajos įgyvendinimą, leidžiantį nuskaityti elementus logaritminiu laiku, todėl jis naudingas paieškos algoritmuose, kur reikia greitai gauti elementus.
- Savarankiškas balansavimas: „TreeMap“ yra įdiegtas naudojant raudonai juodą medį, kuris yra savaime balansuojančio dvejetainio paieškos medžio tipas. Tai užtikrina efektyvų elementų pridėjimo, pašalinimo ir gavimo našumą, taip pat elementų rūšiavimo tvarkos palaikymą.
„TreeMap“ trūkumai:
- Lėtas elementų įterpimas: elementų įterpimas į „TreeMap“ gali būti lėtesnis nei elementų įterpimas į įprastą žemėlapį, nes „TreeMap“ turi išlaikyti elementų rūšiavimo tvarką.
- Raktų apribojimas: „TreeMap“ raktai turi įdiegti java.lang.Comparable sąsają arba turi būti pateikta tinkinta palyginimo priemonė. Tai gali būti apribojimas, jei reikia naudoti pasirinktinius raktus, kurie neįgyvendina šios sąsajos.
Žinynai:
Maurice'o Naftalino ir Philipo Wadlerio „Java“ kolekcijos. Šioje knygoje pateikiama išsami Java kolekcijų sistemos, įskaitant TreeMap, apžvalga.
Java trumpai, David Flanagan. Šioje knygoje pateikiama trumpa informacija apie pagrindines „Java“ funkcijas, įskaitant „TreeMap“.
Maurice'o Naftalino ir Philipo Wadlerio „Java Generics and Collections“. Šioje knygoje pateikiamas išsamus „Java“ generinių vaistų ir kolekcijų vadovas, įskaitant „TreeMap“.