18.3    Assoziative Speicher 

Ein assoziativer Speicher verbindet einen Schlüssel mit einem Wert. Java bietet für Datenstrukturen dieser Art die allgemeine Schnittstelle Map mit wichtigen Operationen wie put(key, value) zum Aufbau einer Assoziation und get(key) zum Erfragen eines assoziierten Werts.

 

18.3.1    Die Klassen HashMap und TreeMap 

Die Java-Bibliothek implementiert assoziativen Speicher mit einigen Klassen, wobei wir unser Augenmerk zunächst auf zwei wichtige Klassen richten wollen:

• Eine schnelle Implementierung ist die Hash-Tabelle (engl. hashtable), die in Java durch java.util.HashMap implementiert ist. Vor Java 1.2 wurde java.util.Hashtable verwendet. Die Schlüsselobjekte müssen »hashbar« sein, also equals(…) und hashCode() konkret implementieren. Eine besondere Schnittstelle für die Elemente ist nicht nötig.

• Daneben existiert die Klasse java.util.TreeMap, die etwas langsamer im Zugriff ist, doch dafür alle Schlüsselobjekte immer sortiert hält. Sie sortiert die Elemente in einen internen Binärbaum ein. Die Schlüssel müssen sich in eine Ordnung bringen lassen, wozu etwas Vorbereitung nötig ist.

Map<String,String> aldiSupplier = new HashMap<>();

aldiSupplier.put( "Carbo, spanischer Sekt", "Freixenet" );

aldiSupplier.put( "ibu Stapelchips", "Bahlsen Chipsletten" );

aldiSupplier.put( "Ko-kra Katzenfutter", "felix Katzenfutter" );

aldiSupplier.put( "Küchenpapier", "Zewa" );

aldiSupplier.put( "Nuss-Nougat-Creme", "Zentis" );

aldiSupplier.put( "Pommes Frites", "McCain" );

Map<String,Number> num = new HashMap<>();

num.put( "zwei", 2 );    // Boxing durch Integer.valueOf(2)

num.put( "drei", 3.0 );  // Boxing durch Double.valueOf(3.0)

Während also bei den Assoziativspeichern nach dem Hashing-Verfahren eine hashCode()- und equals(…)-Methode bei den Schlüssel-Objekten essenziell ist, ist das bei den baumorientierten Verfahren nicht nötig – hier muss nur eine Ordnung zwischen den Elementen her, entweder mit Comparable oder Comparator.

Ein Assoziativspeicher arbeitet nur in eine Richtung schnell. Wenn etwa im Fall eines Telefonbuchs ein Name mit einer Nummer assoziiert wurde, kann die Datenstruktur die Frage nach einer Telefonnummer schnell beantworten. In die andere Richtung dauert es wesentlich länger, weil hier keine Verknüpfung besteht. Sie ist immer nur einseitig. Auf wechselseitige Beziehungen sind die Klassen nicht vorbereitet.

Abbildung 18.2     UML-Klassendiagramm der Schnittstelle Map

Die Klasse HashMap

Die Klasse HashMap eignet sich ideal dazu, viele Elemente unsortiert zu speichern und sie über die Schlüssel schnell wieder verfügbar zu machen. Das interne Hashing-Verfahren ist schnell, eine Sortierung der Schlüssel nach einem gegebenen Kriterium aber nicht möglich, ein Iterator wird auch eine undurchsichtbare Reihenfolge liefern.

class java.util.HashMap<K,V>

extends AbstractMap<K,V>

implements Map<K,V>, Cloneable, Serializable

• HashMap()
  
  Erzeugt eine neue Hash-Tabelle.

• HashMap(Map<? extends K,? extends V> m)
  
  Erzeugt eine neue Hash-Tabelle aus einer anderen Map.

Die Klasse TreeMap und die Schnittstelle SortedMap/NavigableMap

Eine TreeMap implementiert die Schnittstelle NavigableMap, die wiederum von der Schnittstelle SortedMap erbt, wobei diese wiederum Map erweitert. Eine NavigableMap sortiert die Elemente eines Assoziativspeichers nach Schlüsseln und bietet Zugriff auf das kleinste oder größte Element.

• Einige Methoden aus SortedMap: firstKey(), lastKey(). subMap(fromKey, toKey) und tailMap(fromKey, toKey) bilden Teilansichten des Assoziativspeichers.

• einige Methoden aus NavigableMap: pollFirstEntry(), pollLastEntry(), descendingMap()

Damit die Schlüssel in einer TreeMap sortiert werden können, gilt das Gleiche wie beim TreeSet: Die Elemente müssen eine natürliche Ordnung besitzen, oder ein externer Comparator muss die Ordnung festlegen.

class java.util.TreeMap<K,V>

extends AbstractMap<K,V>

implements NavigableMap<K,V>, Cloneable, Serializable

• TreeMap()
  
  Erzeugt eine neue TreeMap, die eine natürliche Ordnung von ihren Elementen erwartet.

• TreeMap(Comparator<? super K> comparator)
  
  Erzeugt eine neue TreeMap mit einem Comparator, sodass die Elemente keine natürliche Ordnung besitzen müssen.

• TreeMap(Map<? extends K,? extends V> m)
  
  Erzeugt eine TreeMap mit einsortierten Elementen aus m, die eine natürliche Ordnung besitzen müssen.

• TreeMap(SortedMap<K,? extends V> m)
  
  Erzeugt eine TreeMap mit einsortierten Elementen aus m und übernimmt von m auch die Ordnung.

Um die Sortierung zu ermöglichen, ist der Zugriff etwas langsamer als über HashMap, aber mit dem Hashing-Verfahren lassen sich Elemente nicht sortieren.

 

18.3.2    Einfügen und Abfragen des Assoziativspeichers 

Wir haben gesagt, dass die Elemente des Assoziativspeichers Paare aus Schlüssel und zugehörigem Wert sind. Das Wiederfinden der Werte ist effizient nur über Schlüssel möglich.

Daten einfügen

Zum Hinzufügen von Schlüssel-Wert-Paaren dient die Methode put(key, value). Das erste Argument ist der Schlüssel und das zweite Argument der mit dem Schlüssel zu assoziierende Wert.

interface java.util.Map<K,V>

• V put(K key, V value)
  
  Speichert den Schlüssel und den Wert im Assoziativspeicher. Falls sich zu diesem Schlüssel schon ein Eintrag im Assoziativspeicher befand, wird der alte Wert überschrieben und der vorherige Wert zum Schlüssel zurückgegeben (das ist anders als bei Set, wo die Operation dann nichts tut). Ist der Schlüssel neu, liefert put(…) den Rückgabewert null. Das heißt auch, dass mit put(key, value) == null nicht klar ist, ob put(…) einen Wert überschreibt und der alte Wert null war oder ob noch kein Schlüssel-Wert-Paar in dem Assoziativspeicher lag.

• void putAll(Map<? extends K,? extends V> m)
  
  Fügt alle Schlüssel-Wert-Paare aus m in die aktuelle Map ein. Auch diese Methode überschreibt unter Umständen vorhandene Schlüssel.

Über alle Werte laufen

Die Default-Methode forEach(java.util.function.BiConsumer) läuft über alle Schlüssel-Wert-Paare und ruft einen BiConsumer auf – das ist eine funktionale Schnittstelle mit einer Methode, die zwei Parameter bekommt, nämlich Schüssel und Wert. Der Konsument kann die Daten dann auswerten.

Map<String,Number> num = new HashMap<>();

num.put( "zwei", 2 );

num.put( "drei", 3.0 );

BiConsumer<String,Number> action =

    (key, value) -> System.out.println( key + "=" + value );

num.forEach( action );

Assoziierten Wert erfragen

Um wieder ein Element auszulesen, deklariert Map die Operation get(key). Das Argument identifiziert das zu findende Objekt über den Schlüssel, indem dasjenige Objekt aus der Datenstruktur herausgesucht wird, das im Sinne von equals(…) mit dem Abfrageobjekt gleich ist. Wenn das Objekt nicht vorhanden ist, ist die Rückgabe null. Allerdings kann auch null der mit einem Schlüssel assoziierte Wert sein, da null als Wert durchaus erlaubt ist.

Map<String,Number> num = new HashMap<>();

Number number = num.get( "zwei" );

if ( number != null )

  System.out.println( number.intValue() );

interface java.util.Map<K,V>

• V get(Object key)
  
  Liefert das mit dem entsprechenden Schlüssel verbundene Objekt. Falls kein passendes Objekt vorhanden ist, liefert die Methode null.

• default V getOrDefault(Object key, V defaultValue)
  
  Existiert zum Schlüssel key ein assoziierter Wert, so wird dieser zurückgegeben, andernfalls der vorgegebene defaultValue.

Existiert der Schlüssel, existiert der Wert?

Mit get(…) kann nicht wirklich sicher das Vorhandensein eines Schlüssels getestet werden, da mit einem Schlüssel null assoziiert sein kann – das gilt zum Beispiel für HashMap, in der null als Schlüssel und Wert erlaubt sind. Eine sichere Alternative bietet die Methode containsKey(…), die true zurückgibt, wenn ein Schlüssel in der Tabelle vorkommt.

Im Gegensatz zu get(…) und containsKey(…), die das Auffinden eines Werts bei gegebenem Schlüssel erlauben, lässt sich auch nur nach den Werten ohne Schlüssel suchen. Dies ist allerdings wesentlich langsamer, da alle Werte der Reihe nach durchsucht werden müssen. Die Klasse bietet hierzu containsValue(…) an. Wir können uns auch alle assoziierten Werte geben lassen und dann Prüfungen durchführen.

interface java.util.Map<K,V>

• boolean containsKey(Object key)
  
  Liefert true, falls der Schlüssel im Assoziativspeicher vorkommt. Den Vergleich auf Gleichwertigkeit führt HashMap mit equals(…) durch. Demnach sollte das zu vergleichende Objekt diese Methode aus Object passend überschreiben. hashCode() und equals(…) müssen miteinander konsistent sein. Aus der Gleichwertigkeit zweier Objekte unter equals(…) muss auch jeweils die Gleichheit von hashCode() folgen.

• boolean containsValue(Object value)
  
  Liefert true, falls der Assoziativspeicher einen oder mehrere Werte enthält, die mit dem Objekt value inhaltlich (also per equals(…)) übereinstimmen.