streamalism.org

1. Overzicht

In dit artikel zullen we een integraal onderdeel van het Java Collections Framework en een van de populairste Set implementaties - de TreeSet.

2. Inleiding tot TreeSet

Simpel gezegd, de TreeSet is een gesorteerde verzameling die de extensie AbstractSet class en implementeert het NavigableSet koppel.

Hier is een korte samenvatting van de belangrijkste aspecten van deze implementatie:

• Het slaat unieke elementen op
• Het behoudt niet de volgorde van invoegen van de elementen
• Het sorteert de elementen in oplopende volgorde
• Het is niet draadveilig

Bij deze implementatie worden objecten gesorteerd en opgeslagen in oplopende volgorde volgens hun natuurlijke volgorde. De TreeSet gebruikt een zelfbalancerende binaire zoekboom, meer specifiek een Rood Zwart boom.

Simpel gezegd, omdat het een zelfbalancerende binaire zoekboom is, bestaat elk knooppunt van de binaire boom uit een extra bit, dat wordt gebruikt om de kleur van het knooppunt te identificeren, die ofwel rood of zwart is. Tijdens daaropvolgende invoegingen en verwijderingen helpen deze "kleur" -bits ervoor te zorgen dat de boom min of meer in balans blijft.

Laten we dus een instantie maken van een TreeSet:

Set treeSet = nieuwe TreeSet ();

2.1. TreeSet met een constructor-vergelijkingsparameter

Optioneel kunnen we een TreeSet met een constructor waarmee we de volgorde kunnen definiëren waarin de elementen worden gesorteerd door een Vergelijkbaar of Comparator:

Set treeSet = new TreeSet (Comparator.comparing (String :: length));

Hoewel TreeSet is niet thread-safe, het kan extern worden gesynchroniseerd met behulp van de Collections.synchronizedSet () wikkel:

Set syncTreeSet = Collections.synchronizedSet (treeSet);

Oké, nu we een duidelijk idee hebben van hoe we een TreeSet Laten we bijvoorbeeld eens kijken naar de algemene bewerkingen die we beschikbaar hebben.

3. TreeSettoevoegen()

De toevoegen() methode, zoals verwacht, kan worden gebruikt voor het toevoegen van elementen aan een TreeSet. Als er een element is toegevoegd, keert de methode terug waar, anders - false.

In het contract van de methode staat dat een element alleen wordt toegevoegd als dit nog niet aanwezig is in het Set.

Laten we een element toevoegen aan een TreeSet:

@Test openbare leegte whenAddingElement_shouldAddElement () {Set treeSet = nieuwe TreeSet (); assertTrue (treeSet.add ("String toegevoegd")); }

De toevoegen methode is buitengewoon belangrijk omdat de implementatiedetails van de methode illustreren hoe de TreeSet werkt intern, hoe het gebruikmaakt van de TreeMap'sleggen methode om de elementen op te slaan:

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

De variabele m verwijst naar een interne rug TreeMap (Let daar op TreeMap werktuigen Navigeerbare kaart):

privé voorbijgaande NavigableMap m;

Daarom, de TreeSet intern afhankelijk van een backing NavigableMap die wordt geïnitialiseerd met een instantie van TreeMap wanneer een instantie van de TreeSet is gecreëerd:

openbare TreeSet () {this (nieuwe TreeMap ()); }

Hierover leest u meer in dit artikel.

4. TreeSet bevat ()

De bevat () methode wordt gebruikt om te controleren of een bepaald element aanwezig is in een gegeven TreeSet. Als het element wordt gevonden, retourneert het true, anders false.

Laten we eens kijken naar de bevat () in actie:

@Test openbare leegte whenCheckingForElement_shouldSearchForElement () {Set treeSetContains = nieuwe TreeSet (); treeSetContains.add ("String toegevoegd"); assertTrue (treeSetContains.contains ("String toegevoegd")); }

5. TreeSet verwijderen ()

De verwijderen() methode wordt gebruikt om het opgegeven element uit de set te verwijderen als het aanwezig is.

Als een set het opgegeven element bevat, retourneert deze methode waar.

Laten we het in actie zien:

@Test openbare leegte whenRemovingElement_shouldRemoveElement () {Set removeFromTreeSet = nieuwe TreeSet (); removeFromTreeSet.add ("String toegevoegd"); assertTrue (removeFromTreeSet.remove ("String toegevoegd")); }

6. TreeSet helder ()

Als we alle items uit een set willen verwijderen, kunnen we de Doorzichtig() methode:

@ Test openbare leegte whenClearingTreeSet_shouldClearTreeSet () {Set clearTreeSet = nieuwe TreeSet (); clearTreeSet.add ("String toegevoegd"); clearTreeSet.clear (); assertTrue (clearTreeSet.isEmpty ()); }

7. TreeSet maat ()

De grootte() methode wordt gebruikt om het aantal elementen te identificeren dat aanwezig is in de TreeSet. Het is een van de fundamentele methoden in de API:

@Test openbare leegte whenCheckingTheSizeOfTreeSet_shouldReturnThesize () {Set treeSetSize = nieuwe TreeSet (); treeSetSize.add ("String toegevoegd"); assertEquals (1, treeSetSize.size ()); }

8. TreeSet isEmpty ()

De is leeg() methode kan worden gebruikt om erachter te komen of een gegeven TreeSet instantie is leeg of niet:

@Test openbare leegte whenCheckingForEmptyTreeSet_shouldCheckForEmpty () {Set emptyTreeSet = nieuwe TreeSet (); assertTrue (emptyTreeSet.isEmpty ()); }

9. TreeSet-iterator ()

De iterator () methode retourneert een iterator die itereert in oplopende volgorde over de elementen in de Set. Die iteratoren zijn niet snel genoeg.

We kunnen de oplopende iteratievolgorde hier observeren:

@ Test openbare leegte whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder () {Set treeSet = nieuwe TreeSet (); treeSet.add ("Eerste"); treeSet.add ("Tweede"); treeSet.add ("Derde"); Iterator itr = treeSet.iterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

Bovendien, TreeSet stelt ons in staat om het Set in aflopende volgorde.

Laten we dat in actie zien:

@Test openbare leegte whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder () {TreeSet treeSet = nieuwe TreeSet (); treeSet.add ("Eerste"); treeSet.add ("Tweede"); treeSet.add ("Derde"); Iterator itr = treeSet.descendingIterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

De Iterator gooit een ConcurrentModificationException if de set wordt op elk moment gewijzigd nadat de iterator op een of andere manier is gemaakt, behalve via de iterator's verwijderen() methode.

Laten we hiervoor een test maken:

@Test (verwacht = ConcurrentModificationException.class) public void whenModifyingTreeSetWhileIterating_shouldThrowException () {Set treeSet = new TreeSet (); treeSet.add ("Eerste"); treeSet.add ("Tweede"); treeSet.add ("Derde"); Iterator itr = treeSet.iterator (); while (itr.hasNext ()) {itr.next (); treeSet.remove ("Tweede"); }} 

Als alternatief, als we de verwijderingsmethode van de iterator hadden gebruikt, zouden we de uitzondering niet zijn tegengekomen:

@Test openbare leegte whenRemovingElementUsingIterator_shouldRemoveElement () {Set treeSet = nieuwe TreeSet (); treeSet.add ("Eerste"); treeSet.add ("Tweede"); treeSet.add ("Derde"); Iterator itr = treeSet.iterator (); while (itr.hasNext ()) {String element = itr.next (); if (element.equals ("Second")) itr.remove (); } assertEquals (2, treeSet.size ()); }

Er is geen garantie voor het faalgedrag van een iterator, aangezien het onmogelijk is om harde garanties te geven in de aanwezigheid van niet-gesynchroniseerde gelijktijdige modificatie.

Meer hierover vind je hier.

10. TreeSet eerste ()

Deze methode retourneert het eerste element van een TreeSet als het niet leeg is. Anders gooit het een NoSuchElementException.

Laten we een voorbeeld bekijken:

@Test openbare leegte whenCheckingFirstElement_shouldReturnFirstElement () {TreeSet treeSet = nieuwe TreeSet (); treeSet.add ("Eerste"); assertEquals ("First", treeSet.first ()); }

11. TreeSet laatste ()

Analoog aan het bovenstaande voorbeeld retourneert deze methode het laatste element als de set niet leeg is:

@Test openbare leegte whenCheckingLastElement_shouldReturnLastElement () {TreeSet treeSet = nieuwe TreeSet (); treeSet.add ("Eerste"); treeSet.add ("Laatste"); assertEquals ("Last", treeSet.last ()); }

12. TreeSet subSet ()

Deze methode retourneert de elementen variërend van fromElement naar naarElement. Let daar op fromElement is inclusief en naarElement is exclusief:

@Test openbare leegte whenUsingSubSet_shouldReturnSubSetElements () {SortedSet treeSet = nieuwe TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Set verwachteSet = nieuwe TreeSet (); verwachteSet.add (2); verwachteSet.add (3); verwachteSet.add (4); verwachteSet.add (5); Stel subSet = treeSet.subSet (2, 6); assertEquals (verwachteSet, subset); }

13. TreeSet headSet ()

Deze methode retourneert elementen van TreeSet die kleiner zijn dan het opgegeven element:

@Test openbare leegte whenUsingHeadSet_shouldReturnHeadSetElements () {SortedSet treeSet = nieuwe TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Stel subSet = treeSet.headSet (6); assertEquals (subSet, treeSet.subSet (1, 6)); }

14. TreeSet tailSet ()

Deze methode retourneert de elementen van een TreeSet die groter zijn dan of gelijk zijn aan het opgegeven element:

@Test openbare leegte whenUsingTailSet_shouldReturnTailSetElements () {NavigableSet treeSet = nieuwe TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Stel subSet = treeSet.tailSet (3); assertEquals (subSet, treeSet.subSet (3, true, 6, true)); }

15. Opslaan Nul Elementen

Vóór Java 7 was het mogelijk om nul elementen naar een lege TreeSet.

Dat werd echter als een bug beschouwd. Daarom TreeSet ondersteunt niet langer de toevoeging van nul.

Wanneer we elementen toevoegen aan het TreeSet, de elementen worden gesorteerd op basis van hun natuurlijke volgorde of zoals gespecificeerd door de comparator. Vandaar het toevoegen van een nul, in vergelijking met bestaande elementen, resulteert in een NullPointerException sinds nul kan met geen enkele waarde worden vergeleken:

@Test (verwacht = NullPointerException.class) openbare leegte whenAddingNullToNonEmptyTreeSet_shouldThrowException () {Set treeSet = nieuwe TreeSet (); treeSet.add ("Eerste"); treeSet.add (null); }

Elementen die zijn ingevoegd in het TreeSet moet ofwel het Vergelijkbaar interface of op zijn minst worden geaccepteerd door de gespecificeerde comparator. Al deze elementen moeten onderling vergelijkbaar zijn,d.w.z.e1.compareTo (e2) of comparator.compare (e1, e2)mag geen ClassCastException.

Laten we een voorbeeld bekijken:

class Element {privé Geheel getal id; // Andere methoden ...} Comparator comparator = (ele1, ele2) -> {retourneer ele1.getId (). CompareTo (ele2.getId ()); }; @Test openbare leegte whenUsingComparator_shouldSortAndInsertElements () {Set treeSet = nieuwe TreeSet (comparator); Element ele1 = nieuw element (); ele1.setId (100); Element ele2 = nieuw element (); ele2.setId (200); treeSet.add (ele1); treeSet.add (ele2); System.out.println (treeSet); }

16. Prestaties van TreeSet

In vergelijking met een HashSet de uitvoering van een TreeSet is aan de onderkant. Operaties zoals toevoegen, verwijderen en zoeken nemen O (logboek n) tijd terwijl bewerkingen zoals afdrukken n elementen in gesorteerde volgorde vereisen Aan) tijd.

EEN TreeSet zou onze eerste keuze moeten zijn als we onze vermeldingen gesorteerd willen houden als een TreeSet kunnen worden geopend en doorlopen in oplopende of aflopende volgorde, en de uitvoering van oplopende bewerkingen en weergaven is waarschijnlijk sneller dan die van aflopende bewerkingen.

The Principle of Locality - is een term voor het fenomeen waarbij dezelfde waarden of gerelateerde opslaglocaties vaak worden gebruikt, afhankelijk van het geheugentoegangspatroon.

Als we plaats zeggen:

• Vergelijkbare gegevens worden vaak benaderd door een applicatie met een vergelijkbare frequentie
• Als er twee vermeldingen in de buurt zijn die een bestelling hebben gekregen, wordt een TreeSet plaatst ze dicht bij elkaar in de datastructuur, en dus in het geheugen

EEN TreeSet omdat het een datastructuur met grotere lokaliteit is, kunnen we daarom in overeenstemming met het principe van lokaliteit concluderen dat we de voorkeur zouden moeten geven aan een TreeSet als we een tekort aan geheugen hebben en als we toegang willen hebben tot elementen die relatief dicht bij elkaar staan ​​volgens hun natuurlijke ordening.

Als gegevens van de harde schijf moeten worden gelezen (die een grotere latentie heeft dan gegevens die uit de cache of het geheugen worden gelezen), geef dan de voorkeur aan TreeSet omdat het een grotere plaats heeft

17. Conclusie

In dit artikel concentreren we ons op het begrijpen van het gebruik van de standaard TreeSet implementatie in Java. We hebben het doel gezien en hoe efficiënt het is met betrekking tot bruikbaarheid, gezien het vermogen om duplicaten te vermijden en elementen te sorteren.

Zoals altijd zijn codefragmenten te vinden op GitHub.