Een set is simpelweg een verzameling unieke objecten. Uniek betekent dat geen twee objecten dezelfde waarde(n) kunnen hebben. Afhankelijk van de uitvoering van de set wordt deze wel of niet besteld. De Java-set, als een abstract gegevenstype (ADT), heeft een paar sleutelbewerkingen (waarbij T staat voor elk gegevenstype, bijvoorbeeld int, String of een ander klasseobject):
boolean add(T item): retourneert true als het item met succes aan de set is toegevoegd, en false als het item al in de set zat.
boolean remove(T item): retourneert true als het item met succes uit de set is verwijderd en anders false (als het item niet in de set zat).
boolean contains(T item): retourneert waar als het item in de set zit en anders onwaar.
boolean isEmpty(): retourneert waar als de set leeg is en anders onwaar.
De sets in Java hebben vrij vanzelfsprekende functiehandtekeningen (zoals het hoort). Als je twee identieke items aan een set toevoegt, dan zit alleen het eerst toegevoegde item in de set. Alle volgende pogingen om hetzelfde item toe te voegen, worden genegeerd, tenzij het item eerst wordt verwijderd. Een van de meest gebruikte setbewerkingen is controleren of een item binnen een bepaalde set valt. De contains()functie geeft hiervoor een geweldige looptijd: O(1) of O(log n) tijdcomplexiteit, afhankelijk van of de gebruikte implementatie een HashSetof eenTreeSet, respectievelijk. Dus waar kan een set voor worden gebruikt? Welnu, als u ooit veel afzonderlijke objecten moet bijhouden, zoals ID's, namen of andere unieke identificatoren, en regelmatig moet controleren of een item in zo'n verzameling bestaat, dan is een set waarschijnlijk een goede keuze. Hier is een voorbeeld van een gebruiksvoorbeeld van een set: stel je voor dat je een lijst hebt met Studentobjecten die alle leerlingen in een bepaalde klas vertegenwoordigen. Elk Studentkan een unieke naam (string) en cijfer (int) hebben voor deze klas. Als je regelmatig naar een lijst van alle A-studenten (cijfer >=90) zou willen verwijzen, dan zou het vervelend zijn om door deze lijst te bladeren en elke keer het cijfer van elke student te controleren. In plaats daarvan zou je een tekenreeks kunnen gebruiken HashSetdie alle A-leerlingen in de klas bijhoudt, als volgt:
Elke keer dat de cijfers van de studenten worden bijgewerkt, kunt u eenvoudig controleren of het nieuwe cijfer van de student hoger is dan of gelijk is aan 90 of niet.
Zo ja, voeg ze dan toe aan de set van A-studenten met behulp vanadd()
Als ze al een A-student waren, wordt deze bewerking gewoon genegeerd.
Zo niet, verwijder ze dan uit de set van A-studenten dieremove()
Als ze op dit moment geen A-student waren, wordt deze bewerking gewoon genegeerd.
Met zo'n systeem heb je altijd een up-to-date set van alle 'A'-leerlingen in je klas. Wil je even checken of Johnny Appleseed het goed deed in jouw klas, dan kon dat heel eenvoudig door een bezoekje te brengen contains(“Johnny Appleseed”)aan de set. Dit is natuurlijk slechts één voorbeeld van een use case voor een set, en dit specifieke probleem van het bijhouden van A-studenten kan op andere manieren worden opgelost.
Implementaties: HashSet in Java en Java TreeSet-voorbeelden
Zowel de HashSetin Java als de TreeSetin Java komen in de java.utils package. U kunt ze als zodanig importeren:
// imports everything from Java's util package, including HashSet and TreeSet
import java.util.*;
of
import java.util.HashSet; // imports only the Java HashSet
import java.util.TreeSet; // imports only the Java TreeSet
Het belangrijkste verschil tussen Java HashSeten Java TreeSetis dat het TreeSetis gesorteerd, terwijl het HashSetniet is. Dit is de reden waarom het TreeSetO(log n) tijdcomplexiteit heeft voor sleutelbewerkingen, terwijl het HashSetO(1) of constante tijdcomplexiteit heeft; de TreeSetmoet te allen tijde de orde handhaven. Naast de eerder genoemde bewerkingen voor het instellen van toetsen, hebben zowel de HashSeten TreeSetin Java een paar andere handige functies:
void clear(): wist de set van alle objecten.
int size(): geeft het aantal objecten in de set terug.
Object clone(): retourneert een ondiepe kopie van de set.
Iterator iterator(): retourneert een iterator naar de set, beginnend bij het eerste object.
U kunt zich voorstellen hoe u deze functies kunt gebruiken in het voorbeeld "lijst van A-studenten": u kunt bellen size()als u wilt zien hoeveel 'A'-studenten u had, of clear()als u de lijst aan het einde van het semester wilt wissen. Je zou kunnen gebruiken clone()om een kloon te maken en te bewaren van de lijst met A-studenten op een specifiek tijdstip, zoals tijdens tussentijdse rapporten (op deze manier blijft de kloon niet up-to-date samen met het origineel).
Java HashSet-voorbeeld
Hier is een kort voorbeeld van een HashSetvan Strings die in Java wordt gebruikt:
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"));
}
}
Uitvoer: --------
[Collin, Bob, Abigail]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Java TreeSet-voorbeeld
Java-voorbeeld kan u helpen de theorie te begrijpen. Hier is het korte voorbeeld van een TreeSetvan Strings die in Java wordt gebruikt:
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());
}
}
Uitvoer: -------
[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