Titel | Inhalt | Suchen | Index | DOC | Handbuch der Java-Programmierung, 3. Auflage
<< | < | > | >> | API | Kapitel 15 - Collections II

## 15.5 Die Collection des Typs Set

- 15.5 Die Collection des Typs Set
  - 15.5.1 Abstrakte Eigenschaften
  - 15.5.2 Implementierungen

### 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 | DOC | Handbuch der Java-Programmierung, 3. Auflage, Addison Wesley, Version 3.0
<< | < | > | >> | API | © 1998-2002 Guido Krüger, http://www.javabuch.de