11.8 Mengen (Sets)
 
Eine Menge ist eine (erste einmal) ungeordnete Sammlung von Elementen. Jedes Element darf nur einmal vorkommen. Für Mengen sieht die Java-Bibliothek die Schnittstelle java.util.Set vor. Sie definiert neben Operationen für Anfrage und Einfügen von Elementen auch Funktionen für Schnitt und Vereinigung von Mengen.
interface java.util.Set<E>
extends Collection<E>
|
|
boolean add( E o )
Setzt o in die Menge, falls es dort noch nicht vorliegt. Liefert true bei erfolgreichem Einfügen. |
|
|
boolean addAll( Collection c )
Fügt alle Elemente von c in das Set ein und liefert true bei erfolgreichem Einfügen. Ist c ein anderes Set, so steht addAll() für die Mengenvereinigung. |
|
|
void clear()
Löscht das Set. |
|
|
boolean contains( Object o )
Ist das Element o in der Menge? |
|
|
boolean containsAll( Collection c )
Ist c Teilmenge von Set? |
|
|
boolean isEmpty()
Ist das Set leer? |
|
|
Iterator<E> iterator()
Gibt einen Iterator für das Set zurück. |
|
|
boolean remove( Object o )
Löscht o aus dem Set, liefert true bei erfolgreichem Löschen. |
|
|
boolean removeAll( Collection<?> c )
Löscht alle Elemente der Collection aus dem Set und liefert true bei erfolgreichem Löschen. |
|
|
boolean retainAll( Collection c )
Bildet die Schnittmenge mit c. |
|
|
int size()
Gibt die Anzahl der Elemente in der Menge zurück. |
|
|
Object[] toArray()
Erzeugt zunächst ein neues Feld, wo alle Elemente der Menge Platz finden, und kopiert anschließend die Elemente in das Feld. |
|
|
<T> T[] ziel toArray( T[] a )
Ist das übergebene Feld groß genug, dann werden alle Elemente der Menge in das Feld kopiert. Ist das Feld zu klein, wird ein neues Feld vom Typ T angelegt, alle Elemente vom Set in der Array kopiert und zurückgegeben. |
Aus Object werden equals() und hashCode() korrekt implementiert.
Obacht muss der Eigenschaft geschenkt werden, dass die Elemente immutable bleiben. Zum einen sind sie nach einer Änderung vielleicht nicht wieder zu finden, und zum Zweiten können so Elemente doppelt in der Menge vorkommen, was der Philosophie der Schnittstelle widerspricht.
11.8.1 HashSet
Ein java.util.HashSet verwaltet die Elemente in einer schneller Hash-basierten Datenstruktur. Dadurch sind die Elemente schnell einsortiert und schnell zu finden. Falls eine Sortierung nötig ist, müssen die Elemente nachträglich sortiert werden.
class java.util.HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, Serializable
|
|
|
HashSet()
Erzeugt ein neues HashSet-Objekt mit 16 freien Plätzen und einem Füllfaktor von 0.75. |
|
|
HashSet( Collection<? extends E> c )
Erzeugt ein neues Set aus der Menge gegebener Elemente. |
|
|
HashSet( int initialCapacity )
Erzeugt ein neues HashSet mit einer gegebenen Anzahl freier Plätze und dem Füllfaktor von 0.75. |
|
|
HashSet(int initialCapacity, float loadFactor)
Erzeugt ein neues leeres HashSet mit einer Startkapazität und einem gegebenen Füllfaktor. |
Die Startgröße ist für die Performanz wichtig. Ist die Größe zu klein gewählt, so muss die Datenstruktur bei neu hinzugefügten Elementen vergrößern – hier unterscheidet sich die HashSet nicht von der HashMap. Im Übrigen basiert HashSet auf HashMap.
11.8.2 TreeSet – die Menge durch Bäume
Die Klasse java.util.TreeSet implementiert ebenfalls wie HashSet die Set-Schnittstelle, verfolgt aber eine andere Implementierungs-Strategie. Ein TreeSet verwaltet die Elemente immer sortiert. (Intern werden die Elemente in einem balancierten Binärbaum gehalten). Speichert TreeSet ein neues Element, so fügt TreeSet das Element automatisch sortiert in die Datenstruktur ein. Das kostet zwar etwas mehr Zeit als ein HashSet, doch diese Sortierung ist dauerhaft. Daher ist es auch nicht zeitaufwändig, alle Elemente geordnet auszugeben. Die Suche nach einem einzigen Element ist aber etwas langsamer als im HashSet. Der Begriff »langsamer« muss jedoch relativiert werden. Die Suche ist logarithmisch und daher nicht wirklich »langsam«. Beim Einfügen muss bei bestimmten Konstellationen eine Reorganisation des Baumes in Kauf genommen werden, was die Einfügezeit verschlechtert. Doch auch beim Re-Hashing gibt es diese Kosten, die dort jedoch durch die passende Startgröße vermieden werden kann.
class java.util.TreeSet<E>
extends AbstractSet<E>
implements SortedSet<E>, Cloneable, Serializable
|
|
|
TreeSet()
Erzeugt ein neues leeres TreeSet. |
|
|
TreeSet( Collection<? extends E> c )
Erzeugt ein neues TreeSet aus der gegebenen Collection. |
|
|
TreeSet( Comparator<? super E> c )
Erzeugt ein leeres TreeSet mit einem gegebenen Comparator, der für die Sortierung der internen Datenstruktur die Vergleiche übernimmt. |
|
|
TreeSet( SortedSet<E> s )
Erzeugt ein neues TreeSet und übernimmt alle Elemente von s und auch die Sortierung von s. |
TreeSet implementiert SortedSet und damit die folgenden Funktionen
public interface java.util.SortedSet<E>
extends Set<E>
|
|
|
E first()
Liefert das erste Element in der Liste. |
|
|
E last()
Liefert das größte Element. |
|
|
Comparator<? super E> comparator()
Liefert den mit dem Set verbundenen Comparator. Die Rückgabe kann null sein, wenn die Objekte sich mit Comparable selbst vergleichen können. |
|
|
SortedSet<E> headSet( E toElement )
Liefert eine Teilmenge von Elementen, die echt kleiner als toElement ist. |
|
|
SortedSet<E> tailSet(E fromElement)
Liefert eine Teilmenge mit Elementen, die größer oder gleich fromElement sind. |
|
|
SortedSet<E> subSet(E fromElement, E toElement)
Liefert eine Teilmenge im gewünschten Bereich. |
Anders als HashSet liefert der Iterator die Elemente aufsteigend sortiert. Davon profitieren auch die beiden Funktionen toArray() – implementiert in AbstractCollection –, denn sie nutzen den Iterator, um ein sortiertes Feld zurückzugeben.
Durch die interne sortierte Speicherung gibt es zwei ganz wichtige Bedingungen:
|
|
Die Elemente müssen sich vergleichen lassen. Kommt ein Kirchen-Objekt in das TreeSet und implementiert dieser nicht die Schnittstelle Comparable, löst TreeSet eine Ausnahme aus. |
|
|
Die Elemente müssen vom gleichen Typ sein. Wie sollte sich ein Kirchen-Objekt mit einem Staubsauger-Objekt vergleichen lassen? |
|
