Java TreeMap vs HashMap

1. Introduksjon

I denne artikkelen skal vi sammenligne to Kart implementeringer: TreeMap og HashMap.

Begge implementeringene utgjør en integrert del av Java Samlinger Framework og lagre data som nøkkelverdi par.

2. Forskjeller

2.1. Gjennomføring

Vi snakker først om HashMap som er en hashtable-basert implementering. Det utvider AbstractMap klasse og implementerer Kart grensesnitt. EN HashMap fungerer på prinsippet om hashing.

Dette Kart implementering fungerer vanligvis som en bøtte hasjbord, men når bøtter blir for store, blir de forvandlet til noder av TreeNodes, hver strukturert på samme måte som i java.util.TreeMap.

Du finner mer på HashMap's internals i artikkelen fokuserte på det.

På den andre siden, TreeMap strekker AbstractMap klasse og redskaper NavigableMap grensesnitt. EN TreeMap lagrer kartelementer i en Rød svart treet, som er et Selvbalansering Binært søketre.

Og du kan også finne mer på TreeMap's internals i artikkelen fokuserte på det her.

2.2. Rekkefølge

HashMap gir ingen garanti for måten elementene er ordnet i Kart.

Det betyr, vi kan ikke påta oss noen ordre mens det gjentas over nøklene og verdier av en HashMap:

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

Imidlertid varer i en TreeMap er sortert etter deres naturlige orden.

Hvis TreeMap objekter kan ikke sorteres etter naturlig rekkefølge, så kan vi bruke en Komparator eller Sammenlignelig for å definere rekkefølgen elementene er ordnet i Kart:

@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 (), inneholder (1, 2, 3)); }

2.3. Null Verdier

HashMap tillater lagring av høyst en nullnøkkel og mange null verdier.

La oss se et eksempel:

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

Derimot, TreeMap tillater ikke a nullnøkkel men kan inneholde mange null verdier.

EN null nøkkelen er ikke tillatt fordi sammenligne med() eller sammenligne() metoden kaster en NullPointerException:

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

Hvis vi bruker en TreeMap med en brukerdefinert Komparator, avhenger det av implementeringen av sammenligningen() metode hvordan null verdier blir håndtert.

3. Prestasjonsanalyse

Ytelse er den mest kritiske beregningen som hjelper oss å forstå egnetheten til en datastruktur gitt en brukssak.

I denne delen vil vi gi en omfattende analyse av ytelsen for HashMap og TreeMap.

3.1. HashMap

HashMap, å være en hashtable-basert implementering, bruker internt en array-basert datastruktur for å organisere elementene i henhold til hash-funksjon.

HashMap gir forventet ytelse i konstant tid O (1) for de fleste operasjoner som legge til(), fjerne() og inneholder (). Derfor er det betydelig raskere enn en TreeMap.

Gjennomsnittlig tid for å søke etter et element under en rimelig antagelse i en hash-tabell er O (1). Men en feil implementering av hash-funksjon kan føre til en dårlig fordeling av verdier i bøtter som resulterer i:

  • Memory Overhead - mange bøtter forblir ubrukt
  • Ytelsesnedbrytningjo høyere antall kollisjoner, jo lavere ytelse

Før Java 8, Separat lenking var den eneste foretrukne måten å håndtere kollisjoner på. Det implementeres vanligvis ved hjelp av koblede lister, dvs., hvis det er en kollisjon eller to forskjellige elementer har samme hash-verdi, så lagre begge elementene i den samme koblede listen.

Derfor søker du etter et element i en HashMap, i verste fall kunne ha tatt så lang tid som å søke etter et element i en koblet liste dvs.På) tid.

Imidlertid, med JEP 180 som kommer inn i bildet, har det skjedd en subtil endring i implementeringen av måten elementene er ordnet på HashMap.

I følge spesifikasjonen, når skuffer blir for store og inneholder nok noder, blir de forvandlet til moduser for TreeNodes, hver strukturert på samme måte som i TreeMap.

Derfor, i tilfelle kollisjon med høy hasj, vil ytelsen i verste fall forbedre seg fra På) til O (log n).

Koden som utfører denne transformasjonen er illustrert nedenfor:

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

Verdien for TREEIFY_THRESHOLD er åtte som effektivt angir terskeltellingen for å bruke et tre i stedet for en koblet liste for en bøtte.

Det er tydelig at:

  • EN HashMap krever mye mer minne enn det som er nødvendig for å lagre dataene
  • EN HashMap bør ikke være mer enn 70% - 75% full. Hvis det nærmer seg, blir størrelsen endret og oppføringene utvasket
  • Rehashing krever n operasjoner som er kostbare der vår konstant tidsinnsats blir av orden På)
  • Det er hashing-algoritmen som bestemmer rekkefølgen for å sette inn objektene i HashMap

Utførelsen av en HashMap kan stilles inn ved å stille inn egendefinert startkapasitet og lastfaktor, på tidspunktet for HashMap selve gjenstandsskapingen.

Vi bør imidlertid velge en HashMap hvis:

  • vi vet omtrent hvor mange ting vi skal ha i samlingen vår
  • vi ønsker ikke å trekke ut varer i en naturlig rekkefølge

Under ovennevnte omstendigheter, HashMap er vårt beste valg fordi det tilbyr konstant tidsinnsetting, søk og sletting.

3.2. TreeMap

EN TreeMap lagrer dataene i et hierarkisk tre med muligheten til å sortere elementene ved hjelp av en tilpasset Komparator.

Et sammendrag av ytelsen:

  • TreeMap gir en forestilling av O (logg (n)) for de fleste operasjoner som legge til(), fjerne() og inneholder ()
  • EN Treemap kan spare minne (i forhold til HashMap) fordi den bare bruker mengden minne som trengs for å holde på elementene, i motsetning til en HashMap som bruker sammenhengende hukommelsesregion
  • Et tre bør opprettholde balansen for å opprettholde den tiltenkte ytelsen, dette krever en betydelig innsats, og kompliserer derfor implementeringen

Vi bør gå for en TreeMap når som helst:

  • minnebegrensninger må tas i betraktning
  • vi vet ikke hvor mange gjenstander som må lagres i minnet
  • vi ønsker å trekke ut objekter i en naturlig rekkefølge
  • hvis gjenstander blir lagt til og fjernet konsekvent
  • vi er villige til å akseptere O (log n) søketid

4. Likheter

4.1. Unike elementer

Både TreeMap og HashMap støtter ikke dupliserte nøkler. Hvis det blir lagt til, overstyrer det forrige element (uten feil eller unntak):

@Test offentlig ugyldighet gittHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique () {Map treeMap = new HashMap (); treeMap.put (1, "Baeldung"); treeMap.put (1, "Baeldung"); assertTrue (treeMap.size () == 1); Map treeMap2 = nytt TreeMap (); treeMap2.put (1, "Baeldung"); treeMap2.put (1, "Baeldung"); assertTrue (treeMap2.size () == 1); }

4.2. Samtidig tilgang

Både Kart implementeringer er det ikke synkronisert og vi må administrere tilgang samtidig.

Begge må synkroniseres eksternt når flere tråder får tilgang til dem samtidig, og minst en av trådene endrer dem.

Vi må bruke det eksplisitt Collections.synchronizedMap (mapName) for å få en synkronisert visning av et gitt kart.

4.3. Fail-Fast Iterators

De Iterator kaster en ConcurrentModificationException hvis Kart blir modifisert på noen måte og når som helst når iteratoren er opprettet.

I tillegg kan vi bruke metoden for fjerning av iterator for å endre Kart under iterasjon.

La oss se et eksempel:

@Test offentlig ugyldig nårModifyMapDuringIteration_thenThrowExecption () {Map hashmap = new HashMap (); hashmap.put (1, "One"); hashmap.put (2, "To"); Kjørbar kjørbar = () -> hashmap .forEach ((nøkkel, verdi) -> hashmap.remove (1)); assertThrows (ConcurrentModificationException.class, kjørbar); }

5. Hvilken implementering skal du bruke?

Generelt har begge implementeringene sine respektive fordeler og ulemper, men det handler om å forstå den underliggende forventningen og kravet som må styre vårt valg om det samme.

Oppsummering:

  • Vi bør bruke en TreeMap hvis vi vil holde oppføringene sortert
  • Vi bør bruke en HashMap hvis vi prioriterer ytelse fremfor minneforbruk
  • Siden a TreeMap har en mer betydelig lokalitet, kan vi vurdere det hvis vi ønsker å få tilgang til objekter som er relativt nær hverandre i henhold til deres naturlige rekkefølge
  • HashMap kan stilles inn ved hjelp av initialCapacity og loadFactor, som ikke er mulig for TreeMap
  • Vi kan bruke LinkedHashMap hvis vi vil bevare innsettingsrekkefølgen mens vi drar nytte av konstant tidstilgang

6. Konklusjon

I denne artikkelen viste vi forskjellene og likhetene mellom TreeMap og HashMap.

Som alltid er kodeeksemplene for denne artikkelen tilgjengelig på GitHub.