Rheinwerk Computing < openbook > Rheinwerk Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger. 
Inhaltsverzeichnis
Vorwort
1 Java ist auch eine Sprache
2 Imperative Sprachkonzepte
3 Klassen und Objekte
4 Der Umgang mit Zeichenketten
5 Eigene Klassen schreiben
6 Objektorientierte Beziehungsfragen
7 Ausnahmen müssen sein
8 Äußere.innere Klassen
9 Besondere Typen der Java SE
10 Generics<T>
11 Lambda-Ausdrücke und funktionale Programmierung
12 Architektur, Design und angewandte Objektorientierung
13 Komponenten, JavaBeans und Module
14 Die Klassenbibliothek
15 Einführung in die nebenläufige Programmierung
16 Einführung in Datenstrukturen und Algorithmen
17 Einführung in grafische Oberflächen
18 Einführung in Dateien und Datenströme
19 Einführung ins Datenbankmanagement mit JDBC
20 Einführung in <XML>
21 Testen mit JUnit
22 Bits und Bytes und Mathematisches
23 Die Werkzeuge des JDK
A Java SE-Paketübersicht
Stichwortverzeichnis


Download:

- Beispielprogramme, ca. 35,4 MB


Buch bestellen
Ihre Meinung?



Spacer
<< zurück
Java ist auch eine Insel von Christian Ullenboom

Einführung, Ausbildung, Praxis
Buch: Java ist auch eine Insel


Java ist auch eine Insel

Pfeil 16 Einführung in Datenstrukturen und Algorithmen
Pfeil 16.1 Listen
Pfeil 16.1.1 Erstes Listenbeispiel
Pfeil 16.1.2 Auswahlkriterium ArrayList oder LinkedList
Pfeil 16.1.3 Die Schnittstelle List
Pfeil 16.1.4 ArrayList
Pfeil 16.1.5 LinkedList
Pfeil 16.1.6 Der Feld-Adapter Arrays.asList(…)
Pfeil 16.1.7 toArray(…) von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 16.1.8 Primitive Elemente in Datenstrukturen verwalten
Pfeil 16.2 Mengen (Sets)
Pfeil 16.2.1 Ein erstes Mengenbeispiel
Pfeil 16.2.2 Methoden der Schnittstelle Set
Pfeil 16.2.3 HashSet
Pfeil 16.2.4 TreeSet – die sortierte Menge
Pfeil 16.2.5 Die Schnittstellen NavigableSet und SortedSet
Pfeil 16.2.6 LinkedHashSet
Pfeil 16.3 Assoziative Speicher
Pfeil 16.3.1 Die Klassen HashMap und TreeMap
Pfeil 16.3.2 Einfügen und Abfragen des Assoziativspeichers
Pfeil 16.3.3 Über die Bedeutung von equals(…) und hashCode() bei Elementen
Pfeil 16.3.4 Eigene Objekte hashen
Pfeil 16.3.5 LinkedHashMap und LRU-Implementierungen
Pfeil 16.3.6 IdentityHashMap
Pfeil 16.3.7 Das Problem veränderter Elemente
Pfeil 16.3.8 Aufzählungen und Ansichten des Assoziativspeichers
Pfeil 16.3.9 Die Properties-Klasse
Pfeil 16.4 Mit einem Iterator durch die Daten wandern
Pfeil 16.5 Algorithmen in Collections
Pfeil 16.5.1 Die Bedeutung von Ordnung mit Comparator und Comparable
Pfeil 16.5.2 Sortieren
Pfeil 16.5.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 16.5.4 Nichtänderbare Datenstrukturen, immutable oder nur lesen?
Pfeil 16.5.5 Null Object Pattern und leere Sammlungen/Iteratoren zurückgeben
Pfeil 16.5.6 Echte typsichere Container
Pfeil 16.5.7 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 16.6 Zum Weiterlesen
 

Zum Seitenanfang

16.3Assoziative 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

16.3.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 Hashtabelle (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[ 233 ](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. Die Richtung ist immer nur einseitig. Auf wechselseitige Beziehungen sind die Klassen nicht vorbereitet.

Klassendiagramm der Schnittstelle Map

Abbildung 16.2Klassendiagramm 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 Hashtabelle.

  • HashMap(Map<? extends K,? extends V> m)

    Erzeugt eine neue Hashtabelle 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

16.3.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 oder 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 natürlich 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 Parameter 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 in Abschnitt 16.3.8 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

Befrage 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 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 sei 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:

Listing 16.8com/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

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

Map<Integer, Point> map = new HashMap<>();

BiFunction<Point, Point, 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 ), remappingFunc );

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.

 

Zum Seitenanfang

16.3.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 16.9com/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

16.3.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, sich aber die Logik für einen Test auf Gleichheit und die Berechnung eines Hashwerts nicht in ein externes Objekt setzen lassen. 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 16.10com/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 16.11com/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

16.3.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 Klassennamens 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 16.12tutego.tutego.insel.util.map.LRUMap

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

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

16.3.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 16.13com/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

16.3.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 Ablaufen, 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 keine Set-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 16.14com/tutego/insel/util/map/MapView, 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

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

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 16.15com/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 Eigenschaftendatei 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).

 


Ihr Kommentar

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

>> Zum Feedback-Formular
<< zurück

 

 


Copyright © Rheinwerk Verlag GmbH 2017

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.

 

[Rheinwerk Computing]



Rheinwerk Verlag GmbH, Rheinwerkallee 4, 53227 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, service@rheinwerk-verlag.de