4.6Assoziative 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.

 

4.6.1Die 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.

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 entweder mit Comparable oder Comparator her.

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 4.4Klassendiagramm 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.

• 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.

• 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.

 

4.6.2Einfü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.

• 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 beim 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.

• default V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)
  Speichert ein neues Schlüssel-Wert-Paar, wobei der assoziierte Wert von einer Funktion zum Zeitpunkt des Einfügens berechnet wird. War mit dem alten Wert etwas assoziiert, wird der alte Wert zurückgegeben. Ein Sonderfall ist es, wenn die Funktion null liefert, dann passiert nichts, bzw. ein altes existierendes Schlüssel-Wert-Paar wird gelöscht.

• 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

Eine neue Default-Methode in Java ist forEach(java.util.function.BiConsumer); sie läuft über alle Schlüssel-Wert-Paare und ruft einen BiConsumer auf, das ist eine funktionale Schnittstelle mit einer Methode, die zwei Paramater bekommt, nämlich Schüssel und Wert. Der Consumer kann die Daten dann auswerten.

Intern greift die Methode auf entrySet() zurück, wir werden die Methode später vorstellen.

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.

• 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.

• boolean containsKey(Object key)
  Liefert true, falls der Schlüssel im Assoziativspeicher vorkommt. Den Vergleich auf Gleichheit 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 Gleichheit 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 inhaltlich (also per equals(…)) übereinstimmen.

Einträge ersetzen

Die Methode getOrDefault(Object key, V defaultValue) ist insofern interessant, als dass sie zwei Dinge tut: testen und in Abhängigkeit vom Ausgang des Tests eine Operation durchführen. Zum Austauschen bietet die Java-API seit Java 8 drei neue replace(…)-Methoden, die nach dem gleichen Prinzip funktionieren; es muss ein Element erst existieren, bevor es ersetzt werden kann.

• default V replace(K key, V value)
  Wenn es zu key schon einen assoziierten Wert gab, wird dieser überschrieben. Wenn mit key noch nichts assoziiert war, passiert nichts. Das ist der Unterschied zu put(…), das in jedem Fall ein Paar assoziiert.

• default boolean replace(K key, V oldValue, V newValue)
  Assoziiert key mit newValue genau dann, wenn key bisher mit oldValue assoziiert war.

• default void replaceAll(BiFunction<? super K,? super V,? extends V> function)
  Läuft über alle Schlüssel-Wert-Paare der Map, ruft die gegebene Funktion mit den Parametern Schlüssel und Wert auf und überschreibt den alten assoziierten Wert mit dem Ergebnis der Funktion.

Einträge löschen oder die ganze Map leeren

Zum Löschen eines Elements gibt es zwei Formen von remove(…), und zum Löschen der gesamten Map gibt es die Methode clear():

• V remove(Object key)
  Löscht den Schlüssel und seinen zugehörigen Wert. Wenn der Schlüssel nicht im Assoziativspeicher ist, so bewirkt die Methode nichts. Im letzten Atemzug wird noch der Wert zum Schlüssel zurückgegeben.

• default boolean remove(Object key, Object value)
  Löscht den Schlüssel mit dem Wert nur dann, wenn key auch mit value assoziiert ist und nicht mit etwas anderem. Die Rückgabe ist true, wenn der Wert gelöscht wurde. Die Methode ist neu seit Java 8.

• void clear()
  Löscht den Assoziativspeicher so, dass er keine Werte mehr enthält.

Map-Operationen in Abhängigkeit von (nicht-)existierenden Werten (ab Java 8)

Die Map-API hat seit Java 8 einige clevere Methoden, die mehrere Operationen zusammenfassen, wobei die Funktionsweise folgendem Bauplan entspricht: Ist ein assoziierter Wert zu einem Schlüssel (nicht) vorhanden, dann tue dies, sonst das.

• default V putIfAbsent(K key, V value)
  Testet zuerst, ob zu dem gegebenen Schlüssel key ein assoziierter Wert existiert, wenn ja, gibt es keine Änderung an der Datenstruktur, nur der alte assoziierte Wert wird zurückgegeben. Existiert kein assoziierter Wert, speichert die Datenstruktur den value zum Schlüssel. Die Rückgabe von putIfAbsent(…) ist null, falls es vorher keinen alten assoziierten Wert gab, andernfalls die Referenz vom alten Objekt (das auch null sein kann, wenn die Map auch null-Werte erlaubt), das jetzt durch den neuen Wert überschrieben wurde. Falls null als Wert in der Map erlaubt ist – wie etwa in HashMap –, so gilt eine Besonderheit: Ist ein existierender Schlüssel mit null assoziiert, dann würde putIfAbsent(…) den Wert null mit etwas anderem überschreiben.

• default V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)
  Vergleichbar mit putIfAbsent(…), nur nutzt diese Methode eine Berechnungsmethode statt eines festen Werts. Ein wichtiger Punkt ist, dass, wenn die Berechnungsfunktion null zurückgibt, nichts an dem Assoziativspeicher verändert wird und der alte Wert bleibt. Der Rückgabewert ist immer entweder der letzte assoziierte Wert oder der neue Eintrag, es sein denn, die mappingFunction liefert null. Die Methode lässt sich damit perfekt in einer Methodenkaskadierung der Art map.computeIfAbsent(…).methodeVonV(…) verwenden.

• default V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)
  Überschreibt den assoziierten Wert mit einem von der Funktion berechneten neuen Wert, wenn das Schlüssel-Wert-Paar existiert. Dann liefert die Methode den neuen Wert zurück. Zwei Sonderfälle sind zu unterscheiden: Falls es zu dem Schlüssel key keinen Wert gibt, macht computeIfPresent(…) nichts, und die Rückgabe ist null. Gibt es einen assoziierten Wert, doch die auf den Wert angewendete Funktion liefert null, wird das Schlüssel-Wert-Paar gelöscht, und die Rückgabe ist ebenfalls null.

• default V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)
  Setzt einen neuen Eintrag in die Map oder verschmilzt einen existierenden Eintrag mit der angegebenen Funktion. Von der Semantik her ist das die komplexeste Methode. Der erste Fall ist einfach, denn wenn es zum Schlüssel keinen Wert gibt, dann wird das Schlüssel-Wert-Paar in die Map gesetzt, und merge(…) liefert als Rückgabe den value. Gibt es schon einen assoziierten Wert, wird die Funktion mit dem alten Wert und value aufgerufen (eine BiFunction hat zwei Parameter) und der alte assoziierte Wert mit diesem neuen Wert überschrieben, woraufhin die Rückgabe von merge(…)diesen neuen Wert liefert. Jetzt gibt es noch zwei Sonderfälle, und die hängen damit zusammen, wenn das Argument value gleich null ist oder die Funktion null liefert. In beiden Fällen wird das Schlüssel-Wert-Paar gelöscht, und die Rückgabe von merge(…) ist null.

Größe und Leertest

Mit size() lässt sich die Anzahl der Werte im Assoziativspeicher erfragen. isEmpty() entspricht einem size() == 0, gibt also true zurück, falls der Assoziativspeicher keine Elemente enthält.

String-Repräsentation, Gleichheitstest, Hashwert und Klon eines Assoziativspeichers *

Viele Methoden von Object überschreiben die Assoziativspeicher-Klassen. toString() auf Assoziativspeichern liefert eine Zeichenkette, die den Inhalt der Sammlung aufzeigt. Die String-Repräsentation liefert jeden enthaltenen Schlüssel, gefolgt von einem Gleichheitszeichen und dem zugehörigen Wert. Entwickler sollten nie diese Zeichenkennung parsen bzw. irgendwelche Annahmen über die Formatierung machen.

Aus Object überschreiben die Standardimplementierungen die Methoden equals(…) und hashCode().

Die Klassen HashMap (und Unterklasse LinkedHashMap), IdentityHashMap, TreeMap, ConcurrentSkipListMap und EnumMap deklarieren eine öffentliche clone()-Methode, die eine Kopie eines Assoziativspeichers erzeugt. Die Kopie bezieht sich allerdings nur auf den Assoziativspeicher selbst; die Schlüssel- und Wert-Objekte teilen sich Original und Klon. Diese Form der Kopie nennt sich auch flache Kopie (engl. shallow copy). Eine Veränderung an den enthaltenen Schlüssel-Wert-Objekten betrifft also immer beide Datenstrukturen, und eine unsachgemäße Modifikation kann zu Unregelmäßigkeiten im Original führen. Eine ConcurrentHashMap oder WeakHashMap unterstützt kein clone(), und eigentlich ist clone() überhaupt nicht nötig, denn die Konstruktoren der Datenstrukturen können immer eine andere Datenstruktur als Vorlage nehmen, etwa clone = new ConcurrentHashMap(existingMap).

• boolean equals(Object o)
  Damit die Gleichheit von zwei Assoziativspeichern gezeigt werden kann, vergleicht equals(…) alle Elemente von beiden Sammlungen.

• int hashCode()
  Liefert den Hashwert des Assoziativspeichers. Das ist wichtig, wenn die Sammlung selbst als Schlüssel benutzt wird – was jedoch als problematisch gelten kann, wenn der (grundsätzlich mutable) Assoziativspeicher später noch verändert werden soll.[ 49 ](Fast schon philosophisch wird’s, wenn eine Hash-Tabelle als Schlüssel oder Wert in sich selbst eingefügt werden soll. Das kann sie zwar noch erkennen, aber bei Map<Object,String> h = new HashMap<>(); h.put(h, "a"); h.put(h, "b"); gibt es einen StackOverflowError, und damit ist die Philosophie am Ende. Mit Generics fallen Fehler wie diese schneller auf. Interessanterweise fängt ein HashSet diesen Sonderfall ab, und Set<Object> s = new HashSet<>(); s.add(s); führt zu keinem Fehler.)

• Object clone()
  Fertigt eine Kopie an, ohne jedoch die Werte selbst zu klonen.

 

4.6.3Über die Bedeutung von equals(…) und hashCode() bei Elementen 

Wenn wir Assoziativspeicher wie eine HashMap nutzen, dann sollte uns bewusst sein, dass Vergleiche nach dem Hashwert und der Gleichheit durchgeführt werden, nicht aber nach der Identität. Die folgenden Zeilen zeigen ein Beispiel:

Listing 4.17com/tutego/insel/util/map/HashMapAndEquals.java(), main()

Die HashMap assoziiert den Punkt p1 mit einer Zeichenkette. Was ist nun, wenn wir ein zweites Punkt-Objekt mit den gleichen Koordinaten bilden und die Map nach diesem Objekt fragen?

Die Antwort ist die Zeichenfolge »Point p1«. Das liegt daran, dass zunächst der Hashwert von p1 und p2 gleich ist. Des Weiteren liefert auch equals(…) ein true, sodass dies als ein Fund zu werten ist (das liefert noch einmal einen wichtigen Hinweis darauf, dass immer beide Methoden equals(…) und hashCode() in Unterklassen zu überschreiben sind).

Mit etwas Überlegung folgt dieser Punkt fast zwangsläufig, denn bei einer Abfrage ist ja das zu erfragende Objekt nicht bekannt. Daher kann der Vergleich nur auf Gleichheit, nicht aber auf Identität stattfinden.

 

4.6.4Eigene Objekte hashen 

Für Objekte, die als Schlüssel in einen Hash-Assoziativspeicher gesetzt werden, gibt es keine Schnittstelle zu implementieren, lediglich die Aufforderung, dass equals(…) und hashCode() in geeigneter Weise (also der Bedeutung oder Semantik des Objekts entsprechend) untereinander konsistent implementiert sein sollen. Wenn equals(…) von zwei Objekten gleichen Typs zum Beispiel true ergibt, muss der Hashwert auch gleich sein, und wenn zwei Hashwerte ungleich sind, darf equals(…) nicht wahr ergeben. Viele Standardklassen, wie String oder Point, erfüllen diese Anforderung, andere, wie StringBuilder, implementieren kein eigenes hashCode() und equals(…). Ein weiteres Problem ist, dass bei Vergleichen mit Ordnung ein externer Comparator eingesetzt werden kann, aber die Logik für einen Test auf Gleichheit und die Berechnung eines Hashwerts lassen sich nicht in ein externes Objekt setzen. Für Schlüsselobjekte in einer NavigableMap/SortedMap ist hashCode() nicht erforderlich, da es hier auf die Ordnung ausdrücklich ankommt.

Wir wollen eine Klasse entwerfen, die hashCode() und equals(…) so implementiert, dass Strings unabhängig von ihrer Groß-/Kleinschreibung einsortiert und gefunden werden:

Listing 4.18com/tutego/insel/util/map/EqualsIgnoreCaseString.java

Ein kleiner Test mit den Rückgaben im Kommentar:

Listing 4.19com/tutego/insel/util/map/EqualsIgnoreCaseStringDemo.java, main()

 

4.6.5LinkedHashMap und LRU-Implementierungen 

Da die Reihenfolge der eingefügten Elemente bei einem Assoziativspeicher verloren geht, gibt es mit LinkedHashMap eine Mischung, also einen schnellen Assoziativspeicher mit gleichzeitiger Speicherung der Reihenfolge der Objekte. Die Bauart des Klassenamens LinkedHashMap macht schon deutlich, dass es eine Map ist, und die Reihenfolge der Objekte liefert einen Iterator; es gibt keine listenähnliche Schnittstelle mit get(int). LinkedHashMap ist für Assoziativspeicher das, was LinkedHashSet für HashSet ist.

Im Gegensatz zur normalen HashMap ruft LinkedHashMap immer genau dann die besondere Methode boolean removeEldestEntry(Map.Entry<K,V> eldest) auf, wenn intern ein Element der Sammlung hinzugenommen wird. Die Standardimplementierung dieser Methode liefert immer false, was bedeutet, dass das älteste Element nicht gelöscht werden soll, wenn ein neues hinzukommt. Doch bietet das JDK die Methode aus Absicht protected an, denn sie kann von uns überschrieben werden, um eine Datenstruktur aufzubauen, die eine maximale Anzahl an Elementen hat.

So sieht das aus:

Listing 4.20com/tutego/tutego/insel/util/map/LRUMap.java

LinkedHashSet bietet eine vergleichbare Methode removeEldestEntry(…) nicht. Wer diese benötigt, muss eine eigene Mengenklasse auf der Basis von LinkedHashMap realisieren.

 

4.6.6IdentityHashMap 

Es gibt eine besondere Datenstruktur mit dem Namen IdentityHashMap, die statt der internen equals(…)-Vergleiche einen Identitätsvergleich mit == durchführt. Die Implementierung ist selten im Einsatz, kann aber im Bereich der Performance-Optimierung eine interessante Rolle übernehmen und auch das Problem lösen, wenn in der Map denn absichtlich Objekte enthalten sein sollen, die equals-gleich, aber nicht identisch sind. Es lässt sich auch so sehen: IdentityHashMap ist attraktiv, wenn als Schlüssel Objekte zum Einsatz kommen, bei denen Gleichheit und Identität dasselbe bedeuten.

 

4.6.7Das Problem veränderter Elemente 

Ein Hashwert ergibt sich aus den Attributen eines Objekts. Um ein Objekt in einem Assoziativspeicher zu finden, wird dann nach dem Hashwert gesucht; dumm, wenn sich dieser in der Zwischenzeit geändert hat:

Listing 4.21com/tutego/insel/util/map/MapImmutable.java, main()

Nach der Zuweisung an x wird hashCode() einen anderen Wert als vorher liefern. Wenn nun get(…) nach dem Objekt sucht, berechnet es den Hashwert und sucht in den internen Datenstrukturen. Ändert sich der Hashwert jedoch unterdessen, kann das Element nicht mehr gefunden werden und liegt als Leiche in der Map. Daher kann nur davor gewarnt werden, Attribute von Objekten, die durch Assoziativspeicher verwaltet werden, nachträglich zu ändern. Das Prinzip Hashing benutzt gerade diese Eigenschaft, um Objekte durch unveränderte Zustände wiederzufinden.

 

4.6.8Aufzählungen und Ansichten des Assoziativspeichers 

Eine Map kann beim erweiterten for nicht rechts vom Doppelpunkt stehen, da sie kein Iterable implementiert – nicht direkt und, da eine Map keine Collection ist, auch nicht indirekt. Auch fehlt der Map irgendeine direkte Methode iterator().

Eine Map kann auf drei Arten Sammlungen zurückgeben, über die sich iterieren lässt:

• keySet() liefert eine Menge der Schlüssel.

• values() liefert eine Collection der Werte.

• entrySet() liefert eine Menge mit speziellen Map.Entry-Objekten. Die Map.Entry-Objekte speichern gleichzeitig den Schlüssel sowie den Wert.

Für die Sammlungen gibt es erst einmal keine definierte Reihenfolge beim Auflaufen, es sei denn, die Map ist eine NavigableMap, wo ein Comparator die Ordnung vorgibt oder die Elemente Comparable sind.

• Set<K> keySet()
  Liefert eine Menge mit den Schlüsseln.

• Set<Map.Entry<K,V>> entrySet()
  Liefert eine Menge von Map.Entry-Objekten, die Zugriff auf die Schlüssel und Werte bieten.

• Collection<V> values()
  Liefert eine Sammlung der Werte.

Da eine Map immer typisiert ist, gilt das natürlich auch für die Sichten auf die Daten.

keySet() und values()

keySet() liefert eine Sammlung als Menge, da die Schlüssel eines Assoziativspeichers immer eindeutig sind.

Für eine Sammlung aller Werte gibt es keineSet-liefernde Methode valueSet(), weil ein Wert mehr als einmal vorkommen kann, wie auch unser Beispiel mit "Weihnachtsmann" → "wunsch@weihnachtsmann.com", "Christkind" → "wunsch@weihnachtsmann.com" zeigt. Daher heißt die Methode für alle assoziierten Werte einfach values(); die Methode liefert die spezielle Collection mit den Werten. Ein Aufruf von iterator() auf dieser Collection bietet dann eine Aufzählung dieser Werte. Über den Iterator oder die Collection können Elemente aus der Map gelöscht, aber keine neuen eingefügt werden.

Map.Entry

Während keySet() nur die eindeutigen Schlüssel in einer Menge liefert und die assoziierten Elemente in einem zweiten Schritt geholt werden müssten, gibt entrySet() ein Set von Elementen, typisiert mit Map.Entry zurück. Entry ist eine innere Schnittstelle von Map, die eine API zum Zugriff auf Schlüssel-Wert-Paare deklariert. Die wichtigen Operationen dieser Schnittstelle sind getKey(), getValue() und setValue(), wobei die letzte Methode optional ist, aber etwa von HashMap angeboten wird. Neben diesen Methoden überschreibt Entry auch hashCode() und equals(…).

Map.Entry ist eher ein Interna, und die Objekte dienen nicht der langfristigen Speicherung. Ein entrySet() ist eine Momentaufnahme, und das Ergebnis sollte nicht referenziert werden, denn ändert sich der darunterliegende Assoziativspeicher, ändern sich auch die Entry-Objekte, und das Set<Map.Entry> als Ganzes ist vielleicht nicht mehr gültig. Entry-Objekte sind nur gültig im Moment der Iteration, was den Nutzen einschränkt. Daher ist die Rückgabe von entrySet() mit Set<Map.Entry<K,V>> auch relativ unspezifisch, und es ist unklar, um was für eine Art von Set es sich genau handelt; ob HashSet oder vielleicht NavigableSet spielt keine Rolle.

Auch wenn die Map.Entry-Objekte nicht für die Speicherung gedacht sind, können Sie in Java 8 in einem Strom von Daten verarbeitet und in einer zustandsbehafteten Operation sortiert werden. Der Bonus der Entry-Objekte im Strom ist einfach, dass es von Vorteil ist, Schüssel und Wert in einem Objekt gekapselt zu sehen. Aber was ist, wenn jetzt der Strom sortiert werden soll, etwa nach dem Schlüssel oder dem Wert? Hier kommen neue Methoden von Java 8 ins Spiel, die den nötigen Comparator liefern.

• static <K extends Comparable<? super K>,V> Comparator<Map.Entry<K,V>> comparingByKey()

• static <K,V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue()

• static <K,V> Comparator<Map.Entry<K,V>> comparingByKey(Comparator<? super K> cmp)

• static <K,V> Comparator<Map.Entry<K,V>> comparingByValue(Comparator<? super V> cmp)

Verändernde Ansichten

Allen Methoden ist gemeinsam, dass sie nur eine andere Sicht auf die Originalmenge darstellen. Wir müssen uns dessen bewusst sein, dass Löschoperationen die ursprüngliche Menge verändern. Mit anderen Worten: Die von keySet(), values() oder entrySet() zurückgegebenen Sammlungen sind verschiedene Ansichten des Originals, und Veränderungen wirken sich unmittelbar auf das Original aus:

Listing 4.22com/tutego/insel/util/map/MapView.java, main()

 

4.6.9Die Arbeitsweise einer Hash-Tabelle * 

Für Assoziativspeicher gibt es unterschiedliche Implementierungen; eine basiert auf sortierten Bäumen, eine andere nutzt eine besondere mathematische Funktion, sodass wir bei diesen Assoziativspeichern von Hash-Tabellen sprechen. Insgesamt setzt Java bei mehreren Datenstrukturen auf das Hashing-Verfahren; die Klassen sind durch das Wort »Hash« zu identifizieren:

• HashMaps

• Hashtable

• HashSet

• LinkedHashMap

• LinkedHashSet

• WeakHashMap

• ConcurrentHashMap

Die Arbeitsweise ist wie folgt: Aus dem Schlüssel wird nach einer mathematischen Funktion – der so genannten Hash-Funktion – ein Hashwert (auch Hashcode) berechnet. Dieser dient dann als Index für ein internes Array. Dieses Array hat am Anfang eine feste Größe. Wenn später eine Anfrage nach dem Schlüssel gestellt wird, muss einfach diese Berechnung erfolgen, und wir können dann an dieser Stelle nachsehen. Wir können uns eine einfache Hash-Funktion für folgendes Problem denken: Beliebige Zeichenketten sollen in der Hash-Tabelle abgelegt werden. Die Hash-Funktion summiert einfach alle ASCII-Werte der Buchstaben und nimmt sie Modulo 77. Dann können in einem Array mit 77 Elementen 77 verschiedene Wörter aufgenommen werden. Leider hat diese Technik einen entscheidenden Nachteil: Wenn zwei unterschiedliche Wörter denselben Hashwert besitzen, kommt es zu einer Kollision. Darauf muss die Datenstruktur vorbereitet sein. Hier gibt es verschiedene Lösungsansätze. Die unter Java implementierte Lösung referenziert eine Datenstruktur hinter jedem Feldelement (einen so genannten Bucket); diese Implementierungsvariante heißt Hashing mit Verkettung. Falls eine Kollision auftritt, wird dieses Element in die Datenstruktur gesetzt. Oftmals ist es eine simple lineare Liste (ein Feld), in der aktuellen Java SE ist es eine Kombination aus Baum und Liste.

Der Füllfaktor und die Konstruktoren

Um ein Maß für den Füllgrad zu bekommen, wird ein Füllfaktor (Füllgrad; engl. load factor) eingeführt. Dieser liegt zwischen 0 % und 100 %. Ist er 0 %, so bedeutet dies, dass die Hash-Tabelle leer ist; ist er 100 %, so enthält die Hash-Tabelle genauso viele Einträge, wie das interne Array Elemente umfasst. Die Verteilung der Einträge auf die Array-Elemente wird dabei in der Regel ungleichmäßig sein. Einige Array-Elemente enthalten bereits (kurze) Listen mit kollidierenden Einträgen, während andere Array-Elemente noch unbenutzt sind. Der Füllfaktor einer Hash-Tabelle sollte für einen schnellen Zugriff nicht höher als 75 % sein. Das heißt, ein Viertel der Array-Elemente wird grundsätzlich nicht belegt.

Der Füllfaktor gibt also an, wie »voll« die Hash-Tabelle ist. Es lässt sich nun einstellen, dass die Hash-Tabelle sich automatisch vergrößert, damit der Zugriff wieder schneller wird. Dazu ordnen wir dem Füllgrad einen Prozentwert als Fließkommazahl zwischen 0,0 und 1,0 zu. Ein Wert von 0,75 entspricht also dem oben angesprochenen idealen Füllgrad von 75  %. Es gibt einen Konstruktor für HashMap/Hashtable-Exemplare, der die Angabe eines Füllgrads erlaubt. Ist dieser überschritten, wird die Hash-Tabelle neu berechnet. Dies nennt sich Re-Hashing. Dazu wird eine neue Hash-Tabelle angelegt, deren Array größer als das alte ist. Jeder Wert aus der alten Hash-Tabelle wird dabei gemäß der Hash-Funktion an die passende Stelle in das größere Array eingefügt. Ist dies für alle Elemente geschehen, wird die alte Hash-Tabelle gelöscht. Dieses Kopieren und Neuberechnen dauert zwar einige Zeit, doch direkt danach lassen sich die Anfragen an die Datenstruktur wieder schnell beantworten. Wenn die Hash-Tabelle zu oft vergrößert und neu organisiert werden muss, ist dies natürlich ein gewaltiger Geschwindigkeitsnachteil. Doch durch die Vergrößerung wird der Zugriff wieder schneller. Das Re-Hashing kann nicht ausdrücklich erzwungen werden.

• HashMap()
  Die Hash-Tabelle enthält initial eine Kapazität von 16 freien Plätzen und einen Füllfaktor von 75  %, also 0,75.

• HashMap(int initialCapacity)
  Erzeugt eine Hash-Tabelle mit einer vorgegebenen Kapazität und dem Füllfaktor 0,75.

• HashMap(int initialCapacity, float loadFactor)
  Erzeugt eine Hash-Tabelle mit einer vorgegebenen Kapazität und dem angegebenen Füllfaktor.

Die anfängliche Größe des internen Arrays lässt sich in zwei Konstruktoren angeben; ein unsinniger Wert löst eine IllegalArgumentException aus. Zusätzlich kann der Füllfaktor angegeben werden; ist dieser falsch, wird diese Exception ebenfalls ausgelöst. initialCapacity muss größer als die geplante Nutzlast der Hash-Tabelle gewählt werden. Das heißt, bei geplanten 1.000 Einträgen ist initialCapacity etwa 1000 × (1/0,75) = 1333. Ist ein Füllfaktor nicht explizit angegeben, wird die Hash-Tabelle dann vergrößert und neu organisiert, wenn die Anzahl der Einträge in der Hash-Tabelle größer gleich 0,75 × Größe des Arrays ist.

Auch die Konstruktoren von HashSet ermöglichen die Angabe des Füllfaktors und der Initialgröße.

• HashSet()
  Erzeugt ein neues HashSet-Objekt mit 16 freien Plätzen und einem Füllfaktor von 0,75.

• 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 Performance wichtig. Ist die Größe zu klein gewählt, muss die Datenstruktur bei neu hinzugefügten Elementen vergrößert werden – hier unterscheidet sich die Klasse HashSet nicht von der Klasse HashMap, da HashSet intern auf HashMap basiert.

Kollisionen und Hash-Funktionen

Die Wahl der richtigen Hash-Funktion ist wichtig für die Performance. Denn eine »dumme« Hash-Funktion, die beispielsweise alle Schlüssel nur auf einen konstanten Wert abbildet, erreicht keine Verteilung, sondern lediglich eine lange Liste von Schlüssel-Wert-Paaren; diese Anhäufung an einer Stelle nennt sich Clustering. Doch auch bei der besten Verteilung über N Buckets ist nach dem Einfügen des Elements N + 1 irgendwo eine Liste mit mindestens zwei Elementen aufgebaut, daher vergrößert die Bibliothek standardmäßig das Feld. Ist aber die Hash-Funktion so schlecht, dass alles auf das gleiche Bucket abgebildet wird, hilft dieses Re-Hashing auch nicht.

Je länger die Datenstruktur der miteinander kollidierenden Einträge wird, desto langsamer wird der Zugriff der auf Hashing basierenden Datenstruktur insgesamt. Java basiert beim Hashing einzig auf der hashCode()-Methode, und es liegt in unserer Hand sie gut zu implementieren. Die Klasse String hat eine relativ einfache (dafür schnelle) Implementierung von hashCode(), die in der Vergangenheit zu Denial-of-Service-Attacken führte, gerade weil es zu Kollisionen kam.[ 50 ](In Java 7 wurde dafür in String eine zusätzliche Hash-Methode realisiert, doch in Java 8 wurde diese Implementierung wieder entfernt und die Implementierung für das Hashing insgesamt verändert, zumindest für die aktuellen Klassen; das ältere java.util.Hashtable blieb unverändert.)

 

4.6.10Die Properties-Klasse 

Die Klasse java.util.Properties ist eine Sonderform der Assoziativspeicher, bei der Schlüssel-Wert-Paare immer vom Typ String sind. Ein Assoziativspeicher, der Strings mit Strings verbindet, ist auch HashMap<String,String>, doch die Klasse Properties kann noch mehr: Sie kann Properties hierarchisch verketten und Einträge in einer Datei speichern und wieder auslesen. Auf diese Weise lassen sich fest verdrahtete Zeichenketten aus dem Programmtext externalisieren, sodass sich die Werte auch ohne Neuübersetzung bequem verändern lassen.

Im Folgenden schauen wir uns an, wie ein Properties-Objekt aufgebaut, gefüllt und erfragt wird. Die Speicherung und das Laden mithilfe von Properties gehören thematisch zu den Datenformaten und sind Bestandteil von Kapitel 9, »Dateiformate«.

Properties setzen und lesen

Die Methode setProperty(String, String) fügt dem Properties-Objekt ein Schlüssel-Wert-Paar hinzu. Um später wieder an den Wert zu kommen, wird getProperty(String) mit dem Schlüssel aufgerufen und liefert dann – wenn beide Zeichenketten vorher verbunden wurden – den Wert:

Von der Klassendeklaration her erweitert Properties die Klasse Hashtable<Object, Object>, und da Hashtable die Schnittstelle Map implementiert, ist Properties auch vom Typ Map. Die Map-Methoden werden jedoch nicht eingesetzt.

Properties verketten

Properties-Objekte lassen sich hierarchisch verbinden, sodass im Fall einer erfolglosen Suche nach einem Schlüssel das Properties-Objekt die Anfrage an ein übergeordnetes Properties-Objekt weiterleitet; das Eltern-Properties-Objekt wird einfach im Konstruktor übergeben:

Listing 4.23com/tutego/insel/util/map/PropertiesDemo.java. main()

Die Zeilen erzeugen zwei Properties-Objekte. Obwohl am Anfang beide leer sind, werden doch die in defaultProperties hinzugefügten Einträge auch in userProperties sichtbar sein. Im Folgenden ist abzulesen, wie userProperties einen Eintrag überschreibt:

Zuerst durchsucht ein Property-Exemplar die eigene Datenstruktur. Liefert diese Property keinen Eintrag oder keinen Wert vom Typ String, so wird das im Konstruktoraufruf angegebene Property-Objekt durchsucht. Auf diese Weise lassen sich mehrstufige Hierarchien von Property-Verzeichnissen konstruieren.

• Properties()
  Erzeugt ein leeres Properties-Objekt ohne Schlüssel und Werte.

• Properties(Properties defaults)
  Erzeugt ein leeres Properties-Objekt, das bei Anfragen auch auf die Einträge in dem übergebenen Properties-Objekt zurückgreift.

• String getProperty(String key)
  Sucht in den Properties nach der Zeichenkette key als Schlüssel und liefert den zugehörigen Wert. Durchsucht auch übergeordnete Properties-Objekte.

• String getProperty(String key, String default)
  Sucht in den Properties nach der Zeichenkette key als Schlüssel und liefert den zugehörigen Wert. Ist der Schlüssel nicht vorhanden, wird der String default zurückgegeben.

• Object setProperty(String key, String value)
  Trägt Schlüssel und Wert im Properties-Exemplar ein. Existiert der Schlüssel schon, wird er überschrieben. Mitunter verdeckt der Schlüssel den Wert der Property in der übergeordneten Property.

• void Enumeration<?> propertyNames()
  Liefert eine Enumeration aller Schlüssel in der Properties-Liste inklusive der Standardwerte aus übergeordneten Properties.

Hierarchische Eigenschaften

Leider kann eine Eigenschaften-Datei nicht segmentiert werden, wie etwa alte Windows-INI-Dateien dies machen. Die Alternative besteht darin, hierarchisch benannte Eigenschaften zu erzeugen, indem eine Zeichenkette vor jeden Schlüssel gesetzt wird. Um zum Beispiel einen Schlüssel User einmal unter Private und einmal unter Public zu halten, lassen sich die Eigenschaften Private.User und Public.User einsetzen. Doch leider tauchen sie nach dem Speichern durcheinandergewürfelt in der Datei auf, weil der Assoziativspeicher keine Sortierung besitzt (Properties basiert nicht auf TreeMap).

Eigenschaften auf der Konsole ausgeben *

Die Methoden list(PrintStream) bzw. list(PrintWriter) wandern durch die Daten eines Properties-Exemplars und schreiben sie in den Datenstrom. Eine Ausgabe auf dem Bildschirm erhalten wir mit list(System.out). Schlüssel und Werte trennt ein Gleichheitszeichen. Die Ausgabe über list(…) ist gekürzt, denn ist ein Wert länger als 40 Zeichen, wird er abgekürzt; daher eignet sich die Methode nicht dafür, die Belegungen gültig in eine Datei zu schreiben. Ein list(System.out) auf die defaultProperties bzw. userProperties von unserem vorangegangenen Beispiel ergibt folgende Ausgabe:

Den Paaren geht eine Kopfzeile der Art -- listing properties -- voran. Es ist wichtig zu verstehen, dass durch die Art der Speicherung (ein Assoziativspeicher auf Basis des Hashings) die Ausgabe unsortiert erfolgt.

• void list(PrintStream out)
  Listet die Properties aus dem PrintStream auf.

• void list(PrintWriter out)
  Listet die Properties aus dem PrintWriter auf.

Klassenbeziehungen – Properties und Hashtable *

Die Properties-Klasse ist eine Erweiterung von Hashtable, weil die Speicherung der Einstellungsdaten in dieser Datenstruktur erfolgt. Ein Properties-Objekt erweitert den Assoziativspeicher um die Möglichkeit, die Schlüssel-Wert-Paare in einem festgelegten Format aus einer Textdatei bzw. einem Datenstrom zu laden und wieder zu speichern. Doch gerade weil Hashtable erweitert wird, sind auch alle Methoden der Klasse Hashtable auf ein Properties-Objekt anwendbar. Das ergibt nicht für alle Methoden Sinn und ist auch nicht in jedem Fall problemlos. Dass Properties eine Unterklasse von Hashtable ist, ist ähnlich fragwürdig wie die Vererbungsbeziehung von Stack als Unterklasse von Vector. So ist ein Augenmerk auf die put(…)-Methode zu richten. Sie gibt es in der Klasse Properties nicht, denn put(…) wird von Hashtable geerbt. Wir sollten sie auch nicht verwenden, da es über sie möglich ist, Objekte einzufügen, die nicht vom Typ String sind. Das gleiche Argument könnte für get(…) gelten, doch sprechen zwei Dinge dagegen: zum einen, dass wir beim get(…) aus einem Hashtable-Objekt immer ein Object-Objekt bekommen und daher meistens eine Typanpassung benötigen; und zum anderen durchsucht diese Methode lediglich den Inhalt des angesprochenen Properties-Exemplars. getProperties() arbeitet da etwas anders. Nicht nur ist der Rückgabewert automatisch ein String, sondern getProperties() durchsucht auch übergeordnete Properties-Objekte mit, die zum Beispiel Standardwerte speichern.