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

Java ist auch eine Insel von Christian Ullenboom
Programmieren für die Java 2-Plattform in der Version 5 (Tiger-Release)
Buch: Java ist auch eine Insel
gp Kapitel 11 Datenstrukturen und Algorithmen
  gp 11.1 Mit einem Iterator durch die Daten wandern
    gp 11.1.1 Die Schnittstellen Enumeration und Iterator
  gp 11.2 Datenstrukturen und die Collection-API
    gp 11.2.1 Die Schnittstelle Collection
    gp 11.2.2 Das erste Programm mit Container-Klassen
    gp 11.2.3 Generische Datentypen in der Collection-API
    gp 11.2.4 Der Iterator, die Schnittstelle Iterable und das erweiterte for
    gp 11.2.5 Schnittstellen, die Collection erweitern, und Map
    gp 11.2.6 Konkrete Container-Klassen
  gp 11.3 Listen
    gp 11.3.1 AbstractList
    gp 11.3.2 Beispiel mit List-Methoden
    gp 11.3.3 ArrayList
    gp 11.3.4 asList() und die »echten« Listen
    gp 11.3.5 toArray() von Collection verstehen – die Gefahr einer Falle erkennen
    gp 11.3.6 Die interne Arbeitsweise von ArrayList und Vector
    gp 11.3.7 LinkedList
  gp 11.4 Stack (Kellerspeicher, Stapel)
    gp 11.4.1 Die Methoden von Stack
    gp 11.4.2 Ein Stack ist ein Vector – aha!
  gp 11.5 Queues (Schlangen)
    gp 11.5.1 Blockierende Queues und Prioritätswarteschlangen
  gp 11.6 Assoziative Speicher und die Klasse HashMap
    gp 11.6.1 Ein Objekt der Klasse HashMap erzeugen
    gp 11.6.2 Einfügen und Abfragen der Datenstruktur
    gp 11.6.3 Wichtige Eigenschaften von Assoziativspeichern
    gp 11.6.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben
    gp 11.6.5 Die Arbeitsweise einer Hash-Tabelle
    gp 11.6.6 Aufzählen der Elemente
    gp 11.6.7 Der Gleichheitstest und der Hash-Wert einer Hash-Tabelle
    gp 11.6.8 Klonen
  gp 11.7 Die Properties-Klasse
    gp 11.7.1 Properties setzen und lesen
    gp 11.7.2 Properties verketten
    gp 11.7.3 Eigenschaften ausgeben
    gp 11.7.4 Hierarchische Eigenschaften
    gp 11.7.5 Properties speichern
    gp 11.7.6 Über die Beziehung Properties und Hashtable
  gp 11.8 Mengen (Sets)
    gp 11.8.1 HashSet
    gp 11.8.2 TreeSet – die Menge durch Bäume
  gp 11.9 Algorithmen in Collections
    gp 11.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren
    gp 11.9.2 Vergleichen von Objekten mit Comparator und Comparable
    gp 11.9.3 Größten und kleinsten Wert einer Collection finden
    gp 11.9.4 Sortieren
    gp 11.9.5 nCopies()
    gp 11.9.6 Singletons
    gp 11.9.7 Elemente in der Collection suchen
  gp 11.10 Synchronisation der Datenstrukturen
  gp 11.11 Die abstrakten Basisklassen für Container
    gp 11.11.1 Optionale Methoden
  gp 11.12 Die Klasse BitSet für Bitmengen
    gp 11.12.1 Ein BitSet anlegen und füllen
    gp 11.12.2 Mengenorientierte Operationen
    gp 11.12.3 Funktionsübersicht
    gp 11.12.4 Primzahlen in einem BitSet verwalten
  gp 11.13 Ein Design-Pattern durch Beobachten von Änderungen
    gp 11.13.1 Design-Pattern
    gp 11.13.2 Das Beobachter-Pattern (Observer/Observable)


Galileo Computing

11.6 Assoziative Speicher und die Klasse HashMadowntop

Es gibt unterschiedliche Arten, wie ein assoziativer Speicher implementiert werden kann. Eine übliche und sehr schnelle Implementierung ist die Hash-Tabelle (engl. hashtable), implementiert in Java durch java.uti.HashMap. Daneben existiert die Klasse java.util.TreeMap, die etwas langsamer im Zugriff ist, doch dafür die die Schlüssel alle sortiert.

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


Galileo Computing

11.6.1 Ein Objekt der Klasse HashMap erzeugen  downtop

Die Klasse HashMap eignet sich ideal dazu, viele Elemente unsortiert zu speichern und sie über die Schlüssel schnell wieder verfügbar zu machen. Für eine geringe Anzahl von Elementen könnte unter Umständen eine Liste besser geeignet sein, da sie etwas weniger Speicherplatz benötigt.



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

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

Galileo Computing

11.6.2 Einfügen und Abfragen der Datenstruktur  downtop

Wir haben gesagt, dass die Elemente der Hash-Tabelle 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(). Das erste Argument ist der Schlüssel und das zweite Argument der mit dem Schlüssel zu assozierende Wert. Der Schlüssel und der Wert können null sein.


Beispiel   Eine Hash-Tabelle, der wir Werte hinzufügen

HashMap<String,String> alidhersteller = new HashMap<String,String> ();  // <sup>6 
    </sup>
alidhersteller.  put  ( "Carbo, spanischer Sekt", "Freixenet" );
alidhersteller.  put  ( "ibu Stapelchips", "Bahlsen Chipsletten" );
alidhersteller.  put  ( "Ko-kra Katzenfutter", "felix Katzenfutter" );
alidhersteller.  put  ( "Küchenpapier", "Zewa" );

alidhersteller.  put  ( "Nuss-Nougat-Creme", "Zentis" );
alidhersteller.  put  ( "Pommes Frites", "McCaine" );
HashMap<String,Number> num = new HashMap<String,Number>();
num.  put  ( "zwei", new Integer(2) );
num.  put  ( "drei", new Float(3.0f) );

Für Objekte, die als Schlüssel in einer Hash-Tabelle dienen sollen, müssen die Methoden hashCode() und equals() in geeigneter Weise (der Bedeutung oder Semantik des Objekts entsprechend) untereinander konsistent implementiert sein.

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

gp  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, so wird der alte Wert überschrieben und der vorherige Wert zum Schlüssel zurückgegeben. 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. Die Methode ist vom Interface Map vorgegeben. Sie überschreibt die Methode aus der Oberklasse AbstractMap.
gp  void putAll( Map<? extends K, ? extends V> m )
Fügt alle Schlüssel-Werte-Paare aus t in die aktuelle Map ein. Die Operation überschreibt unter Umständen vorhandene Schlüssel.

Daten auslesen

Um wieder ein Element auszulesen, verwenden wir get(key). Das Argument identifiziert das zu findende Objekt über den Schlüssel, in dem das Objekt herausgesucht wird, welchen den gleichen Hashwert besitzt und im Sinne von equals() 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, denn null ist als Wert durchaus erlaubt.


Beispiel   Erfrage den Assoziativspeicher nach »zwei«. Das Ergebnis wird ein Integer-Objekt sein. Wurde der Typ nicht angegeben, ist eine Typanpassung nötig. Mit Generics kann diese Typanpassung entfallen, wenn – wie in unserem Beispiel – Number-Objekte mit dem String assoziiert waren. Dann muss aber mit Generics der Typ Number sein. Das ist in Ordnung, denn jedes konkrete Number-Objekt hat die Methode intValue().

Integer n = (Integer) numbers.  get  ( "zwei" );

if ( n != null )
  System.out.println( "zwei = " + n.intValue() );



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

gp  V get( Object key )
Liefert das erfragte Objekt, welches mit dem entsprechenden Schlüssel verbunden ist, vorgegeben vom Interface Map. Es überschreibt die Methode von Dictionary. Falls kein passendes Objekt vorhanden ist, liefert die Funktion null.

Existiert der Schlüssel, existiert der Wert?

Neben get() kann auch noch mit einer anderen Funktion 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.



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

gp  boolean containsKey( Object key )
Liefert true, falls der Schlüssel in der Hash-Tabelle vorkommt; Vorgabe vom Interface Map. Der Vergleich auf Gleichheit wird mit equals() durchgeführt. 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 die Gleichheit ihrer hashCode()s folgen.
gp  boolean containsValue( Object value )
Liefert true, falls der Assoziativspeicher ein oder mehrere Werte enthält, die mit dem Objekt inhaltlich (also per equals()) übereinstimmen; Vorgabe vom Interface Map.

Einträge und die Map löschen

Zum Löschen eines Elements gibt es remove() und zum Löschen der gesamten Map die Funktion clear(). clear() kann interessant sein, da sich der Assoziativspeicher weiterverwenden lässt, ohne dass ein neues Exemplar angelegt werden muss. Das kann unter günstigen Umständen die Performanz steigern.



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

gp  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 macht die Funktion nichts. Im letzten Atemzug wird noch der Wert zum Schlüssel zurückgegeben.
gp  void clear()
Löscht die Hash-Tabelle, so dass sie keine Werte mehr enthält.

Abbildung
Hier klicken, um das Bild zu Vergrößern

Sonstiges

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


Galileo Computing

11.6.3 Wichtige Eigenschaften von Assoziativspeichern  downtop

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:


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

In die HashMap wird ein Punkt p1 mit einer Zeichenkette assoziiert. 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( hm1.get(p2) );           // ???

Die Antwort ergibt tatsächlich 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, so dass dies als ein Fund zu werten ist. (Das liefert noch einmal einen wichtigen Hinweis, dass immer beide Funktionen 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.


Galileo Computing

11.6.4 Elemente im Assoziativspeicher müssen unveränderbar bleiben  downtop

Ein Hashcode ergibt sich aus den Attributen eines Objekts. Zum Finden eines Objekts in einem Assoziativspeicher wird dann nach dem Hash-Wert gesucht. Dumm ist, wenn sich dieser in der Zwischenzeit ändert.


Point q = new Point( 10, 10 );
Map<Point,String> hm = new HashMap<Point,String>();
hm.put( q, "Punkt q" );
q.x = 12345;
System.out.println( hm.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. Änderte sich jedoch der Hashcode zwischendurch, kann das Element nicht mehr gefunden werden und liegt als Leiche in der Map. Daher kann nur davor gewarnt werden, Objektattribute von Objekten, die durch Assoziativspeicher verwaltet werden, nachträglich zu ändern. Das Prinzip Hashing benutzt gerade diese Eigenschaft, Objekte durch unveränderte Zustände wieder zu finden.


Galileo Computing

11.6.5 Die Arbeitsweise einer Hash-Tabelle  downtop

Die Hash-Tabelle arbeitet mit Schlüssel-Werte-Paaren. Aus dem Schlüssel wird nach einer Funktion – der so genannten Hash-Funktion – ein Hashcode berechnet. Dieser dient dann als Index für ein internes Array. Dieses Array hat zu 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 auf 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. Denn wenn zwei unterschiedliche Wörter denselben Hashcode besitzen, dann kommt es zu einer Kollision. Darauf muss die Datenstruktur vorbereitet sein. Hier gibt es verschiedene Lösungsansätze. Die unter Java implementierte Variante benutzt eine verkettete Liste. Falls eine Kollision auftritt, so wird der Hashcode beibehalten und der Schlüssel beziehungsweise Wert in einem Listen-Element an den vorhandenen Eintrag 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. 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 Datenstruktur HashMap und Hashtable.

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 genau so 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 Prozent. Es gibt einen Konstruktor für HashMap/Hashtable-Exemplare, der die Angabe eines Füllgrads erlaubt. Ist dieser überschritten, so 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

gp  HashMap()
Die Hash-Tabelle enthält initial eine Kapazität von 16 Einträgen und einen Füllfaktor von 75  %, also 0.75.
gp  HashMap( int initialCapacity )
Erzeugt eine Hash-Tabelle mit einer vorgegebenen Kapazität und dem Füllfaktor 0.75.
gp  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 Arrays lässt sich in den beiden anderen Konstruktoren angeben. Ist dort ein unsinniger Wert angegeben, wird eine IllegalArgumentException ausgeworfen. Zusätzlich kann der Füllfaktor angegeben werden; ist dieser falsch, so wird ebenfalls diese Exception 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 etwa 1000 * (1/0.75) = 1333. Ist ein Füllfaktor nicht explizit angegeben, so 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.


Galileo Computing

11.6.6 Aufzählen der Elemente  downtop

Eine HashMap gibt mit keySet() eine Ergebnismenge für die Schlüssel zurück, so dass ein Iterator über alle Werte laufen kann. Natürlich gibt es keine definierte Reihenfolge.


Beispiel   Laufe die Schlüssel einer HashMap mit einem Iterator ab.

HashMap<String,String> h = new HashMap<String,String>();
h.put( "C.Ullenboom", "C.Ullenboom@java-tutor.com" );
h.put( "Webmaster", "C.Ullenboom@java-tutor.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 kann es kein valueSet() geben, da ein Wert mehr als einmal vorkommen kann und eine Menge laut Definition ein Wert nicht zweimal enthalten darf. Dennoch gibt es die Objektfunktion values(), die eine spezielle Collection mit den Werten liefert. iterator() auf dieser Collection liefert 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@java-tutor.com
C.Ullenboom@java-tutor.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 Klasse Map, welches Schlüssel-Werte-Paare speichert. Die wichtigen Funktionen dieser Schnittstelle sind Object getKey(), Object getValue() und Object setValue(Object value), wobei die letzte Funktion von HashMap angeboten wird, aber eine optionale Funktion 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() );

Wir müssen uns bewusst sein, dass Mengen keine Kopie der Werte sind, sondern dass sich bei Veränderungen das Original verändert.



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

gp  Set<K> keySet()
Liefert eine Menge mit den Schlüsseln.
gp  Set<Map.Entry<K,V>> entrySet()
Liefert eine Menge von Map.Entry-Objekten, die Zugriff auf die Schlüssel und Werte bieten.
gp  Collection<V> values()
Liefert eine Sammlung der Werte.

Galileo Computing

11.6.7 Der Gleichheitstest und der Hash-Wert einer Hash-Tabelle  downtop

Aus Object stammen die Funktionen equals() und hashCode(), die HashMap beide implementiert.



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

gp  boolean equals( Object o )
Damit die Gleichheit von zwei Hash-Tabellen gezeigt werden kann, vergleicht equals() alle Elemente von beiden Tabellen.
gp  int hashCode()
Liefert den Hashcode des Objekts. Das ist wichtig, wenn eine Hash-Tabelle selbst als Schlüssel benutzt werden soll. Dies ist jedoch problematisch, falls die Hash-Tabelle später noch verändert werden soll.

Galileo Computing

11.6.8 Klonen  toptop

Jede HashMap besitzt eine clone()-Methode, die eine Kopie der Hash-Tabelle erzeugt. Die Kopie bezieht sich allerdings nur auf die Hash-Tabelle 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.



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

gp  clone()
Fertigt eine Kopie der Hash-Tabelle an, ohne jedoch die Werte selbst zu klonen.





1   Siehe dazu auch http://www.aldibaran.de/faq/faq5.html#2.

2   Unter JDK 1.3 besaß die Hashtable im Standard-Konstruktor 101 Elemente, dann in den frühen 1.4-Versionen 11 Elemente und seit 1.4.1 in einer ganz neuen Implementierung des Hashings 16 Elemente – eine Zweierpotenz. Ja! Richtig gesehen, keine Primzahl.

3   Fast schon philosophisch wird’s, wenn eine Hash-Tabelle als Schlüssel oder Wert in sich selbst eingefügt werden soll.





Copyright © Galileo Press GmbH 2004
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.


[Galileo Computing]

Galileo Press GmbH, Gartenstraße 24, 53229 Bonn, Tel.: 0228.42150.0, Fax 0228.42150.77, info@galileo-press.de