Rheinwerk Computing < openbook > Rheinwerk Computing - Professionelle Bücher. Auch für Einsteiger.
Professionelle Bücher. Auch für Einsteiger.

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

Buch bestellen
Ihre Meinung?

Spacer
Java 7 - Mehr als eine Insel von Christian Ullenboom
Das Handbuch zu den Java SE-Bibliotheken
Buch: Java 7 - Mehr als eine Insel

Java 7 - Mehr als eine Insel
Rheinwerk Computing
1433 S., 2012, geb.
49,90 Euro, ISBN 978-3-8362-1507-7
Pfeil 3 Datenstrukturen und Algorithmen
Pfeil 3.1 Datenstrukturen und die Collection-API
Pfeil 3.1.1 Designprinzip mit Schnittstellen, abstrakten und konkreten Klassen
Pfeil 3.1.2 Die Basis-Schnittstellen Collection und Map
Pfeil 3.1.3 Die Utility-Klassen Collections und Arrays
Pfeil 3.1.4 Das erste Programm mit Container-Klassen
Pfeil 3.1.5 Die Schnittstelle Collection und Kernkonzepte
Pfeil 3.1.6 Schnittstellen, die Collection erweitern, und Map
Pfeil 3.1.7 Konkrete Container-Klassen
Pfeil 3.1.8 Generische Datentypen in der Collection-API
Pfeil 3.1.9 Die Schnittstelle Iterable und das erweiterte for
Pfeil 3.2 Listen
Pfeil 3.2.1 Erstes Listen-Beispiel
Pfeil 3.2.2 Auswahlkriterium ArrayList oder LinkedList
Pfeil 3.2.3 Die Schnittstelle List
Pfeil 3.2.4 ArrayList
Pfeil 3.2.5 LinkedList
Pfeil 3.2.6 Der Feld-Adapter Arrays.asList()
Pfeil 3.2.7 ListIterator *
Pfeil 3.2.8 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
Pfeil 3.2.9 Primitive Elemente in Datenstrukturen verwalten
Pfeil 3.3 Mengen (Sets)
Pfeil 3.3.1 Ein erstes Mengen-Beispiel
Pfeil 3.3.2 Methoden der Schnittstelle Set
Pfeil 3.3.3 HashSet
Pfeil 3.3.4 TreeSet – die sortierte Menge
Pfeil 3.3.5 Die Schnittstellen NavigableSet und SortedSet
Pfeil 3.3.6 LinkedHashSet
Pfeil 3.4 Stack (Kellerspeicher, Stapel)
Pfeil 3.4.1 Die Methoden von Stack
Pfeil 3.5 Queues (Schlangen) und Deques
Pfeil 3.5.1 Queue-Klassen
Pfeil 3.5.2 Deque-Klassen
Pfeil 3.5.3 Blockierende Queues und Prioritätswarteschlangen
Pfeil 3.5.4 PriorityQueue
Pfeil 3.6 Assoziative Speicher
Pfeil 3.6.1 Die Klassen HashMap und TreeMap
Pfeil 3.6.2 Einfügen und Abfragen der Datenstruktur
Pfeil 3.6.3 Über die Bedeutung von equals() und hashCode()
Pfeil 3.6.4 Eigene Objekte hashen
Pfeil 3.6.5 IdentityHashMap
Pfeil 3.6.6 Das Problem von veränderten Elementen
Pfeil 3.6.7 Aufzählungen und Ansichten des Assoziativspeichers
Pfeil 3.6.8 Die Arbeitsweise einer Hash-Tabelle *
Pfeil 3.7 Die Properties-Klasse
Pfeil 3.7.1 Properties setzen und lesen
Pfeil 3.7.2 Properties verketten
Pfeil 3.7.3 Hierarchische Eigenschaften
Pfeil 3.7.4 Eigenschaften auf der Konsole ausgeben *
Pfeil 3.7.5 Properties laden und speichern
Pfeil 3.7.6 Klassenbeziehungen: Properties und Hashtable *
Pfeil 3.8 Mit einem Iterator durch die Daten wandern
Pfeil 3.8.1 Die Schnittstelle Iterator
Pfeil 3.8.2 Der Iterator kann (eventuell auch) löschen
Pfeil 3.8.3 Einen Zufallszahleniterator schreiben
Pfeil 3.8.4 Iteratoren von Sammlungen, das erweiterte for und Iterable
Pfeil 3.8.5 Fail-Fast-Iterator und die ConcurrentModificationException
Pfeil 3.8.6 Die Schnittstelle Enumerator *
Pfeil 3.9 Algorithmen in Collections
Pfeil 3.9.1 Die Bedeutung von Ordnung mit Comparator und Comparable
Pfeil 3.9.2 Sortieren
Pfeil 3.9.3 Den größten und kleinsten Wert einer Collection finden
Pfeil 3.9.4 Nicht-änderbare Datenstrukturen, immutable oder nur-lesen?
Pfeil 3.9.5 Null Object Pattern und leere Sammlungen/Iteratoren zurückgeben
Pfeil 3.9.6 Mit der Halbierungssuche nach Elementen fahnden
Pfeil 3.9.7 Ersetzen, Kopieren, Füllen, Umdrehen, Rotieren *
Pfeil 3.9.8 Listen durchwürfeln *
Pfeil 3.9.9 Häufigkeit eines Elements *
Pfeil 3.9.10 Singletons *
Pfeil 3.9.11 nCopies() *
Pfeil 3.10 Spezielle thread-sichere Datenstrukturen
Pfeil 3.10.1 Wait-free-Algorithmen
Pfeil 3.10.2 Nebenläufiger Assoziativspeicher und die Schnittstelle ConcurrentMap
Pfeil 3.10.3 ConcurrentLinkedQueue
Pfeil 3.10.4 CopyOnWriteArrayList und CopyOnWriteArraySet
Pfeil 3.10.5 Wrapper zur Synchronisation
Pfeil 3.10.6 Blockierende Warteschlangen
Pfeil 3.10.7 ArrayBlockingQueue und LinkedBlockingQueue
Pfeil 3.10.8 PriorityBlockingQueue
Pfeil 3.11 Google Guava (aka Google Collections Library)
Pfeil 3.11.1 Beispiel Multi-Set und Multi-Map
Pfeil 3.11.2 Datenstrukturen aus Guava
Pfeil 3.11.3 Utility-Klassen von Guava
Pfeil 3.11.4 Prädikate
Pfeil 3.11.5 Transformationen
Pfeil 3.12 Die Klasse BitSet für Bitmengen *
Pfeil 3.12.1 Ein BitSet anlegen, füllen und erfragen
Pfeil 3.12.2 Mengenorientierte Operationen
Pfeil 3.12.3 Methodenübersicht
Pfeil 3.12.4 Primzahlen in einem BitSet verwalten
Pfeil 3.13 Zum Weiterlesen

Rheinwerk Computing - Zum Seitenanfang

3.6 Assoziative SpeicherZur 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 Wertes.


Rheinwerk Computing - Zum Seitenanfang

3.6.1 Die Klassen HashMap und TreeMapZur nächsten ÜberschriftZur vorigen Ü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.
Beispiel

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

Map<String, String> aldiSupplier = new HashMap<String, String>();
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<String, Number>();
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 Baum-orientierten Verfahren nicht nötig – hier muss nur eine Ordnung zwischen den Elementen entweder mit Comparable oder Comparator her.

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

Abbildung

Abbildung 3.8: Klassendiagramm der Schnittstelle Map

Die Klasse HashMap

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

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 seit Java 6 die Schnittstelle NavigableMap, die wiederum von der Schnittstelle SortedMap[21](Vor Java 6 war dies die implementierte Schnittstelle.) 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 mit Methoden wie firstKey(), lastKey() und kann mit subMap() und tailMap() Teilansichten des Assoziativspeichers bilden.

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.


Rheinwerk Computing - Zum Seitenanfang

3.6.2 Einfügen und Abfragen der DatenstrukturZur nächsten ÜberschriftZur vorigen Ü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-Werte-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. Der Schlüssel und der Wert können null sein.

interface java.util.Map<K,V>
  • V put(K key, V value)
    Speichert den Schlüssel und den Wert in der Hash-Tabelle. Falls sich zu diesem Schlüssel schon ein Eintrag in der Hash-Tabelle 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-Werte-Paar in dem Assoziativspeicher lag.
  • void putAll(Map<? extends K, ? extends V> m)
    Fügt alle Schlüssel-Werte-Paare aus m in die aktuelle Map ein. Auch diese Methode überschreibt unter Umständen vorhandene Schlüssel.

Daten auslesen

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

Beispiel

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

Map<String, Number> num = new HashMap<String, Number>();
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.

Existiert der Schlüssel, existiert der Wert?

Neben get() kann auch mit einer anderen Methode das Vorhandensein eines Schlüssels getestet werden: containsKey() überprüft, ob ein Schlüssel in der Tabelle vorkommt, und gibt dann ein true zurück. Die Implementierung unterscheidet sich nicht wesentlich von get().

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 in der Hash-Tabelle 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 und die Map löschen

Zum Löschen eines Elements gibt es 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 in der Hash-Tabelle ist, so bewirkt die Methode nichts. Im letzten Atemzug wird noch der Wert zum Schlüssel zurückgegeben.
  • void clear()
    Löscht die Hash-Tabelle so, dass sie keine Werte mehr enthält.

Größe und Leertest

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

toString(), Gleichheitstest, Hash-Wert und Klon einer Hash-Tabelle *

toString() liefert eine Zeichenkette, die eine Repräsentation der Hash-Tabelle zurückgibt. Die Stringrepräsentation der Hash-Tabelle liefert jeden enthaltenen Schlüssel, gefolgt von einem Gleichheitszeichen und dem zugehörigen Wert. Aus Object überschreiben die JDK-Standardimplementierungen die Methoden equals() und hashCode(), die eine Map wie HashMap beide implementiert. Jede HashMap/TreeMap besitzt zudem eine clone()-Methode, die eine Kopie der Hash-Tabelle 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-Werte-Objekten betrifft also immer beide Datenstrukturen, und eine unsachgemäße Modifikation kann zu Unregelmäßigkeiten im Original führen.

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

Rheinwerk Computing - Zum Seitenanfang

3.6.3 Über die Bedeutung von equals() und hashCode()Zur nächsten ÜberschriftZur vorigen Überschrift

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

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

Map<Point, String> map = new HashMap<Point, String>();
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 Hashcode 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 Anfrage ist ja das zu erfragende Objekt nicht bekannt. Daher kann der Vergleich nur auf Gleichheit, nicht aber auf Identität stattfinden.


Rheinwerk Computing - Zum Seitenanfang

3.6.4 Eigene Objekte hashenZur nächsten ÜberschriftZur vorigen Ü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. Viele Standard-Klassen, wie String oder Point, erfüllen diese Anforderung, andere, wie StringBuilder, wiederum nicht. Für Schlüsselobjekte in einer NavigableMap ist hashCode() natürlich nicht erforderlich.

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

Listing 3.17: com/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;
if ( string == null )
if ( ((EqualsIgnoreCaseString) obj).string != null )
return false;
return string.equals( ((EqualsIgnoreCaseString) obj).string );
}
}

Ein kleiner Test mit den Rückgaben im Kommentar:

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

Map<EqualsIgnoreCaseString, String> map =
new HashMap<EqualsIgnoreCaseString, String>();
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

Rheinwerk Computing - Zum Seitenanfang

3.6.5 IdentityHashMapZur nächsten ÜberschriftZur vorigen Ü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.


Rheinwerk Computing - Zum Seitenanfang

3.6.6 Das Problem von veränderten ElementenZur nächsten ÜberschriftZur vorigen Überschrift

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

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

Map<Point, String> map = new HashMap<Point, String>();
Point q = new Point( 10, 10 );
map.put( q, "Punkt q" );
q.x = 12345;
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 Hashcode und sucht in den internen Datenstrukturen. Ändert sich der Hashcode 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.


Rheinwerk Computing - Zum Seitenanfang

3.6.7 Aufzählungen und Ansichten des AssoziativspeichersZur nächsten ÜberschriftZur vorigen Ü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 jedoch auf drei Arten Collection-Sammlungen zurückgeben, über die sich iterieren lässt:

  • keySet() liefert eine Menge der Schlüssel.
  • values() liefert eine Collection der Werte.
  • entrySet() liefert ein Set 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, es sei denn, die Map ist eine NavigableMap, wo ein Comparator die Ordnung vorgibt oder die Elemente Comparable sind.

Beispiel

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

HashMap<String,String> h = new HashMap<String,String>();
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@pro-christkind.at" );
for ( String elem : h.keySet() )
System.out.println( elem );

Liefert:

Christkind
Webmaster
C.Ullenboom
Weihnachtsmann

Für die Werte ist kein valueSet() möglich, weil ein Wert mehr als einmal vorkommen kann und eine Menge laut Definition einen Wert nicht zweimal enthalten darf. values() liefert die spezielle Collection mit den Werten – iterator() auf dieser Collection bietet dann eine Aufzählung nach Werten. Über den Iterator oder die Collection können Elemente aus der Map gelöscht, aber keine neuen eingefügt werden.

Beispiel

Laufe die Werte einer HashMap mit einem Iterator ab:

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

Das liefert:

wunsch@pro-christkind.at
C.Ullenboom@no-spam.com
C.Ullenboom@spammer.com
Wunsch@weihnachtsmann.com

Während keySet() nur die eindeutigen Schlüssel in einer Menge liefert, gibt entrySet() eine Menge von Objekten vom Typ Map.Entry zurück. Entry ist eine innere Schnittstelle in der Schnittstelle Map, die Schlüssel-Werte-Paare speichert. Die wichtigen Operationen dieser Schnittstelle sind getKey(), getValue() und setValue(), wobei die letzte Methode von HashMap angeboten wird, aber eine optionale Operation ist.

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

Abbildung

Abbildung 3.9: Dieses UML-Diagramm zeigt den inneren Typ Entry in Map

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

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.

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ösch-Operationen 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 3.20: com/tutego/insel/util/map/MapView, main()

Map<Integer, String> m = new HashMap<Integer, String>();
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 ); // {}

Rheinwerk Computing - Zum Seitenanfang

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

Die Hash-Tabelle arbeitet mit Schlüssel-Werte-Paaren. Aus dem Schlüssel wird nach einer mathematischen Funktion – der sogenannten Hash-Funktion – ein 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 Hashcode 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 benutzt eine verkettete Liste hinter jedem Feldelement (einen sogenannten Bucket); diese Implementierungsvariante heißt Hashing mit Verkettung. Falls eine Kollision auftritt, wird ein kleines Behälterobjekt mit dem Schlüssel und Wert aufgebaut und als Element an die Liste angehängt. Eine Sortierung findet nicht statt. Wir merken, dass es auf eine geschickte Wahl der Hash-Funktion ankommt. Denn eine »dumme« Hash-Funktion, die beispielsweise alle Schlüssel nur auf einen Indexwert abbilden würde, erreicht keine Verteilung, sondern lediglich eine lange Liste von Schlüssel-Werte-Paaren; das nennt sich Clustering. Doch auch bei der besten Verteilung über 77 Elemente ist nach dem Einfügen des 78. Elements irgendwo eine Liste mit mindestens zwei Elementen aufgebaut. Je länger die Listen der miteinander kollidierenden Einträge werden, desto langsamer wird der Zugriff auf die Datenstrukturen, die auf Hashing basieren.

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 und die Konstruktoren

Wir haben oben schon kurz über den Füllfaktor gesprochen. Dieser gibt 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 rehash. 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 Rehashen kann nicht ausdrücklich erzwungen werden.

class java.util.HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

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



Ihr Kommentar

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

>> Zum Feedback-Formular
<< zurück
  Zum Katalog
Neuauflage: Java SE 8 Standard-Bibliothek
Neuauflage: Java SE 8 Standard-Bibliothek
Jetzt bestellen


 Ihre Meinung?
Wie hat Ihnen das <openbook> gefallen?
Ihre Meinung

 Buchempfehlungen
Zum Katalog: Professionell entwickeln mit Java EE 7






 Professionell
 entwickeln mit
 Java EE 7


Zum Katalog: Java ist auch eine Insel






 Java ist auch
 eine Insel


Zum Katalog: Einstieg in Eclipse






 Einstieg in Eclipse


Zum Katalog: Einstieg in Java






 Einstieg in Java


 Shopping
Versandkostenfrei bestellen in Deutschland und Österreich
InfoInfo




Copyright © Rheinwerk Verlag GmbH 2012
Für Ihren privaten Gebrauch dürfen Sie die Online-Version natürlich ausdrucken. Ansonsten unterliegt das 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.


Nutzungsbestimmungen | Datenschutz | Impressum

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