A készlet egyszerűen egyedi tárgyak gyűjteménye. Az egyedi azt jelenti, hogy nincs két objektumnak azonos értéke(i). A készlet kivitelezésétől függően megrendelhető vagy nem. A Java halmaznak, mint absztrakt adattípusnak (ADT) van néhány kulcsművelete (ahol a T bármilyen adattípust jelöl, pl. int, String vagy bármely osztályobjektum):
boolean add(T item): igazat ad vissza, ha az elemet sikeresen hozzáadta a készlethez, és hamis értéket, ha az elem már a készletben volt.
boolean remove(T item): igazat ad vissza, ha az elemet sikeresen eltávolították a készletből, és hamis értéket egyébként (ha az elem nem volt a készletben).
boolean contains(T item): igazat ad vissza, ha az elem benne van a halmazban, és hamis értéket egyébként.
boolean isEmpty(): igazat ad vissza, ha a halmaz üres, ellenkező esetben pedig false-t.
A Java-készletek meglehetősen magától értetődő függvényaláírásokkal rendelkeznek (ahogyan kell). Ha két azonos elemet ad hozzá egy készlethez, akkor csak az elsőként hozzáadott elem lesz a készletben. A rendszer figyelmen kívül hagyja az összes további próbálkozást ugyanazon elem hozzáadására, hacsak nem távolítja el először az elemet. Az egyik leggyakrabban használt halmazművelet annak ellenőrzése, hogy egy elem egy adott halmazon belül van-e. A contains()függvény kiváló futási időt biztosít ehhez: O(1) vagy O(log n) időbonyolultság attól függően, hogy a vagy a használt HashSetimplementációTreeSet, ill. Tehát mire használható egy készlet? Nos, ha valaha is nyomon kell követnie számos különböző objektumot – például azonosítókat, neveket vagy más egyedi azonosítókat –, és gyakran ellenőriznie kell, hogy létezik-e egy elem egy ilyen gyűjteményben, akkor valószínűleg jó választás lehet egy készlet. Íme egy példa egy halmaz használati esetére: Képzeljük el, hogy van egy objektumlistája, amely Studentegy adott osztály összes tanulóját reprezentálja. Mindegyiknek Studentegyedi neve (karakterlánc) és fokozata (int) lehet ehhez az osztályhoz. Ha gyakran szeretne hivatkozni az összes A tanuló listájára (>=90 osztályzat), akkor unalmas lenne végignézni ezt a listát, és minden alkalommal ellenőrizni minden tanuló osztályzatát. Ehelyett használhat egy HashSetkarakterláncot, amely nyomon követi az osztály összes A tanulóját:
Minden alkalommal, amikor a tanulók érdemjegyei frissülnek, egyszerűen ellenőrizheti, hogy a tanuló új érdemjegye nagyobb-e vagy egyenlő-e 90-el vagy sem.
Ha igen, adja hozzá őket az A tanulók halmazáhozadd()
Ha már A tanulók voltak, akkor ezt a műveletet egyszerűen figyelmen kívül hagyja.
Ha nem, akkor távolítsa el őket az A tanulók halmazábólremove()
Ha ezen a ponton nem A tanuló, akkor ezt a műveletet egyszerűen figyelmen kívül hagyja.
Egy ilyen rendszerrel mindig naprakész készlettel rendelkezne az osztály összes „A” tanulójáról. Ha ellenőrizni szeretné, hogy Johnny Appleseed jól teljesít-e az osztályában, egyszerűen megteheti, ha felhívja contains(“Johnny Appleseed”)a készüléket. Természetesen ez csak egy példa egy halmaz használati esetére, és az A tanulók nyomon követésének ez a sajátos problémája más módon is megoldható.
Megvalósítások: HashSet Java-ban és Java TreeSet példák
Mind a HashSetJava-ban, TreeSetmind a Java-ban a java.utils package. Így importálhatja őket:
// imports everything from Java's util package, including HashSet and TreeSet
import java.util.*;
vagy
import java.util.HashSet; // imports only the Java HashSet
import java.util.TreeSet; // imports only the Java TreeSet
A legfontosabb különbség a Java HashSetés a Java között TreeSetaz, hogy a TreeSetrendezve van, míg a HashSetnem. Ez az oka annak, hogy TreeSeta kulcsműveletekhez O(log n) időbonyolultságú, míg HashSetO(1) vagy állandó időbonyolultságú; a TreeSetrendet mindenkor fenn kell tartani. A korábban említett kulcskészlet-műveleteken kívül a HashSetés TreeSeta Java-ban is van még néhány hasznos funkció:
void clear(): törli az összes objektum halmazát.
int size(): a halmazban lévő objektumok számát adja vissza.
Object clone(): a készlet sekély másolatát adja vissza.
Iterator iterator(): egy iterátort ad vissza a halmazhoz, az első objektumtól kezdve.
Elképzelheti, hogy ezeknek a függvényeknek a felhasználását az „A hallgatók listája” példában találja meg: felhívhatja, size()ha látni szeretné, hogy hány „A” hallgatója van, vagy clear()ha törölni szeretné a listát a félév végén. Használhatja clone()az A-tanulók listájának klónjának létrehozását és megtartását egy adott időpontban, például félévközi jelentések során (ilyen módon a klón nem marad naprakész az eredetivel együtt).
Java HashSet példa
Íme egy rövid példa a Java-ban használt a HashSet-ra :String
import java.util.HashSet;
class HashSetDemo {
public static void main(String[] args)
{
// create a HashSet of Strings
HashSet<String> hs = new HashSet<String>();
// Add elements using the add() method
hs.add("Collin");
hs.add("Bob");
hs.add("Abigail");
// Duplicates will ignored; this statement is useless
hs.add("Collin");
System.out.println(hs);
System.out.println("Bob is in the set (T/F): " + hs.contains("Bob"));
System.out.println("Max is in the set (T/F): " + hs.contains("Max"));
}
}
Kimenet: --------
[Collin, Bob, Abigail]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Java TreeSet példa
A Java-készlet példa segíthet az elmélet megértésében. Íme egy rövid példa a Java-ban használt a TreeSetof s-re:String
import java.util.TreeSet;
class TreeSetDemo {
public static void main(String[] args)
{
// create a TreeSet of Strings
TreeSet<String> ts = new TreeSet<String>();
// Add elements using the add() method.
ts.add("Collin");
ts.add("Bob");
ts.add("Abigail");
// Duplicates will ignored; this statement is useless
ts.add("Collin");
// printing the set prints the names in alphabetical order!
System.out.println(ts);
System.out.println("Bob is in the set (T/F): " + ts.contains("Bob"));
System.out.println("Max is in the set (T/F): " + ts.contains("Max"));
System.out.println("Size of the set: " + ts.size());
ts.clear();
System.out.println("Size of the set after clear(): " + ts.size());
}
}
Kimenet: -------
[Abigail, Bob, Collin]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Size of the set: 3
Size of the set after clear(): 0
GO TO FULL VERSION