Titel   Inhalt   Suchen   Index   API  Go To Java 2, Zweite Auflage, Handbuch der Java-Programmierung
 <<    <     >    >>  Kapitel 15 - Collections II

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.

 Warnung 

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

 Titel   Inhalt   Suchen   Index   API  Go To Java 2, Zweite Auflage, Addison Wesley, Version 2.0
 <<    <     >    >>  © 2000 Guido Krüger, http://www.gkrueger.com