16.4 Die Collection des Typs Set
16.4.1 Abstrakte Eigenschaften
Ein Set
ähnelt der List,
erlaubt aber im Gegensatz zu dieser keine doppelten Elemente. Genauer
gesagt, in einem Set
darf es zu keinem Zeitpunkt zwei Elemente x
und y geben, für die x.equals(y)
wahr ist. Ein Set
entspricht damit im mathematischen Sinn einer Menge, in der
ja ebenfalls jedes Element nur einmal vorkommen kann. Ein Set
hat allerdings keine spezielle Schnittstelle, sondern erbt seine Methoden
von der Basisklasse Collection.
Die Unterschiede zu List
treten zutage, wenn man versucht, mit add
ein Element einzufügen, das bereits vorhanden ist (bei dem also
die equals-Methode
wie zuvor beschrieben true
ergibt). In diesem Fall wird es nicht erneut eingefügt, sondern
add
gibt false
zurück. Auch für die Methoden addAll
und den Konstruktor Set(Collection c)
gilt, dass sie kein Element doppelt einfügen und damit insgesamt
die Integritätsbedingung einer Menge erhalten.
Ein weiterer Unterschied zu List
ist, dass ein Set
keinen ListIterator,
sondern lediglich einen einfachen Iterator
erzeugen kann. Dessen Elemente haben keine definierte Reihenfolge.
Sie kann sich durch wiederholtes Einfügen von Elementen im Laufe
der Zeit sogar ändern.
 |
|
|
|
Besondere Vorsicht ist geboten, wenn ein Set
dazu benutzt wird, veränderliche Objekte
zu speichern (sie werden auch als mutable
bezeichnet). Wird ein Objekt, das in einem Set
gespeichert ist, so verändert, dass der equals-Vergleich
mit einem anderen Element danach einen anderen Wert ergeben könnte,
so gilt der komplette Set
als undefiniert und darf nicht mehr benutzt werden.
Zentrale Ursache für dieses Problem ist die Tatsache, dass Objektvariablen
intern als Zeiger auf die zugehörigen Objekte dargestellt
werden. Auf ein Objekt, das in einem Set
enthalten ist, kann somit auch von außen zugegriffen werden,
wenn nach dem Einfügen des Objekts noch ein Verweis darauf zur
Verfügung steht. Bei den in Java vordefinierten »kleinen«
Klassen wie String,
Integer
usw. ist das kein Problem, denn Objekte dieses Typs können nach
ihrer Konstruktion nicht mehr verändert werden (sie sind immutable).
Bei veränderlichen Objekten könnten dagegen im Set
enthaltene Elemente unbemerkt verändert und dessen Integrität
verletzt werden. |
|
|
|
16.4.2 Implementierungen
Das Set-Interface
wird im JDK beispielsweise von den Klassen HashSet,
TreeSet
und AbstractSet
implementiert. Die abstrakte Implementierung dient als Basisklasse
für weitere Ableitungen. In der HashSet-Implementierung
werden die Elemente intern in einer HashMap
gespeichert, im TreeSet
als balancierter Baum. Vor jedem Einfügen wird geprüft,
ob das einzufügende Element bereits in der HashMap
enthalten ist. Die Performance der Einfüge-, Lösch- und
Zugriffsfunktionen ist im Mittel konstant. Neben den oben erwähnten
Standardkonstruktoren besitzt die Klasse HashSet
zwei weitere Konstruktoren, deren Argumente direkt an den Konstruktor
der HashMap
weitergereicht werden:
HashSet(int initialCapacity)
HashSet(int initialCapacity, float loadFactor)
|
java.util.HashSet |
Wir wollen uns die Anwendung eines HashSet
am Beispiel der Generierung eines Lottotipps ansehen. Ein ähnliches
Beispiel gibt es in Listing 17.1.
Dort wird ein BitSet
verwendet, um doppelte Zahlen zu verhindern.
001 /* Listing1603.java */
002
003 import java.util.*;
004
005 public class Listing1603
006 {
007 public static void main(String[] args)
008 {
009 HashSet set = new HashSet(10);
010 int dubletten = 0;
011 //Lottozahlen erzeugen
012 while (set.size() < 6) {
013 int num = (int)(Math.random() * 49) + 1;
014 if (!set.add(new Integer(num))) {
015 ++dubletten;
016 }
017 }
018 //Lottozahlen ausgeben
019 Iterator it = set.iterator();
020 while (it.hasNext()) {
021 System.out.println(((Integer)it.next()).toString());
022 }
023 System.out.println("Ignorierte Dubletten: " + dubletten);
024 }
025 }
|
Listing1603.java |
Listing 16.3: Generierung eines Lottotipps mit HashSet
In diesem Listing wird ein HashSet
so lange mit Zufallszahlen zwischen 1 und 49 bestückt, bis die
Anzahl der Elemente 6 ist. Da in ein Set
keine Elemente eingefügt werden können, die bereits darin
enthalten sind, ist dafür gesorgt, dass jede Zahl nur einmal
im Tipp auftaucht. Der Zähler dubletten
wird durch den Rückgabewert false
von add
getriggert. Er zählt, wie oft eine Zahl eingefügt werden
sollte, die bereits enthalten war. Die Ausgabe des Programms könnte
beispielsweise so aussehen:
29
17
16
35
3
30
Ignorierte Dubletten: 2