Mengen (Collection)

Mengen (Collection)

Das Java Collections Framework stellt mit der Schnittstelle Set<E> einen Behälter zur Verfügung der keine Elemente mehrfach enthält. Die Schnittstelle Set<E> stellt die folgenden Methoden für die unterschiedlichen Implementierungen zur Verfügung:

package java.util;
public interface Set<E> extends Collection<E> {
// Grundlegende Operationen
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element);
boolean remove(Object element);
Iterator<E> iterator(); // Massenoperationen boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean removeAll(Collection<?> c); boolean retainAll(Collection<?> c); void clear(); // Feld Operationen Object[] toArray(); <T> T[] toArray(T[] a); }

Neben der Schnittstelle Set<E> existiert auch eine Schnittstelle SortedSet<E> in der die Mengenelemente nach ihrer natürlichen oder einer definierten Ordnung sortiert sind.

package package java.util;
public interface SortedSet<E> extends Set<E> {
// Range-view
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement); // Endpoints E first(); E last(); // Comparator access Comparator<? super E> comparator(); } 

Als konkrete Implementierungen können die folgenden Klassen benutzt werden:

Klasse TreeSet

Die Klasse TreeSet verwaltet alle Elemente in ihrer natürlichen Ordnung oder in der Ordnung die mit der Schnittstelle Comparator definiert wurde.

Die Kosten für die Zugriffsmethoden add(), remove(), contains() liegen bei O(log(n)).

Die Klasse TreeSet ist nicht synchronisiert.

Anwendungsfälle:

  • Man muß über die Menge mit einem bestimmten Schlüsselkriterium iterieren können
  • Die erhöhten Kosten für Einfügen und Entfernen von Objekten sind nicht relevant.

Klasse EnumSet

Die Klasse EnumSet ist eine Spezialimplementierung für Aufzählungen (enum). Der Aufzählungstyp enum ist extrem effizient mit Hilfe von Bitvektoren implementiert. Die Klasse EnumSet unterstützt extrem effiziente Mengenoperationen auf einem gegegebenen Aufzählungstyp.

Die Iteratoren aller anderen Collections sind "fail safe". Das heißt sie werfen eine  ConcurrentModificationException Ausnahme falls die Collection an mehreren Stellen gleichzeitig modifiziert wird. Dies ist nicht der Fall bei den Iteratoren der Klasse EnumSet. Ihre Iteratoren sind nur "weakly consistent" (siehe Dokumentation im API).

Klasse HashSet

Die Klasse HashSet verwendet intern eine Implementierung einer HashMap. Die Klasse HashSet hat keine Ordnung der Elemente. Das bedeutet, dass beim Iterieren über die Menge die Elemente der Menge nicht in einer sortierten Reihenfolge präsentiert werden. Es gibt nicht einmal eine Garantie, dass bei mehrfachem Iterieren über die Menge die Reihenfolge konstant ist.

Der Zugriff der Methoden add(), remove(), contains(), size() haben einen konstanten Aufwand. Diese Operationen sind bei großen Mengen schneller als die Methoden der Klasse TreeSet.

Anwendungsfälle:

  • Einfüge-, Entfernungs- und Leseoperationen sollen sehr effizient sein
  • Die Ordnung der Menge nach einem Schlüsselkriterium spielt keine Rolle

 

Stefan Schneider Sat, 05/14/2011 - 15:36