Java SE 8 Standard-Bibliothek  
Professionelle Bücher. Auch für Einsteiger.
 
Inhaltsverzeichnis

Vorwort
1 Neues in Java 8 und Java 7
2 Fortgeschrittene String-Verarbeitung
3 Threads und nebenläufige Programmierung
4 Datenstrukturen und Algorithmen
5 Raum und Zeit
6 Dateien, Verzeichnisse und Dateizugriffe
7 Datenströme
8 Die eXtensible Markup Language (XML)
9 Dateiformate
10 Grafische Oberflächen mit Swing
11 Grafikprogrammierung
12 JavaFX
13 Netzwerkprogrammierung
14 Verteilte Programmierung mit RMI
15 RESTful und SOAP-Web-Services
16 Technologien für die Infrastruktur
17 Typen, Reflection und Annotationen
18 Dynamische Übersetzung und Skriptsprachen
19 Logging und Monitoring
20 Sicherheitskonzepte
21 Datenbankmanagement mit JDBC
22 Java Native Interface (JNI)
23 Dienstprogramme für die Java-Umgebung
Stichwortverzeichnis

Jetzt Buch bestellen
Ihre Meinung?

Spacer
<< zurück
Java SE 8 Standard-Bibliothek von Christian Ullenboom
Das Handbuch für Java-Entwickler
Buch: Java SE 8 Standard-Bibliothek

Java SE 8 Standard-Bibliothek
Pfeil 4 Datenstrukturen und Algorithmen
Pfeil 4.1 Datenstrukturen und die Collection-API
Pfeil 4.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 4.1.2 Die Basisschnittstellen Collection und Map
Pfeil 4.1.3 Die Utility-Klassen Collections und Arrays
Pfeil 4.1.4 Das erste Programm mit Container-Klassen
Pfeil 4.1.5 Die Schnittstelle Collection und Kernkonzepte
Pfeil 4.1.6 Schnittstellen, die Collection erweitern, und Map
Pfeil 4.1.7 Konkrete Container-Klassen
Pfeil 4.1.8 Generische Datentypen in der Collection-API
Pfeil 4.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 4.2 Listen
Pfeil 4.2.1 Erstes Listen-Beispiel
Pfeil 4.2.2 Auswahlkriterium ArrayList oder LinkedList
Pfeil 4.2.3 Die Schnittstelle List
Pfeil 4.2.4 ArrayList
Pfeil 4.2.5 LinkedList
Pfeil 4.2.6 Der Feld-Adapter Arrays.asList(…)
Pfeil 4.2.7 ListIterator *
Pfeil 4.2.8 toArray(…) von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 4.2.9 Primitive Elemente in Datenstrukturen verwalten
Pfeil 4.3 Mengen (Sets)
Pfeil 4.3.1 Ein erstes Mengen-Beispiel
Pfeil 4.3.2 Methoden der Schnittstelle Set
Pfeil 4.3.3 HashSet
Pfeil 4.3.4 TreeSet – die sortierte Menge
Pfeil 4.3.5 Die Schnittstellen NavigableSet und SortedSet
Pfeil 4.3.6 LinkedHashSet
Pfeil 4.4 Queues (Schlangen) und Deques
Pfeil 4.4.1 Queue-Klassen
Pfeil 4.4.2 Deque-Klassen
Pfeil 4.4.3 Blockierende Queues und Prioritätswarteschlangen
Pfeil 4.4.4 PriorityQueue
Pfeil 4.5 Stack (Kellerspeicher, Stapel)
Pfeil 4.5.1 Die Methoden von java.util.Stack
Pfeil 4.6 Assoziative Speicher
Pfeil 4.6.1 Die Klassen HashMap und TreeMap
Pfeil 4.6.2 Einfügen und Abfragen des Assoziativspeichers
Pfeil 4.6.3 Über die Bedeutung von equals(…) und hashCode() bei Elementen
Pfeil 4.6.4 Eigene Objekte hashen
Pfeil 4.6.5 LinkedHashMap und LRU-Implementierungen
Pfeil 4.6.6 IdentityHashMap
Pfeil 4.6.7 Das Problem veränderter Elemente
Pfeil 4.6.8 Aufzählungen und Ansichten des Assoziativspeichers
Pfeil 4.6.9 Die Arbeitsweise einer Hash-Tabelle *
Pfeil 4.6.10 Die Properties-Klasse
Pfeil 4.7 Mit einem Iterator durch die Daten wandern
Pfeil 4.8 Iterator-Schnittstelle
Pfeil 4.8.1 Der Iterator kann (eventuell auch) löschen
Pfeil 4.8.2 Operationen auf allen Elementen durchführen
Pfeil 4.8.3 Einen Zufallszahlen-Iterator schreiben
Pfeil 4.8.4 Iteratoren von Sammlungen, das erweiterte for und Iterable
Pfeil 4.8.5 Fail-Fast-Iterator und die ConcurrentModificationException
Pfeil 4.8.6 Die Schnittstelle Enumerator *
Pfeil 4.9 Algorithmen in Collections
Pfeil 4.9.1 Die Bedeutung von Ordnung mit Comparator und Comparable
Pfeil 4.9.2 Sortieren
Pfeil 4.9.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 4.9.4 Nichtänderbare Datenstrukturen, immutable oder nur lesen?
Pfeil 4.9.5 Null Object Pattern und leere Sammlungen/Iteratoren zurückgeben
Pfeil 4.9.6 Echte typsichere Container
Pfeil 4.9.7 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 4.9.8 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren *
Pfeil 4.9.9 Listen durchwürfeln *
Pfeil 4.9.10 Häufigkeit eines Elements *
Pfeil 4.9.11 Singletons *
Pfeil 4.9.12 nCopies(…) *
Pfeil 4.10 Datenstrukturen mit Änderungsmeldungen
Pfeil 4.10.1 Das Paket javafx.collections
Pfeil 4.10.2 Fabrikmethoden in FXCollections
Pfeil 4.10.3 Änderungen melden über InvalidationListener
Pfeil 4.10.4 Änderungen melden über XXXChangeListener
Pfeil 4.10.5 Change-Klassen
Pfeil 4.10.6 Weitere Hilfsmethoden einer ObservableList
Pfeil 4.10.7 Melden von Änderungen an Arrays
Pfeil 4.10.8 Transformierte FXCollections
Pfeil 4.10.9 Weitere statische Methoden in FXCollections
Pfeil 4.11 Stream-API
Pfeil 4.11.1 Stream erzeugen
Pfeil 4.11.2 Terminale Operationen
Pfeil 4.11.3 Intermediäre Operationen
Pfeil 4.11.4 Streams mit primitiven Werten
Pfeil 4.11.5 Stream-Beziehungen, AutoCloseable
Pfeil 4.11.6 Stream-Builder
Pfeil 4.11.7 Spliterator
Pfeil 4.11.8 Klasse StreamSupport
Pfeil 4.12 Spezielle threadsichere Datenstrukturen
Pfeil 4.12.1 Zu Beginn nur synchronisierte Datenstrukturen in Java 1.0
Pfeil 4.12.2 Nicht synchronisierte Datenstrukturen in der Standard-Collection-API
Pfeil 4.12.3 Nebenläufiger Assoziativspeicher und die Schnittstelle ConcurrentMap
Pfeil 4.12.4 ConcurrentLinkedQueue
Pfeil 4.12.5 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 4.12.6 Wrapper zur Synchronisation
Pfeil 4.12.7 Blockierende Warteschlangen
Pfeil 4.12.8 ArrayBlockingQueue und LinkedBlockingQueue
Pfeil 4.12.9 PriorityBlockingQueue
Pfeil 4.12.10 Transfer-Warteschlangen – TransferQueue und LinkedTransferQueue
Pfeil 4.13 Google Guava (Google Collections Library)
Pfeil 4.13.1 Beispiel Multi-Set und Multi-Map
Pfeil 4.13.2 Datenstrukturen aus Guava
Pfeil 4.13.3 Utility-Klassen von Guava
Pfeil 4.13.4 Prädikate
Pfeil 4.13.5 Transformationen
Pfeil 4.14 Die Klasse BitSet für Bitmengen *
Pfeil 4.14.1 Ein BitSet anlegen
Pfeil 4.14.2 BitSet füllen und Zustände erfragen
Pfeil 4.14.3 Mengenorientierte Operationen
Pfeil 4.14.4 Weitere Methoden von BitSet
Pfeil 4.14.5 Primzahlen in einem BitSet verwalten
Pfeil 4.15 Zum Weiterlesen
 
Zum Seitenanfang

4.6Assoziative Speicher Zur vorigen ÜberschriftZur nächsten Überschrift

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.

 
Zum Seitenanfang

4.6.1Die Klassen HashMap und TreeMap Zur vorigen ÜberschriftZur nächsten Überschrift

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.

[zB]Beispiel

Ein Assoziativspeicher, dem wir Werte[ 47 ](Siehe dazu auch http://www.aldibaran.de/?page_id=13#2.) hinzufügen:

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", "McCaine" );

Die zweite HashMap soll Strings mit Zahlen assoziieren:

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

Klassendiagramm der Schnittstelle Map

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.

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.

 
Zum Seitenanfang

4.6.2Einfügen und Abfragen des Assoziativspeichers Zur vorigen ÜberschriftZur nächsten Überschrift

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.

[»]Hinweis für Nullen

Bei manchen Implementierungen der Map-Schnittstelle kann der Schlüssel bzw. Wert null sein – hier lohnt ein Blick auf die Javadoc der einzelnen Klassen. Bei HashMap ist null als Schlüssel und Wert ausdrücklich erlaubt, bei ConcurrentHashMap dürfen weder Schlüssel noch Wert null sein.

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

[zB]Beispiel

Die Ausgabe wird sein: »zwei=2« und »drei=3.0«.

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 );

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.

[zB]Beispiel

Erfrage den Assoziativspeicher nach »zwei«. Das Ergebnis wird ein Number-Objekt sein:

Map<String,Number> num = new HashMap<>();
Number number = num.get( "zwei" );
if ( number != null )
System.out.println( number.intValue() );

Mit Generics kann eine Typanpassung entfallen, wenn – wie in unserem Beispiel – Number-Objekte mit dem String assoziiert waren. Wurde der Typ nicht angegeben, ist eine Typanpassung nötig.

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.

interface java.util.Map<K,V>
  • 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.

interface java.util.Map<K,V>
  • 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.

Implementierungsdetail

Die Implementierung von replaceAll(…) ist über die Default-Methode gegeben und sieht (abgesehen von der internen Ausnahmebehandlung) so aus:

for ( (Map.Entry<K, V> entry : map.entrySet() )
entry.setValue( function.apply( entry.getKey(), entry.getValue() ) );

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():

interface java.util.Map<K,V>
  • 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.

interface java.util.Map<K,V>
  • 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.

[zB]Beispiel

Java bietet von Haus aus keine Datenstruktur, die wie ein Assoziativspeicher arbeitet, aber einen Schlüssel mit einer Sammlung von Werten assoziieren kann. Doch so eine Klasse ist schnell geschrieben:[ 48 ](Und so etwas ist Teil jeder Java-API-Erweiterung, wir kommen darauf noch zu sprechen.)

Listing 4.16com/tutego/insel/util/map/MultimapDemo.java, Multimap

class Multimap<K, V> {
private final Map<K,Collection<V>> map = new HashMap<>();

public Collection<V> get( K key ) {
return map.getOrDefault( key, Collections.<V> emptyList() );
}

public void put( K key, V value ) {
map.computeIfAbsent( key, k -> new ArrayList<>() )
.add( value );
}
}

Ein kleines Beispiel:

Multimap<Integer,String> mm = new Multimap<>();
System.out.println( mm.get( 1 ) ); // []
mm.put( 1, "eins" );
System.out.println( mm.get( 1 ) ); // [eins]
mm.put( 1, "one" );
System.out.println( mm.get( 1 ) ); // [eins, one]
interface java.util.Map<K,V>
  • 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.

[zB]Beispiel

Zu einer ID soll ein Punkt assoziiert werden. Neue, hinzugefügte Punkte zu dieser ID sollen die Koordinate des ursprünglichen Punktes verschieben.

Map<Integer,Point> map = new HashMap<>();
BiFunction<? super Point,? super Point,? extends Point> remappingFunc =
(oldVal, val) -> { val.translate( oldVal.x, oldVal.y ); return val; };
map.merge( 1, new Point( 12, 3 ), remappingFunc );
System.out.println( map.get( 1 ) ); // java.awt.Point[x=12,y=3]
map.merge( 1, new Point( -2, 2 ), remappingFunc );
System.out.println( map.get( 1 ) ); // java.awt.Point[x=10,y=5]
map.merge( 1, new Point( 0, 5 ), remappingFunct );
System.out.println( map.get( 1 ) ); // java.awt.Point[x=10,y=10]

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.

[zB]Beispiel

Ein Assoziativspeicher soll die Zahlen 1, 2, 3 jeweils mit ihrem Quadrat assoziieren. Zum Aufbau benutzen wir eine fortgeschrittene Technik aus Java 8:

Map<Integer,Integer> map = Arrays.asList( 1, 2, 3 )
.stream()
.collect( Collectors.<Integer,Integer,Integer>toMap( id -> id, id -> id*id) );
System.out.println( map ); // {1=1, 2=4, 3=9}

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

interface java.util.Map<K,V>
  • 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.)

class java.util.HashMap<K,V> …
class java.util.TreeMap<K,V> …
  • Object clone()
    Fertigt eine Kopie an, ohne jedoch die Werte selbst zu klonen.

 
Zum Seitenanfang

4.6.3Über die Bedeutung von equals(…) und hashCode() bei Elementen Zur vorigen ÜberschriftZur nächsten Überschrift

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()

Map<Point,String> map = new HashMap<>();
Point p1 = new Point( 10, 20 );
map.put( p1, "Point p1" );

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?

Point p2 = new Point( 10, 20 );
System.out.println( map.get( p2 ) ); // ???

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.

 
Zum Seitenanfang

4.6.4Eigene Objekte hashen Zur vorigen ÜberschriftZur nächsten Überschrift

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

package com.tutego.insel.util.map;

public class EqualsIgnoreCaseString {

private final String string;

public EqualsIgnoreCaseString( String string ) {
this.string = string.toLowerCase();
}

@Override public int hashCode() {
return string.hashCode();
}

@Override public boolean equals( Object obj ) {
if ( this == obj )
return true;
if ( obj == null )
return false;
if ( getClass() != obj.getClass() )
return false;
return string.equals( ((EqualsIgnoreCaseString) obj).string );
}
}

Ein kleiner Test mit den Rückgaben im Kommentar:

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

Map<EqualsIgnoreCaseString, String> map = new HashMap<>();
map.put( new EqualsIgnoreCaseString("tutego"), "tutego" ); // null
map.put( new EqualsIgnoreCaseString("Tutego"), "Tutego" ); // tutego
map.put( new EqualsIgnoreCaseString("TUTI!"), "TUTI!" ); // null

map.get( new EqualsIgnoreCaseString("tutego") ); // Tutego
map.get( new EqualsIgnoreCaseString("TUTEGO") ); // Tutego
map.get( new EqualsIgnoreCaseString("tUtI!") ); // TUTI!
map.get( new EqualsIgnoreCaseString("tröt") ); // null
 
Zum Seitenanfang

4.6.5LinkedHashMap und LRU-Implementierungen Zur vorigen ÜberschriftZur nächsten Überschrift

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

package com.tutego.insel.util.map;

import java.util.*;

public class LRUMap<K,V> extends LinkedHashMap<K,V> {
private final int capacity;

public LRUMap( int capacity ) {
super( capacity, 0.75f, true );
this.capacity = capacity;
}

@Override
protected boolean removeEldestEntry( Map.Entry<K,V> eldest ) {
return size() > capacity;
}
}

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

 
Zum Seitenanfang

4.6.6IdentityHashMap Zur vorigen ÜberschriftZur nächsten Überschrift

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.

[»]Hinweis

An Integer-Objekten in einer IdentityHashMap zeigt sich genau der Unterschied zur klassischen Map wie einer HashMap. Nehmen wir

Integer key1 = 1;
Integer key2 = 1;
Integer key3 = 1000;
Integer key4 = 1000;

dann sind wegen des Autoboxings und wegen des internen Caches key1 == key2, aber key3 != key4 (die Integer-Klasse cacht standardmäßig Ganzzahlen im Wertebereich eines byte). Abfragen mit equals-gleichen Integer-Objekten sind in der HashMap üblich, laufen aber bei IdentityHashMap ins Leere, da es unmöglich ist, zum Beispiel später über Integer.value(1000) ein genau identisches Integer-Objekt aufzubauen, sodass es als Schlüssel in der IdentityHashMap »passt« und der Identitätsvergleich wahr wird.

 
Zum Seitenanfang

4.6.7Das Problem veränderter Elemente Zur vorigen ÜberschriftZur nächsten Überschrift

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()

Map<Point,String> map = new HashMap<>();
Point q = new Point( 1, 1 );
map.put( q, "Punkt q" );
q.x = 12345;
System.out.println( map.get( q ) ); // ???
q.x = 1;
System.out.println( map.get( q ) ); // ???

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.

 
Zum Seitenanfang

4.6.8Aufzählungen und Ansichten des Assoziativspeichers Zur vorigen ÜberschriftZur nächsten Überschrift

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.

[zB]Beispiel

Laufe die Schlüssel einer HashMap mit einem Iterator (über das erweiterte for) ab:

Map<String,String> h = new HashMap<>();
h.put( "C.Ullenboom", "c.ullenboom@no-spam.com" );
h.put( "Webmaster", "c.ullenboom@spammer.com" );
h.put( "Weihnachtsmann", "wunsch@weihnachtsmann.com" );
h.put( "Christkind", "wunsch@weihnachtsmann.com" );
for ( String elem : h.keySet() )
System.out.println( elem );

Liefert:

Weihnachtsmann
C.Ullenboom
Christkind
Webmaster
interface java.util.Map<K,V>
  • 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.

[zB]Beispiel

Es ist zu erfragen, ob sich in zwei Assoziativspeichern map1 und map2 die gleichen Schlüssel befinden – unabhängig vom Wert:

boolean sameKeys = map1.keySet().equals( map2.keySet() );

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.

[zB]Beispiel

Laufe die Werte einer HashMap mit einem Iterator ab:

for ( String elem : h.values() )
System.out.println( elem );

Das liefert:

wunsch@weihnachtsmann.com
c.ullenboom@no-spam.com
wunsch@weihnachtsmann.com
c.ullenboom@spammer.com

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(…).

[zB]Beispiel

Laufe die Elemente HashMap als Menge von Map.Entry-Objekten ab:

for ( Map.Entry<String,String> e : h.entrySet() )
System.out.println( e.getKey() + "=" + e.getValue() );

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.

[zB]Beispiel *

Erfrage eine Menge von Entry-Objekten, und sortiere sie nach dem assoziierten Wert:

map.entrySet()
.stream()
.sorted( Map.Entry.<String,String>comparingByValue() )
.forEach( System.out::println );
static interface Map.Entry<K,V>
  • 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()

Map<Integer,String> m = new HashMap<>();
m.put( 1, "Eins" );
m.put( 2, "ZZZZZWWWWEEEEEIIII" );
m.put( 3, "drei" );
System.out.println( m ); // {1=Eins, 2=ZZZZZWWWWEEEEEIIII, 3=drei}

m.keySet().remove( 2 );
System.out.println( m ); // {1=Eins, 3=drei}

m.values().remove( "Eins" );
System.out.println( m ); // {3=drei}

m.entrySet().clear();
System.out.println( m ); // {}
 
Zum Seitenanfang

4.6.9Die Arbeitsweise einer Hash-Tabelle * Zur vorigen ÜberschriftZur nächsten Überschrift

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.

class java.util.HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
  • 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.

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(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.)

 
Zum Seitenanfang

4.6.10Die Properties-Klasse Zur vorigen ÜberschriftZur nächsten Überschrift

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:

Properties props = new Properties();
props.setProperty( "User", "Eddie Grundies" );
props.setProperty( "Version", "0.02" );
System.out.println( props.getProperty("User") ); // Eddie Grundies
System.out.println( props.getProperty("Passwort") ); // null

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()

Properties defaultProperties = new Properties(),
userProperties = new Properties( defaultProperties );

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:

defaultProperties.setProperty( "User", "Bill Grundies" );
defaultProperties.setProperty( "Password", "(nicht gesetzt)" );
userProperties.setProperty( "Password", "SagIchNet" );

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.

class java.util.Properties
extends Hashtable<Object,Object>
  • 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:

-- listing properties --
Password=(nicht gesetzt)
User=Bill Grundies
-- listing properties --
Password=SagIchNet
User=Bill Grundies

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.

class java.util.Properties
extends Hashtable<Object,Object>
  • 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.

 


Ihre Meinung

Wie hat Ihnen das Openbook gefallen? Wir freuen uns immer über Ihre Rückmeldung. Schreiben Sie uns gerne Ihr Feedback als E-Mail an kommunikation@rheinwerk-verlag.de.

<< zurück
 Zum Rheinwerk-Shop
Zum Rheinwerk-Shop: Java SE 8 Standard-Bibliothek Java SE 8 Standard-Bibliothek
Jetzt Buch bestellen

 Buchempfehlungen
Zum Rheinwerk-Shop: Java ist auch eine Insel
Java ist auch eine Insel


Zum Rheinwerk-Shop: Professionell entwickeln mit Java EE 8
Professionell entwickeln mit Java EE 8


Zum Rheinwerk-Shop: Besser coden
Besser coden


Zum Rheinwerk-Shop: Entwurfsmuster
Entwurfsmuster


Zum Rheinwerk-Shop: IT-Projektmanagement
IT-Projektmanagement


 Lieferung
Versandkostenfrei bestellen in Deutschland, Österreich und der Schweiz
InfoInfo

 
 


Copyright © Rheinwerk Verlag GmbH 2018. Original - https://www.rheinwerk-verlag.de/openbook/
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das Openbook denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt.
Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

 

 
 


12.12.2024 - Sitemap.xml