En guide til TreeSet i Java

1. Oversigt

I denne artikel ser vi på en integreret del af Java Collections Framework og en af ​​de mest populære Sæt implementeringer - den TreeSet.

2. Introduktion til TreeSet

Kort sagt, den TreeSet er en sorteret samling, der udvider Abstrakt sæt klasse og implementerer NavigableSet interface.

Her er et hurtigt resumé af de vigtigste aspekter af denne implementering:

  • Det gemmer unikke elementer
  • Det bevarer ikke elementernes indsætningsrækkefølge
  • Det sorterer elementerne i stigende rækkefølge
  • Det er ikke trådsikkert

I denne implementering sorteres objekter og lagres i stigende rækkefølge i henhold til deres naturlige rækkefølge. Det TreeSet bruger et selvbalancerende binært søgetræ, mere specifikt a Rød-sort træ.

Kort sagt, da det er et selvbalancerende binært søgetræ, består hvert knudepunkt af det binære træ af en ekstra bit, der bruges til at identificere farven på noden, som enten er rød eller sort. Under efterfølgende indsættelser og sletninger hjælper disse “farve” bits med at sikre, at træet forbliver mere eller mindre afbalanceret.

Så lad os oprette en forekomst af en TreeSet:

Indstil treeSet = nyt TreeSet ();

2.1. TreeSet med en Constructor Comparator Param

Eventuelt kan vi konstruere en TreeSet med en konstruktør, der lader os definere rækkefølgen, i hvilken elementerne sorteres ved hjælp af a Sammenlignelig eller Komparator:

Indstil treeSet = nyt TreeSet (Comparator.comparing (String :: længde));

Selvom TreeSet ikke er trådsikker, kan den synkroniseres eksternt ved hjælp af Collections.synchronizedSet () indpakning:

Indstil syncTreeSet = Collections.synchronizedSet (treeSet);

Okay, nu hvor vi har en klar idé om, hvordan vi opretter en TreeSet Lad os f.eks. se på de almindelige operationer, vi har til rådighed.

3. TreeSettilføje()

Det tilføje() metode, som forventet, kan bruges til at tilføje elementer til en TreeSet. Hvis der blev tilføjet et element, returneres metoden rigtigt, Ellers - falsk.

Kontrakten med metoden angiver, at et element kun tilføjes, når det samme ikke allerede er til stede i Sæt.

Lad os tilføje et element til en TreeSet:

@Test offentlig ugyldig nårAddingElement_shouldAddElement () {Set treeSet = new TreeSet (); assertTrue (treeSet.add ("Streng tilføjet")); }

Det tilføje metoden er ekstremt vigtig, da implementeringsoplysningerne om metoden illustrerer, hvordan TreeSet arbejder internt, hvordan det udnytter TreeMap'ssætte metode til at gemme elementerne:

public boolean add (E e) {return m.put (e, PRESENT) == null; }

Variablen m henviser til en intern opbakning TreeMap (Noter det TreeMap redskaber NavigateableMap):

privat forbigående NavigableMap m;

Derfor er den TreeSet internt afhænger af en opbakning NavigableMap som bliver initialiseret med en forekomst af TreeMap når en forekomst af TreeSet er oprettet:

public TreeSet () {this (new TreeMap ()); }

Mere om dette kan findes i denne artikel.

4. TreeSet indeholder ()

Det indeholder() metode bruges til at kontrollere, om et givet element er til stede i et givet TreeSet. Hvis elementet findes, returnerer det sandt, ellers falsk.

Lad os se indeholder() i aktion:

@Test offentlig ugyldig nårCheckingForElement_shouldSearchForElement () {Set treeSetContains = new TreeSet (); treeSetContains.add ("Streng tilføjet"); assertTrue (treeSetContains.contains ("Streng tilføjet")); }

5. TreeSet fjern ()

Det fjerne() metoden bruges til at fjerne det angivne element fra sættet, hvis det er til stede.

Hvis et sæt indeholdt det angivne element, returneres denne metode rigtigt.

Lad os se det i aktion:

@Test offentlig ugyldig nårRemovingElement_shouldRemoveElement () {Set removeFromTreeSet = nyt TreeSet (); removeFromTreeSet.add ("Streng tilføjet"); assertTrue (removeFromTreeSet.remove ("Streng tilføjet")); }

6. TreeSet clear ()

Hvis vi vil fjerne alle elementerne fra et sæt, kan vi bruge klar() metode:

@Test offentlig ugyldig nårClearingTreeSet_shouldClearTreeSet () {Set clearTreeSet = new TreeSet (); clearTreeSet.add ("Streng tilføjet"); clearTreeSet.clear (); assertTrue (clearTreeSet.isEmpty ()); }

7. TreeSet størrelse ()

Det størrelse() Metoden bruges til at identificere antallet af elementer, der findes i TreeSet. Det er en af ​​de grundlæggende metoder i API:

@Test offentlig ugyldig nårCheckingTheSizeOfTreeSet_shouldReturnThesize () {Set treeSetSize = new TreeSet (); treeSetSize.add ("Streng tilføjet"); assertEquals (1, treeSetSize.size ()); }

8. TreeSet er tom ()

Det er tom() metode kan bruges til at finde ud af, om en given TreeSet forekomst er tom eller ej:

@Test offentlig ugyldig nårCheckingForEmptyTreeSet_shouldCheckForEmpty () {Set emptyTreeSet = new TreeSet (); assertTrue (emptyTreeSet.isEmpty ()); }

9. TreeSet iterator ()

Det iterator () metoden returnerer en iterator, der gentager i stigende rækkefølge over elementerne i Sæt. Disse iteratorer er fail-hurtige.

Vi kan observere den stigende iterationsrækkefølge her:

@Test offentlig ugyldig nårIteratingTreeSet_shouldIterateTreeSetInAscendingOrder () {Set treeSet = new TreeSet (); treeSet.add ("First"); treeSet.add ("Second"); treeSet.add ("Tredje"); Iterator itr = treeSet.iterator (); mens (itr.hasNext ()) {System.out.println (itr.next ()); }}

Derudover TreeSet gør det muligt for os at gentage gennem Sæt i faldende rækkefølge.

Lad os se det i aktion:

@Test offentlig ugyldig nårIteratingTreeSet_shouldIterateTreeSetInDescendingOrder () {TreeSet treeSet = new TreeSet (); treeSet.add ("First"); treeSet.add ("Second"); treeSet.add ("Tredje"); Iterator itr = treeSet.descendingIterator (); mens (itr.hasNext ()) {System.out.println (itr.next ()); }}

Det Iterator kaster en ConcurrentModificationException if Sættet ændres når som helst efter at iteratoren er oprettet på nogen måde undtagen gennem iteratorens fjerne() metode.

Lad os oprette en test for dette:

@Test (forventet = ConcurrentModificationException.class) offentlig ugyldig nårModifyingTreeSetWhileIterating_shouldThrowException () {Set treeSet = new TreeSet (); treeSet.add ("First"); treeSet.add ("Second"); treeSet.add ("Tredje"); Iterator itr = treeSet.iterator (); mens (itr.hasNext ()) {itr.next (); treeSet.remove ("Second"); }} 

Alternativt, hvis vi havde brugt iteratorens fjernelsesmetode, ville vi ikke have fundet undtagelsen:

@Test offentlig ugyldig nårRemovingElementUsingIterator_shouldRemoveElement () {Set treeSet = new TreeSet (); treeSet.add ("First"); treeSet.add ("Second"); treeSet.add ("Tredje"); Iterator itr = treeSet.iterator (); mens (itr.hasNext ()) {String element = itr.next (); if (element.equals ("Second")) itr.remove (); } assertEquals (2, treeSet.size ()); }

Der er ingen garanti for, at en iterator fejler hurtigt, da det er umuligt at stille hårde garantier i nærvær af usynkroniseret samtidig ændring.

Mere om dette kan findes her.

10. TreeSet først ()

Denne metode returnerer det første element fra a TreeSet hvis det ikke er tomt. Ellers kaster det en NoSuchElementException.

Lad os se et eksempel:

@Test offentlig ugyldig nårCheckingFirstElement_shouldReturnFirstElement () {TreeSet treeSet = new TreeSet (); treeSet.add ("First"); assertEquals ("First", treeSet.first ()); }

11. TreeSet sidste ()

Analogt med ovenstående eksempel returnerer denne metode det sidste element, hvis sættet ikke er tomt:

@Test offentlig ugyldig nårCheckingLastElement_shouldReturnLastElement () {TreeSet treeSet = new TreeSet (); treeSet.add ("First"); treeSet.add ("Sidste"); assertEquals ("Last", treeSet.last ()); }

12. TreeSet subSet ()

Denne metode returnerer elementerne fra fromElement til toElement. Noter det fromElement er inkluderende og toElement er eksklusiv:

@Test offentlig ugyldig nårUsingSubSet_shouldReturnSubSetElements () {SortedSet treeSet = new TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Sæt expectSet = nyt TreeSet (); expectSet.add (2); expectSet.add (3); expectSet.add (4); expectSet.add (5); Sæt subSet = treeSet.subSet (2, 6); assertEquals (expectSet, subSet); }

13. TreeSet headSet ()

Denne metode returnerer elementer af TreeSet som er mindre end det angivne element:

@Test offentlig ugyldig nårUsingHeadSet_shouldReturnHeadSetElements () {SortedSet treeSet = new TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Indstil subSet = treeSet.headSet (6); assertEquals (subSet, treeSet.subSet (1, 6)); }

14. TreeSet tailSet ()

Denne metode returnerer elementerne i a TreeSet som er større end eller lig med det angivne element:

@Test offentlig ugyldig nårUsingTailSet_shouldReturnTailSetElements () {NavigableSet treeSet = new TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Indstil subSet = treeSet.tailSet (3); assertEquals (subSet, treeSet.subSet (3, true, 6, true)); }

15. Opbevaring Nul Elementer

Før Java 7 var det muligt at tilføje nul elementer til en tom TreeSet.

Det blev dog betragtet som en fejl. Derfor, TreeSet understøtter ikke længere tilføjelsen af nul.

Når vi tilføjer elementer til Træsæt, elementerne sorteres efter deres naturlige rækkefølge eller som specificeret af komparator. Derfor tilføjes en nul, sammenlignet med eksisterende elementer, resulterer i NullPointerException siden nul kan ikke sammenlignes med nogen værdi:

@Test (forventet = NullPointerException.class) offentlig ugyldig nårAddingNullToNonEmptyTreeSet_shouldThrowException () {Set treeSet = new TreeSet (); treeSet.add ("First"); treeSet.add (null); }

Elementer indsat i TreeSet skal enten implementere Sammenlignelig interface eller i det mindste accepteres af den specificerede komparator. Alle sådanne elementer skal være indbyrdes sammenlignelige,dvs.e1.compareTo (e2) eller comparator.compare (e1, e2)må ikke smide en ClassCastException.

Lad os se et eksempel:

klasse Element {privat heltal id; // Andre metoder ...} Komparator-komparator = (ele1, ele2) -> {returner ele1.getId (). SammenlignTo (ele2.getId ()); }; @Test offentlig ugyldig nårUsingComparator_shouldSortAndInsertElements () {Set treeSet = new TreeSet (comparator); Element ele1 = nyt element (); ele1.setId (100); Element ele2 = nyt element (); ele2.setId (200); treeSet.add (ele1); treeSet.add (ele2); System.out.println (treeSet); }

16. Opførelse af TreeSet

Sammenlignet med en HashSet udførelsen af ​​en TreeSet er på undersiden. Operationer som tilføje, fjerne og Søg tage O (log n) tid, mens operationer som udskrivning n elementer i sorteret rækkefølge kræver På) tid.

EN TreeSet bør være vores primære valg, hvis vi vil beholde vores poster sorteret som en TreeSet kan tilgås og krydses i enten stigende eller faldende rækkefølge, og udførelsen af ​​stigende operationer og visninger er sandsynligvis hurtigere end for faldende.

Princippet om lokalitet - er et udtryk for fænomenet, hvor de samme værdier eller relaterede lagerplaceringer ofte er tilgængelige, afhængigt af hukommelsesadgangsmønsteret.

Når vi siger lokalitet:

  • Lignende data er ofte åbnet af en applikation med lignende frekvens
  • Hvis der er bestilt to poster i nærheden, a TreeSet placerer dem nær hinanden i datastrukturen og dermed i hukommelsen

EN TreeSet at være en datastruktur med større lokalitet, kan vi derfor konkludere i overensstemmelse med lokalitetsprincippet, at vi skal foretrække en TreeSet hvis vi mangler hukommelse, og hvis vi ønsker at få adgang til elementer, der er relativt tæt på hinanden i henhold til deres naturlige rækkefølge.

Hvis data skal læses fra harddisken (som har større latenstid end data, der læses fra cachen eller hukommelsen), foretrækker TreeSet da det har større lokalitet

17. Konklusion

I denne artikel fokuserer vi på at forstå, hvordan man bruger standarden TreeSet implementering i Java. Vi så dets formål, og hvor effektiv det er med hensyn til anvendelighed i betragtning af dets evne til at undgå duplikater og sortere elementer.

Som altid kan kodeuddrag findes på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found