13.3 Mengen (Sets)

Eine Menge ist eine (erst einmal) ungeordnete Sammlung von Elementen. Jedes Element darf nur einmal vorkommen. Für Mengen sieht die Java-Bibliothek die Schnittstelle java.util.Set vor. Beliebte implementierende Klassen sind:

• HashSet: Schnelle Mengenimplementierung durch Hashing-Verfahren (dahinter steckt die HashMap)
• TreeSet: Mengen werden durch balancierte Binärbäume realisiert, die eine Sortierung ermöglichen.
• LinkedHashSet: Schnelle Mengenimplementierung unter Beibehaltung der Einfügereihenfolge
• EnumSet: Eine spezielle Menge ausschließlich für Enum-Objekte
• CopyOnWriteArraySet: Schnelle Datenstruktur für viele lesende Operationen

Abbildung 13.3: UML-Diagramm der Schnittstelle List

13.3.1 Ein erstes Mengen-Beispiel

Das folgende Programm analysiert einen Text und erkennt Städte, die vorher in eine Datenstruktur eingetragen wurden. Alle Städte, die im Text vorkommen, werden gesammelt und später ausgegeben.

Listing 13.3: com/tutego/insel/util/set/WhereHaveYouBeen

package com.tutego.insel.util.set;

import java.text.BreakIterator;
import java.util.*;

public class WhereHaveYouBeen
{
  public static String join( Iterable<?> iterable )
  {
    StringBuilder result = new StringBuilder();
    for ( Object o : iterable )
    {
      if ( result.length() != 0 )
        result.append( ", " );
      result.append( o.toString() );
    }
    return result.toString();
  }

  public static void main( String[] args )
  {
    // Menge mit Städten aufbauen

    Set<String> allCities = new HashSet<String>();
    allCities.add( "Sonsbeck" );
    allCities.add( "Düsseldorf" );
    allCities.add( "Manila" );
    allCities.add( "Seol" );
    allCities.add( "Siquijor" );

    // Menge für besuchte Städte aufbauen

    Set<String> visitedCities = new TreeSet<String>();

    // Satz parsen und in Wörter zerlegen. Alle gefundenen Städte
    // in neue Datenstruktur aufnehmen

    String sentence = "Von Sonsbeck fahre ich nach Düsseldorf und fliege nach Manila.";
    BreakIterator iter = BreakIterator.getWordInstance();
    iter.setText( sentence );

    for ( int first = iter.first(), last = iter.next();
          last != BreakIterator.DONE;
          first = last, last = iter.next() )
    {
      String word = sentence.subSequence( first, last ).toString();
      if ( allCities.contains( word ) )
        visitedCities.add( word );
    }

    // Kleine Statistik

    System.out.println( "Anzahl besuchter Städte: " + visitedCities.size() );
    System.out.println( "Anzahl nicht besuchter Städte: " +
                        (allCities.size() – visitedCities.size()) );
    System.out.println( "Besuchte Städte: " + join( visitedCities ) );
    Set<String> unvisitedCities = new TreeSet<String>( allCities );
    unvisitedCities.removeAll( visitedCities );
    System.out.println( "Unbesuchte Städte: " + join( unvisitedCities ) );
  }
}

Insgesamt kommen drei Mengen im Programm vor:

• allCities speichert alle möglichen Städte. Die Wahl fällt auf den Typ HashSet, da die Menge nicht sortiert sein muss, Nebenläufigkeit kein Thema ist und HashSet eine gute Zugriffszeit bietet.
• Ein TreeSet visiteCities merkt sich die besuchten Städte. Auch dieses Set ist schnell, aber hat den Vorteil, dass es die Elemente sortiert hält. Das ist später hübsch in der Ausgabe.
• Um alle nicht besuchten Städte herauszufinden, berechnet das Programm die Differenzmenge zwischen allen Städte und besuchten Städten. Es gibt in der Schnittstelle Set keine Methode, die das direkt macht, genau genommen gibt es keine Operation in Set, die den Rückgabetyp Set oder Collection hat. Also können wir nur mit einer Methode wie removeAll() arbeiten, die aus der Menge aller Städte die besuchten entfernt, um zu denen zu kommen, die noch nicht besucht wurden. Das »Problem« der removeAll()-Methode ist aber ihre zerstörerische Art – die Elemente werden genau aus der Menge gelöscht. Da die Originalmenge jedoch nicht verändert werden soll, kopieren wir alle Städte in einen Zwischenspeicher (unvisitedCities) und löschen aus diesem Zwischenspeicher, was die Originalmenge unangetastet lässt.

13.3.2 Methoden der Schnittstelle Set

Eine Mengenklasse deklariert neben Operationen für die Anfrage und das Einfügen von Elementen auch Methoden 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<? extends E> 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 eine 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, in dem alle Elemente der Menge Platz finden, und kopiert anschließend die Elemente in das Feld.
• <T> T[] 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, und alle Elemente werden vom Set in das Array kopiert und zurückgegeben.

In der Schnittstelle Set werden die aus Object stammenden Methoden equals() und hashCode() mit ihrer Funktionalität bei Mengen in der API-Dokumentation präzisiert.

Ihr Kommentar

Wie hat Ihnen das <openbook> gefallen? Wir freuen uns immer über Ihre freundlichen und kritischen Rückmeldungen.