Útmutató a Java-ban található TreeSet-hez

1. Áttekintés

Ebben a cikkben áttekintjük a Java Collections Framework és a az egyik legnépszerűbb Készlet megvalósítások - a TreeSet.

2. Bevezetés TreeSet

Egyszerűen fogalmazva: TreeSet egy válogatott gyűjtemény, amely kiterjeszti a AbstractSet osztály és végrehajtja a NavigableSet felület.

Itt van egy rövid összefoglaló a megvalósítás legfontosabb szempontjairól:

  • Egyedi elemeket tárol
  • Nem őrzi meg az elemek beszúrási sorrendjét
  • Növekvő sorrendbe rendezi az elemeket
  • Ez nem szálkás

Ebben a megvalósításban az objektumokat növekvő sorrendben rendezik és tárolják a természetes sorrend szerint. A TreeSet önkiegyenlítő bináris kereső fát használ, pontosabban a Piros fekete fa.

Egyszerűen fogalmazva, mivel önkiegyensúlyozó bináris kereső fa, a bináris fa minden csomópontja tartalmaz egy extra bitet, amelyet a csomópont vörös vagy fekete színének azonosítására használnak. A későbbi beillesztések és törlések során ezek a „színes” bitek segítenek abban, hogy a fa többé-kevésbé kiegyensúlyozott maradjon.

Tehát hozzunk létre egy példányt a TreeSet:

Set treeSet = új TreeSet ();

2.1. TreeSet egy konstruktor összehasonlító paraméterrel

Opcionálisan elkészíthetjük a TreeSet egy konstruktorral, amely lehetővé teszi az elemek rendezésének sorrendjét az a használatával Hasonló vagy Összehasonlító:

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

Habár TreeSet nem szálkamentes, a szinkronizálható külsőleg Collections.synchronizedSet () csomagolás:

Set syncTreeSet = Collections.synchronizedSet (treeSet);

Rendben, most, hogy világos elképzelésünk van a TreeSet vessünk egy pillantást a rendelkezésünkre álló közös műveletekre.

3. TreeSetadd ()

A add () módszer, a várakozásoknak megfelelően használható elemek hozzáadásához a TreeSet. Ha elemet adtak hozzá, a metódus visszatér igaz, másképp - hamis.

A metódus szerződése kimondja, hogy egy elem csak akkor kerül hozzáadásra, ha ugyanez még nem szerepel a Készlet.

Adjunk hozzá egy elemet az a-hoz TreeSet:

@Test public void whenAddingElement_shouldAddElement () {Set treeSet = new TreeSet (); assertTrue (treeSet.add ("String hozzáadva")); }

A hozzá A módszer rendkívül fontos, mivel a módszer megvalósítási részletei szemléltetik, hogy a TreeSet belsőleg működik, hogyan használja ki a TreeMap'stedd módszer az elemek tárolására:

nyilvános logikai hozzáadás (E e) {return m.put (e, PRESENT) == null; }

A változó m belső háttérre utal TreeMap (vegye figyelembe, hogy TreeMap megvalósítja Navigálható térkép):

privát tranziens NavigableMap m;

Ezért a TreeSet belsőleg a támogatástól függ NavigableMap amely inicializálódik egy példánnyal TreeMap amikor a TreeSet létrehozva:

public TreeSet () {this (új TreeMap ()); }

Erről bővebben ebben a cikkben található.

4. A TreeSet tartalmaz ()

A tartalmaz () metódust használjuk annak ellenőrzésére, hogy egy adott elem szerepel-e egy adott elemben TreeSet. Ha az elem megtalálható, akkor igaz értéket ad vissza, ellenkező esetben hamis.

Lássuk a tartalmaz () működés közben:

@Test public void whenCheckingForElement_shouldSearchForElement () {Set treeSetContains = new TreeSet (); treeSetContains.add ("String hozzáadva"); assertTrue (treeSetContains.contains ("String hozzáadva")); }

5. TreeSet eltávolítás ()

A eltávolítás () metódust használják a megadott elem eltávolítására a halmazból, ha jelen van.

Ha egy halmaz tartalmazta a megadott elemet, akkor ez a módszer visszatér igaz.

Lássuk működés közben:

@Test public void whenRemovingElement_shouldRemoveElement () {Set removeFromTreeSet = new TreeSet (); removeFromTreeSet.add ("String hozzáadva"); assertTrue (removeFromTreeSet.remove ("String hozzáadva")); }

6. TreeSet clear ()

Ha az összes elemet el akarjuk távolítani egy készletből, használhatjuk a egyértelmű() módszer:

@Test public void whenClearingTreeSet_shouldClearTreeSet () {Set clearTreeSet = new TreeSet (); clearTreeSet.add ("String hozzáadva"); clearTreeSet.clear (); assertTrue (clearTreeSet.isEmpty ()); }

7. TreeSet méret ()

A méret() módszerrel azonosítják a programban jelenlévő elemeket TreeSet. Ez az egyik alapvető módszer az API-ban:

@Test public void whenCheckingTheSizeOfTreeSet_shouldReturnThesize () {Set treeSetSize = new TreeSet (); treeSetSize.add ("String hozzáadva"); assertEquals (1, treeSetSize.size ()); }

8. A TreeSet isEmpty ()

A üres() módszerrel lehet kideríteni, hogy adott-e TreeSet a példány üres vagy sem:

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

9. TreeSet iterator ()

A iterátor () metódus egy iterátort ad vissza növekvő sorrendben az Készlet. Azok az iterátorok kudarcot vallanak.

Itt figyelhetjük meg a növekvő iterációs sorrendet:

@Test public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder () {Set treeSet = new TreeSet (); treeSet.add ("Első"); treeSet.add ("Második"); treeSet.add ("Harmadik"); Iterátor itr = treeSet.iterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

Ezenkívül TreeSet lehetővé teszi számunkra az iterációt a Készlet csökkenő sorrendben.

Lássuk ezt működés közben:

@Test public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder () {TreeSet treeSet = new TreeSet (); treeSet.add ("Első"); treeSet.add ("Második"); treeSet.add ("Harmadik"); Iterátor itr = treeSet.descendingIterator (); while (itr.hasNext ()) {System.out.println (itr.next ()); }}

A Iterátor dob egy ConcurrentModificationException if a halmaz bármikor módosul, miután az iterátort bármilyen módon létrehozták, kivéve az iterátort eltávolítás () módszer.

Hozzunk létre egy tesztet ehhez:

@Test (várható = ConcurrentModificationException.class) public void whenModifyingTreeSetWhileIterating_shouldThrowException () {Set treeSet = new TreeSet (); treeSet.add ("Első"); treeSet.add ("Második"); treeSet.add ("Harmadik"); Iterátor itr = treeSet.iterator (); while (itr.hasNext ()) {itr.next (); treeSet.remove ("Második"); }} 

Alternatív megoldásként, ha az iterátor eltávolítási módszerét használtuk volna, akkor nem találkoztunk volna a kivétellel:

@Test public void whenRemovingElementUsingIterator_shouldRemoveElement () {Set treeSet = new TreeSet (); treeSet.add ("Első"); treeSet.add ("Második"); treeSet.add ("Harmadik"); Iterátor itr = treeSet.iterator (); while (itr.hasNext ()) {String elem = itr.next (); if (elem.egyenlő ("Második")) itr.remove (); } assertEquals (2, treeSet.size ()); }

Nincs garancia az iterátor hibamentes viselkedésére, mivel szinkronizálatlan párhuzamos módosítás esetén lehetetlen szigorú garanciákat nyújtani.

Erről többet itt talál.

10. TreeSet first ()

Ez a módszer az első elemet adja vissza az a-ból TreeSet ha nem üres. Ellenkező esetben a NoSuchElementException.

Lássunk egy példát:

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

11. TreeSet last ()

A fenti példához hasonlóan ez a módszer az utolsó elemet adja vissza, ha a halmaz nem üres:

@Test public void whenCheckingLastElement_shouldReturnLastElement () {TreeSet treeSet = new TreeSet (); treeSet.add ("Első"); treeSet.add ("Utolsó"); assertEquals ("Utolsó", treeSet.last ()); }

12. TreeSet subSet ()

Ez a módszer visszaadja az elemeket fromElement nak nek toElement. Vegye figyelembe, hogy fromElement befogadó és toElement kizárólagos:

@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 VárhatóSet = új TreeSet (); várhatóSet.add (2); várhatóSet.add (3); várhatóSet.add (4); várhatóSet.add (5); Set subSet = treeSet.subSet (2, 6); assertEquals (várhatóSet, subSet); }

13. TreeSet headSet ()

Ez a módszer a TreeSet amelyek kisebbek, mint a megadott elem:

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

14. TreeSet tailSet ()

Ez a módszer az a elemeit adja vissza TreeSet amelyek nagyobbak vagy egyenlőek a megadott elemekkel:

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

15. Tárolás Nulla Elemek

A Java 7 előtt lehetőség volt hozzáadni nulla elemeket egy üres TreeSet.

Ezt azonban hibának tekintették. Ebből kifolyólag, TreeSet már nem támogatja a nulla.

Amikor elemeket adunk a TreeSet, - az elemek a természetes sorrendjük szerint vagy az összehasonlító. Ezért hozzáadjuk a nulla, a meglévő elemekhez képest a NullPointerException mivel nulla nem lehet összehasonlítani semmilyen értékkel:

@Test (várható = NullPointerException.class) public void whenAddingNullToNonEmptyTreeSet_shouldThrowException () {Set treeSet = new TreeSet (); treeSet.add ("Első"); treeSet.add (null); }

Az elembe illesztett elemek TreeSet vagy meg kell valósítania a Hasonló interfészt, vagy legalábbis a megadott összehasonlító elfogadja. Minden ilyen elemnek kölcsönösen összehasonlíthatónak kell lennie,azaze1.compareTo (e2) vagy Comparator.compare (e1, e2)nem szabad dobni a ClassCastException.

Lássunk egy példát:

osztály Elem {magán egész szám azonosító; // Egyéb módszerek ...} Összehasonlító összehasonlító = (ele1, ele2) -> {return ele1.getId (). CompareTo (ele2.getId ()); }; @Test public void whenUsingComparator_shouldSortAndInsertElements () {Set treeSet = új TreeSet (komparátor); Ele1 = új elem (); ele1.setId (100); Elem ele2 = új elem (); ele2.setId (200); treeSet.add (ele1); treeSet.add (ele2); System.out.println (treeSet); }

16. Teljesítése TreeSet

Ha összehasonlítjuk a HashSet előadása a TreeSet az alsó oldalon van. Olyan műveletek, mint hozzá, eltávolítani és keresés vesz O (log n) idő, míg a műveletek, például a nyomtatás n elemek rendezett sorrendben megkövetelik Tovább) idő.

A TreeSet legyen az elsődleges választásunk, ha bejegyzéseinket a-ként szeretnénk rendezni TreeSet akár növekvő, akár csökkenő sorrendben lehet hozzáférni és bejárni őket, és az emelkedő műveletek és nézetek teljesítménye valószínűleg gyorsabb lesz, mint a leszállóaké.

A lokalitás elve - egy olyan jelenség kifejezés, amelyben gyakran ugyanazokat az értékeket vagy kapcsolódó tárolási helyeket érik el, a memória hozzáférési mintázatától függően.

Amikor azt mondjuk, hogy helység:

  • Hasonló adatokhoz gyakran hasonló gyakoriságú alkalmazások férnek hozzá
  • Ha két bejegyzés található a közelben, megrendelést kapunk, a TreeSet egymás közelébe helyezi őket az adatszerkezetben, tehát a memóriában

A TreeSet nagyobb lokalitású adatstruktúra lévén, ezért a lokalitás elvének megfelelően arra a következtetésre juthatunk, hogy előnyben kell részesítenünk egy TreeSet ha kevés a memória, és ha olyan elemekhez szeretnénk hozzáférni, amelyek természetes sorrendjük szerint viszonylag közel vannak egymáshoz.

Ha az adatokat a merevlemezről kell olvasni (amelynek késleltetési ideje nagyobb, mint a gyorsítótárból vagy a memóriából olvasott adatoknak), akkor inkább TreeSet mivel nagyobb lokalitása van

17. Következtetés

Ebben a cikkben arra összpontosítunk, hogy megértsük a szabvány használatát TreeSet megvalósítás Java-ban. Láttuk annak célját és mennyire hatékony a használhatóság szempontjából, tekintettel arra, hogy képes elkerülni az ismétléseket és az elemek rendezését.

Mint mindig, a kódrészletek is megtalálhatók a GitHubon.