Java Collection Framework
Implementierungen: Set
Willemers Informatik-Ecke
LinkedList Java Map

Ein Set enthält eine Menge von Elementen, von denen keines doppelt auftreten darf. In diesem Sinne bildet es eine mathematische Menge ab.

Implementiert wird Set durch HashSet, TreeSet und LinkedHashSet.

Zwischenfrage: Was ist ein Hash?

Ein Hash dient dazu, möglichst schnell an Informationen zu gelangen. Während der Mensch spontan die Daten ordnen würde, geht Hash einen anderen Weg. Stellen wir uns vor, wir sollten Städte anhand ihres Namens wiederfinden. Dann ginge ein Hash so vor, dass er die Quersumme der Buchstaben bildet und an dieser Position die Information ablegt. Liegt dort schon eine Stadt, so wird eine weitere Quersumme über die Zahl gebildet und die Stadt dort abgelegt. Ist dort auch schon eine Stadt, wird der Vorgang solange wiederholt, bis ein Platz gefunden wurde.

Quersummen werden tatsächlich nicht verwendet, weil diese sehr schnell in ihrem Bereich schrumpfen. Stattdessen verwendet man Funktionen, die dafür sorgen, dass die Streuung groß ist. Während eine binäre Suche nach einer Zahl im Bereich bis 1000 bereits zehn Zugriffe benötigt, ist ein Hash in der Regel deutlich schneller. Der einzige Haken: Die Daten sind nicht sortiert abgelegt.

Lottozahlen

Das folgende Programm sorgt dafür, dass sechs zufällige Lottozahlen gezogen werden. Der TreeSet sorgt dafür, dass es keine Doppelziehung gibt und dass die Zahlen in aufsteigender Reihenfolge angezeigt werden.
java.util.Random zufall = new java.util.Random();
Set<Integer> lotto = new TreeSet<>();
while (lotto.size()<6) {
    lotto.add(zufall.nextInt(49) + 1);            
}
for (Integer zahl : lotto) {
    System.out.println(zahl);
}
Die Schleife läuft so lange im Set noch nicht sechs Zahlen angekommen sind. Es wird immer wieder eine zufällige Zahl zwischen 1 und 49 hinzugefügt, außer natürlich, wenn es sie schon gibt. Da Set durch TreeSet implementiert ist, werden die Elemente in aufsteigender Reihenfolge ausgegeben. Die for-Schleife ist die spezielle Variante, die Elemente einer Menge ausgibt, also quasi ein foreach.

Wortmenge

Als Beispiel werden einfache Sätze von einem Programm in einem Set abgelegt. Dabei werden doppelte Worte entfallen. Das folgende Beispiel nutzt den booleschen Rückgabewert von add um die Anzahl der Doppelungen zu zählen.
import java.util.*;

public class EntDoppler {
    public static void main(String[] args) {
        Set s = new TreeSet(); // hier HashSet, TreeSet und LinkedHashSet probieren!
        int doppelte = 0;
        doppelte +=  s.add("das")?0:1;  // Fragezeichenoperator!
        doppelte +=  s.add("buch")?0:1; // Nur erhöhen, wenn eine Dopplung vorliegt.
        doppelte +=  s.add("das")?0:1;
        doppelte +=  s.add("das")?0:1;
        doppelte +=  s.add("java")?0:1;
        doppelte +=  s.add("beschreibt")?0:1;
        System.out.println("Doppelte: " + doppelte);
        System.out.println("Anzahl Einzelne: " + s.size() + " und zwar "  + s);
    }
}
Bei der Erzeugung des Sets kann festgelegt werden, welche Implementierung verwendet wird. Hier kann schnell getestet werden, wie sich die Ergebnisse auswirken, wenn unterschiedliche Implementierungen gewählt werden. In der letzten Zeile wird der Inhalt des Sets ausgegeben und so zeigen die folgenden drei Zeilen die Ergebnisse von Hashset, TreeSet und LinkedHashSet.
beschreibt, das, buch, java
beschreibt, buch, das, java
das, buch, java, beschreibt
Das Ergebnis des HashSet erscheint völlig chaotisch. TreeSet liefert eine alphabetisch sortierte Reihenfolge. LinkedHashSet behält die Reihenfolge der Einfügung bei.

Ein Wort zu der Kapazität des HashSet. Wenn Sie abschätzen können, wie groß der Container wird, können Sie die Kapazität als Parameter angeben.

Set meinSet = new HashSet(64);
Der Vorgabewert ist 16. Verwenden Sie einen zu großen Speicher, vergeuden Sie Zeit und Speicherplatz. Ist die Kapazität zu klein, kommt es zu Zeitverlusten durch das notwendige Umkopieren des Sets.