streamalism.org

1. Oversikt

I denne artikkelen ser vi på en integrert del av Java Collections Framework og en av de mest populære Sett implementeringer - den TreeSet.

2. Introduksjon til TreeSet

Enkelt sagt, den TreeSet er en sortert samling som utvider Abstrakt sett klasse og implementerer NavigableSet grensesnitt.

Her er et raskt sammendrag av de viktigste aspektene ved denne implementeringen:

• Den lagrer unike elementer
• Det bevarer ikke innsettingsrekkefølgen for elementene
• Den sorterer elementene i stigende rekkefølge
• Det er ikke trådsikkert

I denne implementeringen blir objekter sortert og lagret i stigende rekkefølge i henhold til deres naturlige rekkefølge. De TreeSet bruker et selvbalanserende binært søketre, nærmere bestemt a Rød svart tre.

Enkelt sagt, som et selvbalanserende binært søketre, består hver node i det binære treet av en ekstra bit, som brukes til å identifisere fargen på noden som enten er rød eller svart. Under påfølgende innsetting og sletting hjelper disse "fargebitene" med å sikre at treet forblir mer eller mindre balansert.

Så la oss lage en forekomst av en TreeSet:

Sett treeSet = nytt TreeSet ();

2.1. TreeSet med en Constructor Comparator Param

Eventuelt kan vi konstruere en TreeSet med en konstruktør som lar oss definere rekkefølgen elementene blir sortert ved å bruke a Sammenlignelig eller Komparator:

Sett treeSet = nytt TreeSet (Comparator.comparing (streng :: lengde));

Selv om TreeSet ikke er trådsikker, kan den synkroniseres eksternt ved hjelp av Collections.synchronizedSet () innpakning:

Sett syncTreeSet = Collections.synchronizedSet (treeSet);

Greit, nå som vi har en klar ide om hvordan vi kan lage en TreeSet La oss ta en titt på de vanlige operasjonene vi har tilgjengelig.

3. TreeSetlegge til()

De legge til() metode, som forventet, kan brukes til å legge til elementer i en TreeSet. Hvis et element ble lagt til, returnerer metoden ekte, ellers - falsk.

Kontrakten med metoden sier at et element bare vil bli lagt til når det samme ikke allerede er til stede i Sett.

La oss legge til et element i a TreeSet:

@Test offentlig ugyldig nårAddingElement_shouldAddElement () {Set treeSet = new TreeSet (); assertTrue (treeSet.add ("String lagt til")); }

De legge til metoden er ekstremt viktig ettersom implementeringsdetaljene for metoden illustrerer hvordan TreeSet jobber internt, hvordan den utnytter TreeMap'ssette metode for å lagre elementene:

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

Variabelen m refererer til en intern støtte TreeMap (noter det TreeMap redskaper NavigateableMap):

privat forbigående NavigableMap m;

derfor TreeSet internt avhenger av støtte NavigableMap som blir initialisert med en forekomst av TreeMap når en forekomst av TreeSet er skapt:

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

Mer om dette finner du i denne artikkelen.

4. TreeSet inneholder ()

De inneholder () metoden brukes til å sjekke om et gitt element er tilstede i et gitt TreeSet. Hvis elementet blir funnet, returnerer det sant, ellers falsk.

La oss se inneholder () i aksjon:

@Test offentlig ugyldig nårCheckingForElement_shouldSearchForElement () {Set treeSetContains = new TreeSet (); treeSetContains.add ("Streng lagt til"); assertTrue (treeSetContains.contains ("String lagt til")); }

5. TreeSet fjerne ()

De fjerne() metoden brukes til å fjerne det spesifiserte elementet fra settet hvis det er til stede.

Hvis et sett inneholdt det angitte elementet, returnerer denne metoden ekte.

La oss se det i aksjon:

@Test offentlig ugyldig nårRemovingElement_shouldRemoveElement () {Set removeFromTreeSet = new TreeSet (); removeFromTreeSet.add ("Streng lagt til"); assertTrue (removeFromTreeSet.remove ("Streng lagt til")); }

6. TreeSet clear ()

Hvis vi vil fjerne alle elementene fra et sett, kan vi bruke klar() metode:

@Test offentlig ugyldig nårClearingTreeSet_shouldClearTreeSet () {Set clearTreeSet = new TreeSet (); clearTreeSet.add ("String lagt til"); clearTreeSet.clear (); assertTrue (clearTreeSet.isEmpty ()); }

7. TreeSet størrelse ()

De størrelse() metoden brukes til å identifisere antall elementer som er tilstede i TreeSet. Det er en av de grunnleggende metodene i API: et:

@Test offentlig ugyldig nårCheckingTheSizeOfTreeSet_shouldReturnThesize () {Set treeSetSize = new TreeSet (); treeSetSize.add ("String lagt til"); assertEquals (1, treeSetSize.size ()); }

8. TreeSet er tom ()

De er tom() metoden kan brukes til å finne ut om en gitt TreeSet forekomst er tom eller ikke:

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

9. TreeSet iterator ()

De iterator () metoden returnerer en iterator som itererer i stigende rekkefølge over elementene i Sett. Disse iteratorene går raskt.

Vi kan observere den stigende iterasjonsrekkefølgen 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 ()); }}

I tillegg TreeSet gjør oss i stand til å gjenta gjennom Sett i fallende rekkefølge.

La oss se det i aksjon:

@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 ()); }}

De Iterator kaster en ConcurrentModificationException if settet endres når som helst etter at iteratoren er opprettet på noen måte unntatt gjennom iteratoren fjerne() metode.

La oss lage 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 hadde brukt metoden for fjerning av iteratoren, ville vi ikke ha opplevd unntaket:

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

Det er ingen garanti for en iterators feilrask oppførsel, da det er umulig å gi noen harde garantier i nærvær av usynkronisert samtidig endring.

Mer om dette finner du her.

10. TreeSet først ()

Denne metoden returnerer det første elementet fra a TreeSet hvis den ikke er tom. Ellers kaster det a NoSuchElementException.

La oss se et eksempel:

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

11. TreeSet siste ()

Analogt med eksemplet ovenfor vil denne metoden returnere det siste elementet hvis settet ikke er tomt:

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

12. TreeSet subSet ()

Denne metoden vil returnere elementene 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); Still forventet sett = nytt tresett (); expectSet.add (2); expectSet.add (3); expectSet.add (4); expectSet.add (5); Sett subSet = treeSet.subSet (2, 6); assertEquals (expectSet, subSet); }

13. TreeSet headSet ()

Denne metoden vil returnere elementer av TreeSet som er mindre enn det spesifiserte elementet:

@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); Sett subSet = treeSet.headSet (6); assertEquals (subSet, treeSet.subSet (1, 6)); }

14. TreeSet tailSet ()

Denne metoden vil returnere elementene i a TreeSet som er større enn eller lik det spesifiserte elementet:

@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); Sett subSet = treeSet.tailSet (3); assertEquals (subSet, treeSet.subSet (3, true, 6, true)); }

15. Lagring Null Elementer

Før Java 7 var det mulig å legge til null elementer til en tom TreeSet.

Imidlertid ble det ansett som en feil. Derfor, TreeSet støtter ikke lenger tillegg av null.

Når vi legger til elementer i TreeSet, elementene blir sortert i henhold til deres naturlige orden eller som spesifisert av komparator. Derfor legger du til en null, sammenlignet med eksisterende elementer, resulterer det i en NullPointerException siden null kan ikke sammenlignes med noen verdi:

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

Elementer satt inn i TreeSet må enten implementere Sammenlignelig grensesnitt eller i det minste bli akseptert av den spesifiserte komparatoren. Alle slike elementer må være gjensidig sammenlignbare,dvs.e1.compareTo (e2) eller comparator.compare (e1, e2)må ikke kaste a ClassCastException.

La oss se et eksempel:

klasse Element {privat Heltall-id; // Andre metoder ...} Comparator comparator = (ele1, ele2) -> {return ele1.getId (). ComparTo (ele2.getId ()); }; @Test offentlig ugyldig nårUsingComparator_shouldSortAndInsertElements () {Set treeSet = new TreeSet (comparator); Element ele1 = nytt Element (); ele1.setId (100); Element ele2 = nytt Element (); ele2.setId (200); treeSet.add (ele1); treeSet.add (ele2); System.out.println (treeSet); }

16. Utførelse av TreeSet

Sammenlignet med en HashSet ytelsen til en TreeSet er på undersiden. Operasjoner som legge til, fjerne og Søk ta O (log n) tid mens operasjoner som utskrift n elementer i sortert rekkefølge krever På) tid.

EN TreeSet bør være vårt primære valg hvis vi ønsker å holde oppføringene sortert som en TreeSet kan nås og krysses i stigende eller synkende rekkefølge, og utførelsen av stigende operasjoner og visninger vil sannsynligvis være raskere enn for synkende.

Prinsippet om lokalitet - er et begrep for fenomenet hvor man ofte får tilgang til de samme verdiene, eller relaterte lagringsplasser, avhengig av minnetilgangsmønsteret.

Når vi sier lokalitet:

• Lignende data er ofte tilgjengelig av en applikasjon med lignende frekvens
• Hvis to oppføringer er i nærheten, får en bestilling, a TreeSet plasserer dem nær hverandre i datastrukturen, og dermed i minnet

EN TreeSet å være en datastruktur med større lokalitet, kan vi derfor konkludere i samsvar med lokalitetsprinsippet om at vi bør foretrekke en TreeSet hvis vi har lite minne og hvis vi vil ha tilgang til elementer som er relativt nær hverandre i henhold til deres naturlige rekkefølge.

I tilfelle data må leses fra harddisken (som har større ventetid enn data som leses fra hurtigbufferen eller minnet), foretrekker du TreeSet ettersom den har større lokalitet

17. Konklusjon

I denne artikkelen fokuserer vi på å forstå hvordan du bruker standarden TreeSet implementering i Java. Vi så formålet med det og hvor effektivt det er med hensyn til brukervennlighet gitt dets evne til å unngå duplikater og sortere elementer.

Som alltid kan du finne kodebiter på GitHub.