Java TreeMap vs HashMap

1. Introduktion

I denne artikel skal vi sammenligne to Kort implementeringer: TreeMap og HashMap.

Begge implementeringer udgør en integreret del af Java Samlinger Framework og gem data som nøgle-værdi par.

2. Forskelle

2.1. Implementering

Vi taler først om HashMap som er en hashtable-baseret implementering. Det udvider AbstraktKort klasse og implementerer Kort interface. EN HashMap arbejder på princippet om hashing.

Det her Kort implementering fungerer normalt som en bucketed hash-bord, men når skovle bliver for store, bliver de omdannet til noder til TreeNodes, hver struktureret som dem i java.util.TreeMap.

Du kan finde mere på HashMap's interner i artiklen fokuserede på det.

På den anden side, TreeMap strækker sig AbstraktKort klasse og redskaber NavigableMap interface. EN TreeMap gemmer kortelementer i en Rød-sort træ, som er en Selvbalancering Binært søgetræ.

Og du kan også finde mere på TreeMap's interner i artiklen fokuserede på det her.

2.2. Bestille

HashMap giver ingen garanti for, hvordan elementerne er arrangeret i Kort.

Det betyder, vi kan ikke påtage os nogen ordre, mens vi gentager nøgler og værdier af en HashMap:

@Test offentligt ugyldigt nårInsertObjectsHashMap_thenRandomOrder () {Map hashmap = new HashMap (); hashmap.put (3, "TreeMap"); hashmap.put (2, "vs"); hashmap.put (1, "HashMap"); assertThat (hashmap.keySet (), indeholderInAnyOrder (1, 2, 3)); }

Emner i en TreeMap er sorteret efter deres naturlige rækkefølge.

Hvis TreeMap objekter kan ikke sorteres efter naturlig rækkefølge, så kan vi bruge en Komparator eller Sammenlignelig for at definere rækkefølgen, i hvilken elementerne er arrangeret inden for Kort:

@Test offentlig ugyldig nårInsertObjectsTreeMap_thenNaturalOrder () {Map treemap = new TreeMap (); treemap.put (3, "TreeMap"); treemap.put (2, "vs"); treemap.put (1, "HashMap"); assertThat (treemap.keySet (), indeholder (1, 2, 3)); }

2.3. Nul Værdier

HashMap tillader opbevaring højst en nulnøgle og mange nul værdier.

Lad os se et eksempel:

@Test offentligt ugyldigt nårInsertNullInHashMap_thenInsertsNull () {Map hashmap = new HashMap (); hashmap.put (null, null); assertNull (hashmap.get (null)); }

Imidlertid, TreeMap tillader ikke en nulnøgle men kan indeholde mange nul værdier.

EN nul nøgle er ikke tilladt, fordi sammenligne med() eller den sammenligne() metoden kaster en NullPointerException:

@Test (forventet = NullPointerException.class) offentlig ugyldig nårInsertNullInTreeMap_thenException () {Map treemap = new TreeMap (); treemap.put (null, "NullPointerException"); }

Hvis vi bruger en TreeMap med en brugerdefineret Komparator, så afhænger det af implementeringen af ​​sammenligningen() metode hvordan nul værdier bliver håndteret.

3. Præstationsanalyse

Ydeevne er den mest kritiske metrik, der hjælper os med at forstå egnetheden af ​​en datastruktur givet en brugssag.

I dette afsnit giver vi en omfattende analyse af ydeevnen for HashMap og TreeMap.

3.1. HashMap

HashMap, er en hashtable-baseret implementering, bruger internt en array-baseret datastruktur til at organisere dens elementer i henhold til hash-funktion.

HashMap giver forventet konstanttidspræstation O (1) til de fleste operationer som tilføje(), fjerne() og indeholder(). Derfor er det betydeligt hurtigere end en TreeMap.

Den gennemsnitlige tid til at søge efter et element under en rimelig antagelse i en hash-tabel er O (1). Men en forkert implementering af hash-funktion kan føre til en dårlig fordeling af værdier i spande, hvilket resulterer i:

  • Hukommelsesoverhead - mange spande forbliver ubrugte
  • Ydelsesnedbrydningjo højere antal kollisioner, jo lavere er ydeevnen

Før Java 8, Separat lænkning var den eneste foretrukne måde at håndtere kollisioner på. Det implementeres normalt ved hjælp af sammenkædede lister, dvs., hvis der er en kollision, eller to forskellige elementer har samme hash-værdi, skal du gemme begge elementerne på den samme linkede liste.

Derfor søger du efter et element i en HashMap, i værste fald kunne have taget så lang tid som at søge efter et element på en linket liste dvs.På) tid.

Da JEP 180 kommer ind i billedet, har der imidlertid været en subtil ændring i implementeringen af ​​den måde, hvorpå elementerne er arrangeret i en HashMap.

I henhold til specifikationen, når skovle bliver for store og indeholder nok noder, bliver de omdannet til tilstande TreeNodes, hver struktureret på samme måde som i TreeMap.

Derfor, i tilfælde af høje hashkollisioner, forbedres ydeevnen i værste fald fra På) til O (log n).

Koden, der udfører denne transformation, er illustreret nedenfor:

hvis (binCount> = TREEIFY_THRESHOLD - 1) {treeifyBin (fane, hash); }

Værdien for TREEIFY_THRESHOLD er otte, hvilket effektivt angiver tærskelværdien for at bruge et træ i stedet for en sammenkædet liste til en spand.

Det er tydeligt, at:

  • EN HashMap kræver meget mere hukommelse, end det er nødvendigt for at gemme dens data
  • EN HashMap bør ikke være mere end 70% - 75% fuld. Hvis det kommer tæt på, ændres størrelsen på det, og poster genindvaskes
  • Genopvaskning kræver n operationer, som er dyre, hvor vores konstant tidsindsats bliver af orden På)
  • Det er hashing-algoritmen, der bestemmer rækkefølgen for indsættelse af objekterne i HashMap

Udførelsen af ​​en HashMap kan indstilles ved at indstille brugerdefineret startkapacitet og belastningsfaktorpå tidspunktet for HashMap selve objektoprettelsen.

Vi skal dog vælge en HashMap hvis:

  • vi ved cirka hvor mange genstande, der skal vedligeholdes i vores samling
  • vi ønsker ikke at udtrække varer i en naturlig rækkefølge

Under ovenstående omstændigheder HashMap er vores bedste valg, fordi det giver konstant tidsindsættelse, søgning og sletning.

3.2. TreeMap

EN TreeMap gemmer sine data i et hierarkisk træ med evnen til at sortere elementerne ved hjælp af en brugerdefineret Komparator.

Et resumé af dets præstationer:

  • TreeMap giver en præstation af O (log (n)) for de fleste operationer som tilføje(), fjerne() og indeholder()
  • EN Treemap kan gemme hukommelse (sammenlignet med HashMap) fordi den kun bruger den mængde hukommelse, der er nødvendig for at holde dens emner, i modsætning til HashMap der bruger sammenhængende hukommelsesregion
  • Et træ skal opretholde sin balance for at opretholde sin tilsigtede ydeevne, dette kræver en betydelig indsats, og derfor komplicerer implementeringen

Vi skulle gå efter en TreeMap hver gang:

  • hukommelsesbegrænsninger skal tages i betragtning
  • vi ved ikke, hvor mange genstande der skal gemmes i hukommelsen
  • vi ønsker at udtrække objekter i en naturlig rækkefølge
  • hvis genstande tilføjes og fjernes konsekvent
  • vi er villige til at acceptere O (log n) søgetid

4. Ligheder

4.1. Unikke elementer

Begge TreeMap og HashMap understøtter ikke duplikatnøgler. Hvis det tilføjes, tilsidesætter det det forrige element (uden en fejl eller en undtagelse):

@Test offentlig ugyldighed givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique () {Map treeMap = new HashMap (); treeMap.put (1, "Baeldung"); treeMap.put (1, "Baeldung"); assertTrue (treeMap.size () == 1); Map treeMap2 = nyt TreeMap (); treeMap2.put (1, "Baeldung"); treeMap2.put (1, "Baeldung"); assertTrue (treeMap2.size () == 1); }

4.2. Samtidig adgang

Begge Kort implementeringer er ikke synkroniseret og vi er nødt til at administrere samtidig adgang alene.

Begge skal synkroniseres eksternt, når flere tråde får adgang til dem samtidigt, og mindst en af ​​tråde ændrer dem.

Vi skal udtrykkeligt bruge det Collections.synchronizedMap (mapName) for at opnå en synkroniseret visning af et givet kort.

4.3. Fail-Fast Iteratorer

Det Iterator kaster en ConcurrentModificationException hvis den Kort bliver ændret på nogen måde og når som helst, når iteratoren er oprettet.

Derudover kan vi bruge iteratorens fjernelsesmetode til at ændre Kort under iteration.

Lad os se et eksempel:

@Test offentlig ugyldig nårModifyMapDuringIteration_thenThrowExecption () {Map hashmap = new HashMap (); hashmap.put (1, "One"); hashmap.put (2, "To"); Eksekverbar eksekverbar = () -> hashmap .forEach ((nøgle, værdi) -> hashmap.remove (1)); assertThrows (ConcurrentModificationException.class, eksekverbar); }

5. Hvilken implementering skal du bruge?

Generelt har begge implementeringer deres respektive fordele og ulemper, dog det handler om at forstå den underliggende forventning og krav, der skal styre vores valg vedrørende det samme.

Sammenfatning:

  • Vi skal bruge en TreeMap hvis vi vil holde vores poster sorteret
  • Vi skal bruge en HashMap hvis vi prioriterer ydeevne frem for hukommelsesforbrug
  • Siden en TreeMap har en mere betydelig lokalitet, kan vi overveje det, hvis vi ønsker at få adgang til objekter, der er relativt tæt på hinanden i henhold til deres naturlige rækkefølge
  • HashMap kan indstilles ved hjælp af initialCapacity og belastningsfaktor, hvilket ikke er muligt for TreeMap
  • Vi kan bruge LinkedHashMap hvis vi vil bevare indsætningsordren, mens vi drager fordel af konstant tidsadgang

6. Konklusion

I denne artikel viste vi forskellene og lighederne mellem TreeMap og HashMap.

Som altid er kodeeksemplerne til denne artikel tilgængelige på GitHub.