streamalism.org

1. Prehľad

V tomto článku sa pozrieme na neoddeliteľnú súčasť rámca Java Collections Framework a jeden z najpopulárnejších Nastaviť implementácie - TreeSet.

2. Úvod do TreeSet

Jednoducho povedané TreeSet je triedený zber, ktorý rozširuje Sada abstraktov triedy a realizuje NavigableSet rozhranie.

Tu je rýchle zhrnutie najdôležitejších aspektov tejto implementácie:

• Uchováva jedinečné prvky
• Nezachováva poradie vkladania prvkov
• Zoradí prvky vzostupne
• Nie je to bezpečné pre vlákna

V tejto implementácii sú objekty triedené a ukladané vzostupne podľa ich prirodzeného poradia. The TreeSet používa samovyvažujúci binárny vyhľadávací strom, konkrétnejšie a Červená čierna strom.

Zjednodušene povedané, keďže je to samovyvažujúci binárny vyhľadávací strom, každý uzol binárneho stromu obsahuje ďalší bit, ktorý sa používa na identifikáciu červenej alebo čiernej farby uzla. Počas nasledujúcich vkladaní a mazaní tieto „farebné“ bity pomáhajú zabezpečiť, aby strom zostal viac-menej vyvážený.

Vytvorme teda inštanciu a TreeSet:

Set treeSet = new TreeSet ();

2.1. TreeSet s parametrom komparátora komparátora

Voliteľne môžeme zostrojiť a TreeSet s konštruktorom, ktorý nám umožňuje definovať poradie, v akom sa prvky triedia, pomocou a Porovnateľné alebo Komparátor:

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

Hoci TreeSet nie je bezpečný pre vlákna, dá sa synchronizovať externe pomocou Collections.synchronizedSet () obal:

Set syncTreeSet = Collections.synchronizedSet (treeSet);

Dobre, teraz, keď máme jasnú predstavu o tom, ako vytvoriť TreeSet Napríklad sa pozrime na bežné operácie, ktoré máme k dispozícii.

3. TreeSetpridať ()

The pridať () podľa očakávania je možné použiť metódu na pridanie prvkov do a TreeSet. Ak bol pridaný prvok, metóda sa vráti pravda, inak - nepravdivé.

Zmluva o metóde stanovuje, že prvok bude pridaný, iba ak ten istý ešte nie je v Nastaviť.

Pridajme prvok do a TreeSet:

@Test public void whenAddingElement_shouldAddElement () {Set treeSet = new TreeSet (); assertTrue (treeSet.add ("Bol pridaný reťazec")); }

The pridať Metóda je mimoriadne dôležitá, pretože podrobnosti implementácie metódy ilustrujú, ako TreeSet pracuje interne, ako využíva TreeMapdať spôsob ukladania prvkov:

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

Premenná m sa vzťahuje na vnútornú podložku TreeMap (poznač si to TreeMap náradie NavigateableMap):

súkromná prechodná NavigableMap m;

Preto TreeSet vnútorne závisí od podpory NavigableMap ktorý sa inicializuje inštanciou TreeMap keď inštancia TreeSet je vytvorené:

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

Viac o tomto nájdete v tomto článku.

4. TreeSet obsahuje ()

The obsahuje () metóda slúži na kontrolu, či je daný prvok v danom TreeSet. Ak sa prvok nájde, vráti hodnotu true, inak nepravdivé.

Pozrime sa na obsahuje () v akcii:

@Test public void whenCheckingForElement_shouldSearchForElement () {Set treeSetContains = new TreeSet (); treeSetContains.add ("Bol pridaný reťazec"); assertTrue (treeSetContains.contains ("Bol pridaný reťazec")); }

5. TreeSet remove ()

The odstrániť () metóda sa používa na odstránenie zadaného prvku zo súpravy, ak je prítomný.

Ak súprava obsahovala zadaný prvok, táto metóda sa vráti pravda.

Pozrime sa na to v akcii:

@Test public void whenRemovingElement_shouldRemoveElement () {Set removeFromTreeSet = new TreeSet (); removeFromTreeSet.add ("Bol pridaný reťazec"); assertTrue (removeFromTreeSet.remove ("Bol pridaný reťazec")); }

6. TreeSet clear ()

Ak chceme odstrániť všetky položky zo sady, môžeme použiť jasný() metóda:

@Test public void whenClearingTreeSet_shouldClearTreeSet () {Set clearTreeSet = new TreeSet (); clearTreeSet.add ("Bol pridaný reťazec"); clearTreeSet.clear (); assertTrue (clearTreeSet.isEmpty ()); }

7. Veľkosť stromu ()

The veľkosť () metóda sa používa na identifikáciu počtu prvkov prítomných v TreeSet. Je to jedna zo základných metód v API:

@Test public void whenCheckingTheSizeOfTreeSet_shouldReturnThesize () {Set treeSetSize = new TreeSet (); treeSetSize.add ("Bol pridaný reťazec"); assertEquals (1, treeSetSize.size ()); }

8. TreeSet isEmpty ()

The je prázdny() metódu je možné použiť na zistenie, či je daný TreeSet inštancia je prázdna alebo nie:

@Test public void whenCheckingForEmptyTreeSet_shouldCheckForEmpty () {Set emptyTreeSet = new TreeSet (); assertTrue (emptyTreeSet.isEmpty ()); }

9. Iterátor TreeSet ()

The iterátor () metóda vracia iterátor iterujúci vo vzostupnom poradí nad prvkami v Nastaviť. Tieto iterátory sú rýchle.

Tu môžeme sledovať vzostupné poradie iterácií:

@Test public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder () {Set treeSet = new TreeSet (); treeSet.add ("Prvý"); treeSet.add ("druhý"); treeSet.add ("tretí"); Iterátor itr = treeSet.iterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

Navyše, TreeSet nám umožňuje iterovať cez Nastaviť v zostupnom poradí.

Pozrime sa na to v akcii:

@Test public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder () {TreeSet treeSet = new TreeSet (); treeSet.add ("Prvý"); treeSet.add ("druhý"); treeSet.add ("tretí"); Iterator itr = treeSet.descendingIterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

The Iterátor hodí a ConcurrentModificationException if je množina upravená kedykoľvek po vytvorení iterátora akýmkoľvek spôsobom, s výnimkou iterátora odstrániť () metóda.

Vytvorme pre to test:

@Test (očakáva sa = ConcurrentModificationException.class) public void whenModifyingTreeSetWhileIterating_shouldThrowException () {Set treeSet = new TreeSet (); treeSet.add ("Prvý"); treeSet.add ("druhý"); treeSet.add ("tretí"); Iterátor itr = treeSet.iterator (); while (itr.hasNext ()) {itr.next (); treeSet.remove ("Druhý"); }} 

Ak by sme použili metódu odstránenia iterátora, nestretli by sme sa s výnimkou:

@Test public void whenRemovingElementUsingIterator_shouldRemoveElement () {Set treeSet = new TreeSet (); treeSet.add ("Prvý"); treeSet.add ("druhý"); treeSet.add ("tretí"); Iterátor itr = treeSet.iterator (); while (itr.hasNext ()) {Reťazcový prvok = itr.next (); if (element.equals ("Druhý")) itr.remove (); } assertEquals (2, treeSet.size ()); }

Neexistuje žiadna záruka na rýchle zlyhanie iterátora, pretože nie je možné poskytnúť žiadne tvrdé záruky za prítomnosti nesynchronizovanej súbežnej úpravy.

Viac o tomto nájdete tu.

10. TreeSet first ()

Táto metóda vracia prvý prvok z a TreeSet ak nie je prázdny. V opačnom prípade hodí a NoSuchElementException.

Pozrime sa na príklad:

@Test public void whenCheckingFirstElement_shouldReturnFirstElement () {TreeSet treeSet = new TreeSet (); treeSet.add ("Prvý"); assertEquals ("Prvý", treeSet.first ()); }

11. TreeSet last ()

Analogicky k vyššie uvedenému príkladu táto metóda vráti posledný prvok, ak množina nie je prázdna:

@Test public void whenCheckingLastElement_shouldReturnLastElement () {TreeSet treeSet = new TreeSet (); treeSet.add ("Prvý"); treeSet.add ("Posledný"); assertEquals ("Posledný", treeSet.last ()); }

12. Podmnožina TreeSet ()

Táto metóda vráti prvky v rozmedzí od fromElement do toElement. Poznač si to fromElement je inkluzívny a toElement je exkluzívny:

@Test public void whenUsingSubSet_shouldReturnSubSetElements () {SortedSet treeSet = new TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Set expectSet = new TreeSet (); expectSet.add (2); expectSet.add (3); expectSet.add (4); expectSet.add (5); Nastaviť subSet = treeSet.subSet (2, 6); assertEquals (expectSet, subSet); }

13. TreeSet headSet ()

Táto metóda vráti prvky z TreeSet ktoré sú menšie ako zadaný prvok:

@Test public void whenUsingHeadSet_shouldReturnHeadSetElements () {SortedSet treeSet = new TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Nastaviť subSet = treeSet.headSet (6); assertEquals (subSet, treeSet.subSet (1, 6)); }

14. TreeSet tailSet ()

Táto metóda vráti prvky a TreeSet ktoré sú väčšie alebo rovnaké ako zadaný prvok:

@Test public void whenUsingTailSet_shouldReturnTailSetElements () {NavigableSet treeSet = new TreeSet (); treeSet.add (1); treeSet.add (2); treeSet.add (3); treeSet.add (4); treeSet.add (5); treeSet.add (6); Nastaviť subSet = treeSet.tailSet (3); assertEquals (subSet, treeSet.subSet (3, true, 6, true)); }

15. Skladovanie Nulový Prvky

Pred Java 7 bolo možné pridať nulový prvky do prázdna TreeSet.

To sa však považovalo za chybu. Preto TreeSet už nepodporuje pridanie nulový.

Keď pridáme prvky do TreeSet, prvky sa triedia podľa ich prirodzeného poradia alebo podľa špecifikácie komparátor. Preto pridanie a nulový, pri porovnaní s existujúcimi prvkami má za následok a NullPointerException odkedy nulový nemožno porovnať s žiadnou hodnotou:

@Test (očakáva sa = NullPointerException.class) public void whenAddingNullToNonEmptyTreeSet_shouldThrowException () {Set treeSet = new TreeSet (); treeSet.add ("Prvý"); treeSet.add (null); }

Prvky vložené do TreeSet musí buď implementovať Porovnateľné rozhranie alebo minimálne akceptovaný špecifikovaným komparátorom. Všetky tieto prvky musia byť vzájomne porovnateľné,t.j.e1.compareTo (e2) alebo comparator.compare (e1, e2)nesmie hádzať a ClassCastException.

Pozrime sa na príklad:

class Element {private Integer id; // Ostatné metódy ...} Komparátor komparátor = (ele1, ele2) -> {návrat ele1.getId (). CompareTo (ele2.getId ()); }; @Test public void whenUsingComparator_shouldSortAndInsertElements () {Set treeSet = new TreeSet (comparator); Element el1 = nový prvok (); ele1.setId (100); Element ele2 = nový prvok (); ele2.setId (200); treeSet.add (ele1); treeSet.add (ele2); System.out.println (treeSet); }

16. Vystúpenie TreeSet

Pri porovnaní s a HashSet výkon a TreeSet je na spodnej strane. Operácie ako pridať, odstrániť a Vyhľadávanie vziať O (log n) čas pri operáciách, ako je tlač n prvky v zoradenom poradí vyžadujú O (n) čas.

A TreeSet by mala byť naša primárna voľba, ak chceme, aby boli naše záznamy zoradené ako a TreeSet možno pristupovať a prechádzať vo vzostupnom alebo zostupnom poradí a výkonnosť vzostupných operácií a zobrazení je pravdepodobne rýchlejšia ako výkonnosť zostupných.

Princíp polohy - je termín pre jav, pri ktorom sa často pristupuje k rovnakým hodnotám alebo súvisiacim úložným miestam, v závislosti od vzoru prístupu do pamäte.

Keď hovoríme o lokalite:

• K podobným údajom často pristupuje aplikácia s podobnou frekvenciou
• Ak sú pri zadaní objednávky dva záznamy, a TreeSet umiestňuje ich blízko seba v dátovej štruktúre, a teda do pamäte

A TreeSet keďže sme dátovou štruktúrou s väčšou lokalitou, môžeme v súlade s princípom lokálnosti dospieť k záveru, že by sme mali uprednostniť TreeSet ak máme nedostatok pamäte a ak chceme získať prístup k prvkom, ktoré sú relatívne blízko seba podľa ich prirodzeného usporiadania.

V prípade, že je potrebné údaje načítať z pevného disku (ktorý má väčšiu latenciu ako dáta načítané z vyrovnávacej pamäte alebo pamäte), uprednostnite ich TreeSet pretože má väčšiu lokalitu

17. Záver

V tomto článku sa zameriavame na pochopenie toho, ako používať štandard TreeSet implementácia v Jave. Videli sme jeho účel a efektivitu, pokiaľ ide o použiteľnosť, vzhľadom na jeho schopnosť vyhnúť sa duplikátom a triediť prvky.

Útržky kódu ako vždy nájdete na GitHub.