15.5 Die Collection des Typs Set
15.5.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, daß sie kein Element doppelt einfügen und damit insgesamt
die Integritätsbedingung einer Menge erhalten.
Ein weiterer Unterschied zu List
ist, daß 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, daß 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, daß
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. |
|
|
|
15.5.2 Implementierungen
Das Set-Interface
wird im JDK nur von den Klassen HashSet
und AbstractSet
implementiert. Die abstrakte Implementierung dient lediglich als Basisklasse
für eigene Ableitungen. In der voll funktionsfähigen HashSet-Implementierung
werden die Elemente intern in einer HashMap
gespeichert. 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 Lottotips ansehen. Ein ähnliches
Beispiel gibt es in Listing 16.1.
Dort wird ein BitSet
verwendet, um doppelte Zahlen zu verhindern.
001 /* Listing1506.java */
002
003 import java.util.*;
004
005 public class Listing1506
006 {
007 public static void main(String[] args)
008 {
009 HashSet set = new HashSet(10);
010 int doubletten = 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 ++doubletten;
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 Doubletten: " + doubletten);
024 }
025 }
|
Listing1506.java |
Listing 15.6: Generierung eines Lottotips 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 einen Set
keine Elemente eingefügt werden können, die bereits darin
enthalten sind, ist dafür gesorgt, daß jede Zahl nur einmal
im Tip auftaucht. Der Zähler doubletten
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 Doubletten: 2