Ú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.