Toteuttamiseen käytetään Javan TreeMapia Karttakäyttöliittymä ja NavigableMap sekä AbstractMap-luokka. Kartta on lajiteltu avainten luonnollisen järjestyksen mukaan tai a Vertailija tarjotaan kartan luomishetkellä riippuen siitä, mitä rakentajaa käytetään. Tämä osoittautuu tehokkaaksi tavaksi lajitella ja tallentaa avainarvo-pareja. Puukartan ylläpitämän tallennusjärjestyksen on oltava yhdenmukainen yhtäläisten kanssa, kuten minkä tahansa muun lajitellun kartan kanssa, riippumatta eksplisiittisistä vertailijoista. Puukartan toteutus ei ole synkronoitu siinä mielessä, että jos karttaan päästään useiden säikeiden kautta, samanaikaisesti ja ainakin yksi säikeistä muokkaa karttaa rakenteellisesti, se on synkronoitava ulkoisesti.
Javan TreeMap on konkreettinen toteutus java.util.SortedMap-käyttöliittymästä. Se tarjoaa tilatun kokoelman avain-arvo-pareja, joissa avaimet on järjestetty niiden luonnollisen järjestyksen tai rakentajalle välitetyn mukautetun vertailijan perusteella.
TreeMap on toteutettu käyttämällä punaista mustaa puuta, joka on eräänlainen itsetasapainottava binäärihakupuu. Tämä tarjoaa tehokkaan suorituskyvyn yleisissä toiminnoissa, kuten elementtien lisäämisessä, poistamisessa ja noutamisessa, keskimääräisellä aikamonimutkaisuudella O(log n).
Tässä on esimerkki TreeMap-luokan käytöstä:
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));> >}> >}> }> |
>
>Lähtö
Value of A: 1 Key: A, Value: 1 Key: C, Value: 3>
TreeMapin ominaisuudet
Jotkut puukartan tärkeät ominaisuudet ovat seuraavat:
- Tämä luokka on jäsen Java-kokoelmat puitteet.
- Luokka toteuttaa Karttarajapinnat mukaan lukien NavigableMap , SortedMap ja laajentaa AbstractMap-luokkaa.
- TreeMap Javassa ei salli nolla-avaimia (kuten Map), joten NullPointerException heitetään. Eri avaimiin voidaan kuitenkin liittää useita nolla-arvoja.
- Tämän luokan ja sen näkymien menetelmien palauttamat merkintäparit edustavat tilannekuvia kartoituksista niiden tuotantohetkellä. Ne eivät tue Entry.setValue-menetelmää.
Siirrytään nyt eteenpäin ja keskustellaan synkronoidusta TreeMapista. TreeMapin toteutusta ei synkronoida. Tämä tarkoittaa, että jos useat säikeet käyttävät puujoukkoa samanaikaisesti ja ainakin yksi säikeistä muokkaa joukkoa, se on synkronoitava ulkoisesti. Tämä saavutetaan yleensä Collections.synchronizedSortedMap-menetelmällä. Tämä on parasta tehdä luontihetkellä, jotta vältetään vahingossa tapahtuva synkronoimaton pääsy laitteeseen. Tämä voidaan tehdä seuraavasti:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));>
Geeks, nyt sinun täytyy ihmetellä, kuinka TreeMap toimii sisäisesti?
TreeMapin menetelmät, kun ne hankkivat avainjoukkoja ja arvoja, palauttavat Iteraattorin, joka on luonteeltaan nopea. Siten kaikki samanaikaiset muutokset aiheuttavat ConcurrentModificationExceptionin. TreeMap perustuu punamustapuun tietorakenteeseen.
Jokaisella puun solmulla on:
- 3 muuttujaa ( K avain = avain, V arvo = arvo, boolen väri = väri )
- 3 lähdettä ( Entry vasen = vasen, Entry right = oikea, Entry parent = vanhempi )
Rakentajat TreeMapissa
TreeMap-kartan luomiseksi meidän on luotava TreeMap-luokan objekti. TreeMap-luokka koostuu erilaisista konstruktoreista, jotka mahdollistavat TreeMapin mahdollisen luomisen. Tässä luokassa saatavilla olevat rakentajat:
- TreeMap()
- TreeMap (Comparator Comp)
- TreeMap (kartta M)
- TreeMap (SortedMap sm)
Keskustellaan niistä erikseen jokaisen rakentajan toteuttamisen ohella seuraavasti:
Rakentaja 1: TreeMap()
Tätä konstruktoria käytetään rakentamaan tyhjä puukartta, joka lajitellaan käyttämällä avainten luonnollista järjestystä.
Esimerkki
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();> >}> }> |
>
>Lähtö
TreeMap using TreeMap() constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Rakentaja 2: TreeMap (Comparator Comp)
Tätä konstruktoria käytetään tyhjän TreeMap-objektin rakentamiseen, jonka elementit tarvitsevat ulkoisen lajittelujärjestyksen määrityksen.
Esimerkki
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();> >}> }> |
>
>Lähtö
TreeMap using TreeMap(Comparator) constructor: TreeMap: {111 bbbb london=2, 121 cccc jaipur=1, 131 aaaa nyc=3}> Rakentaja 3: TreeMap (kartta M)
Tätä konstruktoria käytetään alustamaan TreeMap tietyn kartan M merkinnöillä, jotka lajitellaan käyttämällä avainten luonnollista järjestystä.
Esimerkki
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();> >}> }> |
>
>Lähtö
TreeMap using TreeMap(Map) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> Rakentaja 4: TreeMap (SortedMap sm)
Tätä rakentajaa käytetään TreeMapin alustamiseen tietyn lajiteltujen kartan merkinnöillä, jotka tallennetaan samassa järjestyksessä kuin annettu lajiteltu kartta.
Esimerkki
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();> >}> }> |
>
>Lähtö
TreeMap using TreeMap(SortedMap) constructor: TreeMap: {10=Geeks, 15=4, 20=Geeks, 25=Welcomes, 30=You}> TreeMap-luokan menetelmät
| Menetelmä | Toimenpide suoritettu |
|---|---|
| asia selvä() | Menetelmä poistaa kaikki kartoitukset tästä TreeMapista ja tyhjentää kartan. |
| klooni() | Menetelmä palauttaa matalan kopion tästä TreeMapista. |
| sisältääKey(Objektiavain) | Palauttaa tosi, jos tämä kartta sisältää määritetyn avaimen määrityksen. |
| sisältääValue(objektin arvo) | Palauttaa tosi, jos tämä kartta yhdistää yhden tai useamman avaimen määritettyyn arvoon. |
| entrySet() | Palauttaa sarjanäkymän tämän kartan sisältämistä kartoituksista. |
| firstKey() | Palauttaa ensimmäisen (alimman) avaimen tällä hetkellä tässä lajiteltussa kartassa. |
| get (Objektiavain) | Palauttaa arvon, johon tämä kartta yhdistää määritetyn avaimen. |
| headMap (objektin avaimen_arvo) | Menetelmä palauttaa kartan osan näkymän tarkasti alle parametrin avainarvo. |
| keySet() | Metodi palauttaa puukartan sisältämien avainten joukkonäkymän. |
| lastKey() | Palauttaa viimeisen (korkeimman) avaimen tällä hetkellä tässä lajiteltussa kartassa. |
| put(Objektiavain, Objektin arvo) | Menetelmää käytetään kartoituksen lisäämiseen karttaan. |
| laita kaikki (karttakartta) | Kopioi kaikki määritetyn kartan kartoitukset tähän karttaan. |
| poista (objektiavain) | Poistaa tämän avaimen yhdistämisen tästä TreeMapista, jos sellainen on. |
| koko() | Palauttaa tämän kartan avainarvokartoitusten määrän. |
| alikartta((K aloitusavain, K endKey) | Metodi palauttaa tämän kartan osan, jonka avaimet vaihtelevat aloitusavaimesta poissulkevaan endKeyyn. |
| arvot() | Palauttaa kokoelmanäkymän tämän kartan sisältämistä arvoista. |
Toteutus: Seuraavat alla olevat ohjelmat osoittavat paremmin TreeMapin luomisen, lisäämisen ja läpikäymisen.
Kuva:
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();> >}> }> |
>
>Lähtö
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> Erilaisten toimintojen suorittaminen TreeMapissa
Genericsin käyttöönoton jälkeen Java 1.5:ssä on mahdollista rajoittaa TreeMapiin tallennettavien objektien tyyppiä. Katsotaanpa nyt, kuinka tehdä muutama usein käytetty toiminto TreeMapissa.
Operaatio 1: Elementtien lisääminen
Elementin lisäämiseksi TreeMapiin voimme käyttää put()-metodia . Lisäysjärjestys ei kuitenkaan säily TreeMapissa. Sisäisesti jokaisen elementin avaimia verrataan ja lajitellaan nousevaan järjestykseen.
Esimerkki
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);> >}> }> |
>
>Lähtö
{1=Geeks, 2=For, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Toiminto 2: Elementtien vaihtaminen
Kun elementit on lisätty, jos haluamme muuttaa elementtiä, se voidaan tehdä lisäämällä elementti uudelleen put()-metodilla . Koska puukartan elementit indeksoidaan avaimilla, avaimen arvoa voidaan muuttaa yksinkertaisesti lisäämällä päivitetty arvo avaimelle, jota haluamme muuttaa.
Esimerkki
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);> >}> }> |
>
>Lähtö
{1=Geeks, 2=Geeks, 3=Geeks} {1=Geeks, 2=For, 3=Geeks}> Operaatio 3: Elementin poistaminen
Elementin poistamiseksi TreeMapista voimme käyttää remove()-menetelmää . Tämä menetelmä ottaa avaimen arvon ja poistaa avaimen kartoituksen tästä puukartasta, jos se on kartassa.
Esimerkki
Java
matriisiluettelo java
// 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);> >}> }> |
>
>Lähtö
{1=Geeks, 2=Geeks, 3=Geeks, 4=For} {1=Geeks, 2=Geeks, 3=Geeks}> Operaatio 4: Iterointi TreeMapin kautta
On olemassa useita tapoja iteroida kartan läpi. Tunnetuin tapa on käyttää a jokaiselle silmukalle ja hanki avaimet. Avaimen arvo löytyy käyttämällä getValue() -menetelmä .
Esimerkki
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);> >}> >}> }> |
>
>Lähtö
1 : Geeks 2 : For 3 : Geeks>
TreeMapin edut:
- Lajiteltu järjestys: TreeMap tarjoaa elementtien lajitellun järjestyksen, joka perustuu sen avainten luonnolliseen järjestykseen tai rakentajalle välitettyyn mukautettuun vertailuun. Tämä tekee siitä hyödyllisen tilanteissa, joissa elementtejä on haettava tietyssä järjestyksessä.
- Ennustettava iterointijärjestys: Koska TreeMapin elementit on tallennettu lajiteltuun järjestykseen, voit ennustaa järjestyksen, jossa ne palautetaan iteroinnin aikana, mikä helpottaa elementit tietyssä järjestyksessä käsittelevien algoritmien kirjoittamista.
- Haun suorituskyky: TreeMap tarjoaa tehokkaan Map-käyttöliittymän toteutuksen, jonka avulla voit noutaa elementtejä logaritmisajassa, mikä tekee siitä hyödyllisen hakualgoritmeissa, joissa elementtejä on haettava nopeasti.
- Itsetasapainottava: TreeMap on toteutettu käyttämällä punaista mustaa puuta, joka on eräänlainen itsetasapainottava binäärihakupuu. Tämä tarjoaa tehokkaan suorituskyvyn elementtien lisäämiseen, poistamiseen ja hakemiseen sekä elementtien järjestyksen ylläpitämiseen.
TreeMapin haitat:
- Hidas elementtien lisääminen: Elementtien lisääminen TreeMapiin voi olla hitaampaa kuin elementtien lisääminen tavalliseen karttaan, koska TreeMapin on säilytettävä elementtiensä järjestys.
- Avainrajoitus: TreeMapin avainten on otettava käyttöön java.lang.Comparable-käyttöliittymä tai mukautettu Comparator on tarjottava. Tämä voi olla rajoitus, jos sinun on käytettävä mukautettuja avaimia, jotka eivät toteuta tätä käyttöliittymää.
Lähdekirjat:
Maurice Naftalinin ja Philip Wadlerin Java-kokoelmat. Tämä kirja tarjoaa kattavan yleiskatsauksen Java Collections -kehyksestä, mukaan lukien TreeMap.
Java pähkinänkuoressa David Flanagan. Tämä kirja tarjoaa nopean viittauksen Javan ydinominaisuuksiin, mukaan lukien TreeMap.
Maurice Naftalinin ja Philip Wadlerin Java Generics and Collections. Tämä kirja tarjoaa kattavan oppaan geneerisiin lääkkeisiin ja kokoelmiin Javassa, mukaan lukien TreeMap.