Et sett er ganske enkelt en samling unike gjenstander. Unik betyr at ingen to objekter kan ha samme verdi(er). Avhengig av implementeringen av settet, kan det bestilles eller ikke. Java-settet, som en abstrakt datatype (ADT), har noen få nøkkeloperasjoner (der T representerer en hvilken som helst datatype, f.eks. int, streng eller et hvilket som helst klasseobjekt):
boolean add(T item): returnerer true hvis elementet er lagt til settet, og usant hvis elementet allerede var i settet.
boolean remove(T item): returnerer true hvis varen ble fjernet fra settet og falsk ellers (hvis varen ikke var i settet).
boolean contains(T item): returnerer true hvis varen er i settet og usann ellers.
boolean isEmpty(): returnerer sant hvis settet er tomt og usant ellers.
Settene i Java har ganske selvforklarende funksjonssignaturer (som de burde). Hvis du legger til to identiske elementer i et sett, vil bare det første elementet være i settet. Alle påfølgende forsøk på å legge til det samme elementet vil bli ignorert med mindre elementet først fjernes. En av de mest brukte settoperasjonene er å sjekke om en vare er innenfor et gitt sett. Funksjonen contains()gir en flott kjøretid for dette: O(1) eller O(log n) tidskompleksitet avhengig av om implementeringen som brukes er en HashSeteller enTreeSet, henholdsvis. Så hva kan et sett brukes til? Vel, hvis du noen gang trenger å holde styr på mange forskjellige objekter - som IDer, navn eller andre unike identifikatorer - og ofte sjekke om et element finnes i en slik samling, er et sett sannsynligvis et godt valg. Her er et eksempel på bruk av et sett: Tenk deg at du har en liste over Studentobjekter som representerer alle elevene i en gitt klasse. Hver Studentkan ha et unikt navn (streng) og karakter (int) for denne klassen. Hvis du ønsker å referere til en liste over alle A-elever (karakter >=90) ofte, ville det være kjedelig å gå gjennom denne listen og sjekke hver elevs karakter hver gang. I stedet kan du bruke en HashSetav strenger som holder styr på alle A-elevene i klassen, som sådan:
Hver gang elevenes karakterer oppdateres, kan du enkelt sjekke om studentens nye karakter er større enn eller lik 90 eller ikke.
Hvis ja, legg dem til i settet med A-elever ved hjelp avadd()
Hvis de allerede var A-student, blir denne operasjonen ganske enkelt ignorert.
Hvis ikke, fjern dem fra settet med A-studenter som brukerremove()
Hvis de ikke var en A-student på dette tidspunktet, blir denne operasjonen ganske enkelt ignorert.
Med et slikt system vil du alltid ha et oppdatert sett med alle 'A'-elever i klassen din. Hvis du ville sjekke om Johnny Appleseed gjorde det bra i klassen din, kunne du enkelt gjøre det ved å ringe contains(“Johnny Appleseed”)på settet. Selvfølgelig er dette bare ett eksempel på en brukssituasjon for et sett, og dette spesifikke problemet med å holde styr på A-elever kan løses på andre måter.
Implementeringer: HashSet i Java og Java TreeSet eksempler
Både HashSeti Java og TreeSeti Java kommer i java.utils package. Du kan importere dem som sådan:
// imports everything from Java's util package, including HashSet and TreeSet
import java.util.*;
eller
import java.util.HashSet; // imports only the Java HashSet
import java.util.TreeSet; // imports only the Java TreeSet
Den viktigste forskjellen mellom Java HashSetog Java TreeSeter at den TreeSeter sortert, mens den HashSetikke er det. Dette er grunnen til at den TreeSethar O(log n) tidskompleksitet for nøkkeloperasjoner, mens den HashSethar O(1) eller konstant tidskompleksitet; må TreeSetopprettholde orden til enhver tid. I tillegg til nøkkelsettoperasjonene nevnt tidligere, har både HashSetog TreeSeti Java noen andre nyttige funksjoner:
void clear(): sletter settet med alle objekter.
int size(): returnerer antall objekter i settet.
Object clone(): returnerer en grunn kopi av settet.
Iterator iterator(): returnerer en iterator til settet, starter ved det første objektet.
Du kan tenke deg å finne bruksområder for disse funksjonene i eksempelet "liste over A-studenter": du kan ringe size()hvis du vil se hvor mange A-studenter du har, eller clear()hvis du vil slette listen på slutten av semesteret. Du kan bruke clone()til å opprette og beholde en klon av listen over A-studenter på et bestemt tidspunkt, for eksempel under midtveisrapporter (på denne måten holder ikke klonen seg oppdatert sammen med originalen).
Eksempel på Java HashSet
Her er et kort eksempel på en HashSetav Strings som brukes i Java:
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"));
}
}
Utgang: --------
[Collin, Bob, Abigail]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Java TreeSet eksempel
Java sett eksempel kan hjelpe deg å forstå teorien. Her er det korte eksemplet på en TreeSetav Strings som brukes i Java:
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());
}
}
Utgang: -------
[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