Die Collection II Part 2 / 3

Sets in der Programmiersprache Java

Sets oder auch Mengen sind in der Programmiersprache Java, Python, C# etc. die Menge an Elemente deren Reihenfolge vollkommen egal ist. Beispielsweise in der Mengenlehre, ein Teilgebiet der Mathematik, ist die Schreibweise der Elemente von einer Menge völlig Egal: 

M = {0, 1, 2, 3, 4} = {1, 2, 4, 3, 0} = etc.

Der Unterschied zur einer Liste wie zum Beispiel ArrayList, LinkedList,... etc. besteht darin, dass die Elemente keine bestimmte Reihenfolge haben. 

Die für Sets wichtigste Methoden lauten wie folgt:

public boolean isEmpty()

public iterator E iterator()

public boolean add(E e)

public boolean remove(Object o)

Die Methode public boolean isEmpty() überprüft, ob die Menge (Set) leer oder gefüllt ist. Falls die Menge (Set) gleich der Nullmenge ist, wird true ausgegeben. Wenn diese mindestens ein Element besitzt, wird false ausgegeben. Mit der Methode add(E e) wird ein Element hinzugefügt und mit remove ein Element mit dem jeweiligen Objekt entfernt.

In einem Set darf ein Element genau einmal vorkommen, das bedeutet, dass jedes Element in einem Set einzigartig ist. Beim Einfügen eines Elements in einem Set wird davor intern überprüft, ob dieses schon in der Menge enthalten ist. Sollte dies der Fall sein, so bleibt die Menge unverändert.

Zu den gängigsten Klassen, die das Interface Set implementieren gehören java.util.HashSet und java.util.TreeSet

HashSet:

Eine gängige Mengen-Klasse, die das Interface Set implementiert, ist die Klasse HashSet. Die Elemente werden in einer HashTabelle gespeichert, wodurch ein schneller Zugriff auf diese Elemente möglich ist.

Beispiel:

HashSet set = new HashSet();

Set.add(“JAVA“);

Set.add(2);

Set.add(“Enterprise“);

Set.add(“Enterprise“);  // Wird nicht nochmal hinzugefügt.

In der Klasse HashSet gibt es keine Methode, um auf ein Objekt der Menge direkt zugreifen zu können. Damit wir auf die Objekte zugreifen zu können, brauchen wir einen Iterator. Ein Iterator ist ein Zeiger, mit dem wir eine Datenstruktur iterieren können. Mit iterieren meinen wir die schrittweise durchlaufen. Ein Iterator bekommen wir, in dem wir die Methode iterator aufrufen.

Das Interface Iterator hat die folgenden Methoden:

public boolean hasNext()

public E next()

public void remove()

Die Methode hasNext() überprüft, ob ein Objekt in unserem HashSet vorhanden ist. Der iterator “läuft“ mit der Methode next zum nächsten Objekt und gibt dieses auch zurück. Die Methode remove entfernt das zuletzt “besuchte“ Objekt.

Möchte man zum Beispiel ein HashSet zweimal Durchsuchen, so muss man für jeden neuen Durchlauf einen neuen Iterator anfordern, da der Iterator nur “Vorwärz“ gehen kann. Sobald er am Ende angekommen ist, kann es sich nicht selber zurücksetzen.

Beispiel für die Verwendung eines Iterators:

Iterator it = set.iterator();

// HashSet wird mit dem Iterator durchlaufen

while(it.hasNext()) {

     String setText = (String) it.next();  System.out.println(setText);

}

//Next gibt das Aktuelle HashSet Objekt zurück und geht zum nächsten //über.

//Ausgabe der jeweiligen HashSet-Elements.

TreeSet:

Eine weitere Set-Klasse ist java.util.TreeSet. In diesem Set werden Objekte in einer Baumstruktur sortiert. Zum besseren Verständnis sieht die Baumstruktur wie folgt aus:

Das oben Abgebildete Baumstruktur besitzt drei Ebenen. Der Knoten in der ersten Ebene ist die Wurzel (root). Die Knoten in der zweiten Ebene werden als Äste (branches) bezeichnet, da sie noch Nachfolger haben. Die Knoten der dritten Ebene werden Blätter(leaves) genannt. Da in dem obigen Bild jeder Vorgänger maximal zwei Nachfolger besitzt, spricht man von einem Binärbaum. Alle Klassen, die in ein TreeSet eingefügt werden sollen, müssen das Interface Comparable und dessen Methode compareTo implementieren. Durch compareTo können Elemente miteinander vergleichen werden. Damit ein Vergleich überhaupt möglich ist, müssen die Objekte im TreeSet von selbem Datentyp sein.

Beispiel:

public class Punkt implements comparable {

     private int x;

     public int getX() {

          return x;

     }

     public void setX(int i) {

          x = i;

     }

     // Implementierte Methode aus dem Interface Comparable

     public int compareTo(Object compareObject) {

          // Rückgabewert

          int compareValue = -2;

          // Typumwandlung zur Klasse Punkt.

          Punkt comparePunkt = (Punkt)compareObject;

          //Vergleich auf Gleichheit

          if(this.x == comparePunkt.getX()) {

                compareValue = 0;

          }

          // Vergleich auf kleiner

          if(this.x < comparePunkt.getX()) {

                compareValue = -1;

          }

          // Vergleich auf größer

          if(this.x > comparePunkt.getX()) {

                compareValue = 1;

          }

          return compareValue;

     }

}

In dem obigen Beispiel haben wir eine Klasse namens Punkt, welches aus dem Interface comparable implementiert, definiert.

Dadurch müssen wir die Methode compareTo implementieren. Da unsere Klasse nur ein einfaches Attribut namens “x“ besitzt, können dessen Wert auf Gleichheit, größer als sowie kleiner als überprüfen, in dem wir diese mit dem Punkt-Objekte vergleichen. Die Implementiertung der Methode compareTo ist davon abhängig, welche Objekte wir vergleichen und welche wir ablegen wollen.

Wir stellen einen TreeSet, dem wir einige Punkte hinzufügen:

// neues TreeSet-Objekt

TreeSet tree = new TreeSet();

Punkt p1 = new Punkt();

p1.setX(12);

Punkt p2 = new Punkt();

p1.setX(13);

Punkt p3 = new Punkt();

p1.setX(11);

Punkt p4 = new Punkt();

p1.setX(13);

Punkt p5 = new Punkt();

p1.setX(61);

// Punkte werden im TreeSet hinzugefüht:

tree.add(p1);

tree.add(p2);

tree.add(p3);

tree.add(p4);

tree.add(p5);

System.out.println("Inhalt unseres TreeSets: ");

Iterator it = tree.iterator();

while(it.hasNext()) {

     Punkt punkt = new Punkt();

     System.out.println(punkt.getX());

}

Würden wir nicht das Interface Comparable innerhalb der Klasse Punkt implementiert, so wäre es nicht möglich, die Punkte p1 bis p5 dem TreeSet hinzufügen. Wie ihr es anhand der Ausgabe in der Konsole sehen könnt, werden die Punkte im Tree absteigend nach dem x-Wert ausgegeben. Der Wert “13“ wird nur einmal ausgegeben, obwohl wir zweimal ein Punkt mit dem x-Wert hinzugefügt haben. Dies liegt daran, dass beim Hinzufügen des vierten Punktes über die Compare Funktion eine Gleichheit der Elemente festgestellt wird. Da in dem Sets (Mengen) jedes Element einzigartig sein soll, wird der Punkt nicht mehrmals hinzugefügt beziehungsweise ausgegeben.