Discussion:
Probleme mit HashMap
(zu alt für eine Antwort)
Stefan Schulze
2003-10-25 04:41:17 UTC
Permalink
Moin...
Ich füg hier Elemente in eine HashMap ein, doch dabei kommt es manchmal
dazu, dass der neue Wert einen alten einfach ersetzt. Allerdings liegt
es nicht daran, dass es zu einer Kollision kam... Sicher bin ich mir
dessen, weil ich vorher den Key nach einem bestimmten System
modifiziere, bis die Methode HashMap#existsKey(Object key) false
zurückgibt. Außerdem sollte die put-Methode ja bei einer Kollision den
alten Wert zurückgeben bzw. null wenn es keine Kollision gab. Der
Rückgabewert ist in dem kritischen Fall jedoch null (und der ersetzte
Wert ist ungleich null).
Außerdem wird die private size-Variable von HashMap trotz der Ersetzung
hochgesetzt - vor dem kritischen put waren drei Werte in der HashMap und
die size()=3, nach dem put sind immer noch drei Werte in der Map (der
eine halt ersetzt und der neue eingefügt) aber size()=4.

Hat irgendwer 'ne Ahnung woran das liegen könnte? Ich häng hier schen
seit einigen Stunden an dem Problem und step mich hier durchs ganze
Modul um den Fehler zu finden, aber leider erfolglos...

CU
Stefan
--
Also, wenn die Mehrheit dämlich ist [...], wird es nicht besser,
wenn ich die auch noch alle vernetze, sorry....
[Thomas Schmidt in de.sci.informatik.misc]
Lothar Kimmeringer
2003-10-25 08:42:15 UTC
Permalink
On Sat, 25 Oct 2003 06:41:17 +0200, Stefan Schulze wrote:

[magische Dinge passieren in HashMap]
Post by Stefan Schulze
Hat irgendwer 'ne Ahnung woran das liegen könnte? Ich häng hier schen
seit einigen Stunden an dem Problem und step mich hier durchs ganze
Modul um den Fehler zu finden, aber leider erfolglos...
Versuche das ganze mal auf ein paar Zeilen Javacode zu
reduzieren, die das Problem reproduzieren lassen. Ohne
genaueres ueber Deine Keys und Values zu wissen und die
Art, wie Du diese in die HashMap reinschreibst und raus-
holst, kann man nur raten.

Als Vokal kaufe ich die Vermutung, dass Du fuer Deinen
Key ein eigenes Objekt benutzt und irgendwelche Schweinereien
mit der equals-Methode angefangen hast.


Gruesse, Lothar
--
Lothar Kimmeringer E-Mail: ***@kimmeringer.de
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
questions!
Stefan Schulze
2003-10-25 16:17:41 UTC
Permalink
Post by Lothar Kimmeringer
Versuche das ganze mal auf ein paar Zeilen Javacode zu
reduzieren, die das Problem reproduzieren lassen. Ohne
genaueres ueber Deine Keys und Values zu wissen und die
Art, wie Du diese in die HashMap reinschreibst und raus-
holst, kann man nur raten.
'nen Javacode dazu findest du als Antwort auf Michael...
In meiner eigentlichen Anwendung sind die Values etwas komplexer als in
meinem vereinfachten Beispiel, aber mit Strings gehts auch... Die Keys
sind exakt die gleichen (zumindest per equals())wie die entsprechenden
in der Anwendung.
Post by Lothar Kimmeringer
Als Vokal kaufe ich die Vermutung, dass Du fuer Deinen
Key ein eigenes Objekt benutzt und irgendwelche Schweinereien
mit der equals-Methode angefangen hast.
Naja... Leider knapp daneben... :-)

CU
Stefan
--
Also, wenn die Mehrheit dämlich ist [...], wird es nicht besser,
wenn ich die auch noch alle vernetze, sorry....
[Thomas Schmidt in de.sci.informatik.misc]
michael paap
2003-10-25 09:00:41 UTC
Permalink
Post by Stefan Schulze
Ich füg hier Elemente in eine HashMap ein, doch dabei kommt es manchmal
dazu, dass der neue Wert einen alten einfach ersetzt.
Das passiert dann, wenn der Key gleich ist. Gleich ist er dann, wenn
equals() auf den beiden Keys ausgeführt true liefert.
Post by Stefan Schulze
Allerdings liegt
es nicht daran, dass es zu einer Kollision kam... Sicher bin ich mir
dessen, weil ich vorher den Key nach einem bestimmten System
modifiziere, bis die Methode HashMap#existsKey(Object key) false
zurückgibt.
Eine Kollision meint auch eigentlich bei Hashing etwas völlig anderes
und hat nichts mit identischen Keys zu tun.
http://www.google.com/search?q=kollision+hashing&ie=UTF-8&oe=UTF-8&hl=de&btnG=Google+Suche&lr=
Post by Stefan Schulze
Außerdem sollte die put-Methode ja bei einer Kollision den
alten Wert zurückgeben bzw. null wenn es keine Kollision gab.
S.o. Was Du meinst sind keine Kollisionen, sondern schlicht das
überschreiben eines alten Value durch einen neuen für den gleichen Key.
Post by Stefan Schulze
Außerdem wird die private size-Variable von HashMap trotz der Ersetzung
hochgesetzt - vor dem kritischen put waren drei Werte in der HashMap und
die size()=3, nach dem put sind immer noch drei Werte in der Map (der
eine halt ersetzt und der neue eingefügt) aber size()=4.
Hat irgendwer 'ne Ahnung woran das liegen könnte?
Problem auf das nachvollziehbare Minimum reduzieren. Minimalen
compilierbaren Code, der das fragwürdige Verhalten zeigt posten.

Gruß,
Michael
--
Sollte ausnahmsweise eine Mail-Antwort auf ein Posting vonnöten sein,
bitte folgende Adresse verwenden: newsreply@<Absender-Domain>.
Stefan Schulze
2003-10-25 16:08:30 UTC
Permalink
Post by michael paap
Das passiert dann, wenn der Key gleich ist. Gleich ist er dann, wenn
equals() auf den beiden Keys ausgeführt true liefert.
Die Keys waren Doubles und ich hab mich - wie geschrieben - auf mehreren
Wegen versichert, dass dem nicht so ist.
Post by michael paap
Eine Kollision meint auch eigentlich bei Hashing etwas völlig anderes
und hat nichts mit identischen Keys zu tun.
Kollision beim Hashing ist doch, wenn mehrere Werte in die gleiche
"Zelle" der Hashtable geschrieben werden würden (je nach
Kollisionsbehandlung). Ausgelöst wird das doch üblicherweise durch
gleiche Hashwerte - was bei den HashMaps ja doch gleich dem eingegebenen
Key ist, oder?
Post by michael paap
Was Du meinst sind keine Kollisionen, sondern schlicht das
überschreiben eines alten Value durch einen neuen für den gleichen Key.
Was doch eben die "Kollisionsbehandlung" bei den HashMaps ist...
Post by michael paap
Problem auf das nachvollziehbare Minimum reduzieren. Minimalen
compilierbaren Code, der das fragwürdige Verhalten zeigt posten.
import java.util.HashMap;
public class test {
public static void main(String[] args) {
HashMap map=new HashMap();
Double key1=new Double(5400);
Double key2=new Double(5400.000001);
Double key3=new Double(8407.546875);
Double key4=new Double(5400.000002);
String value1=new String("value1");
String value2=new String("value2");
String value3=new String("value3");
String value4=new String("value4");

map.put(key1,value1);
map.put(key2,value2);
map.put(key3,value3);
map.put(key4,value4);
}
}

CU
Stefan
--
Also, wenn die Mehrheit dämlich ist [...], wird es nicht besser,
wenn ich die auch noch alle vernetze, sorry....
[Thomas Schmidt in de.sci.informatik.misc]
Tobias Vogele
2003-10-25 16:44:38 UTC
Permalink
Hallo,

Stefan Schulze spoke:

[..]
Post by Stefan Schulze
map.put(key1,value1);
map.put(key2,value2);
map.put(key3,value3);
map.put(key4,value4);
Wenn ich hier ein
System.out.println(map.get(key1));
System.out.println(map.get(key2));
System.out.println(map.get(key3));
System.out.println(map.get(key4));
einfüge, wird das ausgegeben:

value1
value2
value3
value4

Also genau wie erwartet.
Gibt es bei Dir eine andere Ausgabe oder erwartest Du eine andere?

Grüße,

tobi
--
URL: http://www.wartmal.de Email: ***@wartmal.de
Stefan Schulze
2003-10-25 16:59:48 UTC
Permalink
Post by Tobias Vogele
Wenn ich hier ein
System.out.println(map.get(key1));
System.out.println(map.get(key2));
System.out.println(map.get(key3));
System.out.println(map.get(key4));
value1
value2
value3
value4
Also genau wie erwartet.
Gibt es bei Dir eine andere Ausgabe oder erwartest Du eine andere?
Also um ehrlich zu sein bin ich beim Debuggen (Der Debugger von
IntelliJ, beim JBuilder evtl auch) darauf gestoßen als ich einen Bug
gesucht habe. Da hab ich dann im Debugger gesehen, dass da anscheinend
in der internen Ansicht der HashMap ein Element (value3) von value4
überschrieben wurde...
Ich werd da in meinem Programm nochmal genauer gucken, wie es da ist und
das dann nachher hier posten...

CU
Stefan
--
Also, wenn die Mehrheit dämlich ist [...], wird es nicht besser,
wenn ich die auch noch alle vernetze, sorry....
[Thomas Schmidt in de.sci.informatik.misc]
Stefan Schulze
2003-10-25 17:08:56 UTC
Permalink
Post by Tobias Vogele
Wenn ich hier ein
System.out.println(map.get(key1));
System.out.println(map.get(key2));
System.out.println(map.get(key3));
System.out.println(map.get(key4));
value1
value2
value3
value4
Also genau wie erwartet.
Gibt es bei Dir eine andere Ausgabe oder erwartest Du eine andere?
Du hast Recht... wenn ich mir einen Wert nach dem anderen raussammel,
dann sind die alle da... Dann scheint das wohl irgendwie ein Bug im
Debugger zu sein...

Naja... Vielen Danke!
CU
Stefan
--
Also, wenn die Mehrheit dämlich ist [...], wird es nicht besser,
wenn ich die auch noch alle vernetze, sorry....
[Thomas Schmidt in de.sci.informatik.misc]
Joachim Karrer
2003-10-25 18:48:53 UTC
Permalink
Post by Stefan Schulze
Du hast Recht... wenn ich mir einen Wert nach dem anderen raussammel,
dann sind die alle da... Dann scheint das wohl irgendwie ein Bug im
Debugger zu sein...
Ich weiss schon, weswegen ich keinem Debugger, sondern nur dem logging
vertrau... ;)
Hendrik Lipka
2003-10-27 11:07:57 UTC
Permalink
On Sat, 25 Oct 2003 18:59:48 +0200, "Stefan Schulze"
Post by Stefan Schulze
Also um ehrlich zu sein bin ich beim Debuggen (Der Debugger von
IntelliJ, beim JBuilder evtl auch) darauf gestoßen als ich einen Bug
gesucht habe. Da hab ich dann im Debugger gesehen, dass da anscheinend
in der internen Ansicht der HashMap ein Element (value3) von value4
überschrieben wurde...
Könnte durchaus sein dass in der Hashmap da umsortiert wird, wenn man ein
Element reinschreibt. Oder dass man z.B. im Debugger erst mal nur das erste
Element eine Buckets zu sehen bekommt, und die anderen nicht gleich angezeigt
werden.
Aber frag doch einfach mal auf intellij.net nach, das weiss bestimmt jemand
was näheres...

hli
--
Gewalt ist die letzte Zuflucht des Unfaehigen
Joachim Karrer
2003-10-25 16:44:40 UTC
Permalink
Post by Stefan Schulze
Post by michael paap
Das passiert dann, wenn der Key gleich ist. Gleich ist er dann, wenn
equals() auf den beiden Keys ausgeführt true liefert.
Die Keys waren Doubles und ich hab mich - wie geschrieben - auf mehreren
Wegen versichert, dass dem nicht so ist.
Post by michael paap
Eine Kollision meint auch eigentlich bei Hashing etwas völlig anderes
und hat nichts mit identischen Keys zu tun.
Kollision beim Hashing ist doch, wenn mehrere Werte in die gleiche
"Zelle" der Hashtable geschrieben werden würden (je nach
Kollisionsbehandlung). Ausgelöst wird das doch üblicherweise durch
gleiche Hashwerte - was bei den HashMaps ja doch gleich dem eingegebenen
Key ist, oder?
eine Kollision tritt dann auf, wenn für zwei unterschiedliche Keys die
Hashfunktion den gleichen Wert ergibt, z.B. 42 % 7 = 6; 2001 % 7 = 6.
Eine Hashmap darf aber nicht den Wert in Index 6 (42) mit 2001
überschreiben, sondern legt eine Liste an, welche Werte auf dem Index 6 zu
liegen kommen (6 -> 42, 2001). Würde man jetzt noch 49 einfügen, so würde
die Liste ergänzt (6 -> 42, 2001, 49). Beim get() wird zuerst der Index
errechnet und dann der Wert in einer möglicherweise vorhandenen Liste
gesucht.
Post by Stefan Schulze
import java.util.HashMap;
public class test {
public static void main(String[] args) {
[BSP]
}
}
Bei mir kein Problem... alle 4 Werte in der Map...

Gruss
Stefan Schulze
2003-10-25 17:50:50 UTC
Permalink
Post by Joachim Karrer
eine Kollision tritt dann auf, wenn für zwei unterschiedliche Keys die
Hashfunktion den gleichen Wert ergibt, [...]
Okay... dann haben wir aneinander vorbeigeredet, bzw. ich hab die
HashMap falsch verstanden...
Ich dachte, dass der Key irgendwie der Hash wäre, nach dem einsortiert
wird. Wenn natürlich aus dem Key erst der wirklich benutzte Hashwert
errechnet wird, hast du selbstverständlich recht...
Post by Joachim Karrer
Post by Stefan Schulze
import java.util.HashMap;
public class test {
public static void main(String[] args) {
[BSP]
}
}
Bei mir kein Problem... alle 4 Werte in der Map...
hat sich grad schon mit dem Post von Tobias geklärt - anscheinend ist
der Fehler nicht bei mir oder in der HashMap (was mich auch sehr
gewundert hätte (also das es in der HashMap liegen würde)!) , sondern im
Debugger von IntelliJ (oder die HashMap wird intern ganz wirr
dargestellt).

CU
Stefan
--
Also, wenn die Mehrheit dämlich ist [...], wird es nicht besser,
wenn ich die auch noch alle vernetze, sorry....
[Thomas Schmidt in de.sci.informatik.misc]
Lothar Kimmeringer
2003-10-25 19:24:19 UTC
Permalink
Post by Stefan Schulze
Post by michael paap
Das passiert dann, wenn der Key gleich ist. Gleich ist er dann, wenn
equals() auf den beiden Keys ausgeführt true liefert.
Die Keys waren Doubles und ich hab mich - wie geschrieben - auf mehreren
Wegen versichert, dass dem nicht so ist.
Je nachdem, wo die Werte herkommen, ist die Verwendung von
Doubles als Key eine semischlaue Geschichte.

Nicht umsonst hat z.B. bei JUnit der assertEquals-Befehl
fuer das Vergleichen zweier doubles einen dritten Parameter
fuer die Toleranz.


Gruesse, Lothar
--
Lothar Kimmeringer E-Mail: ***@kimmeringer.de
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
questions!
Stefan Schulze
2003-10-25 20:08:12 UTC
Permalink
Post by Lothar Kimmeringer
Je nachdem, wo die Werte herkommen, ist die Verwendung von
Doubles als Key eine semischlaue Geschichte.
Die Doubles sind Flächen.
Es geht darum, dass eine Reihe von Zuständen eines Statecharts nach der
Fläche sortiert benötige.
Dabei ist eine 100%ige Präzision nicht nötig.
Wenn die Klasse mit der HashMap mir sagt, dass es den Key schon gibt,
wird er so lange minimal verändert (daher kamen die ,00000000[1|2]) und
dann an die entsprechende Stelle einsortiert.
Kann es denn in diesem Rahmen zu Problemen dadurch kommen?
Und wenn ja: Was ist denn das genaue Problem bei Doubles als Key und wie
wäre der schlauere Weg?

CU
Stefan
--
Also, wenn die Mehrheit dämlich ist [...], wird es nicht besser,
wenn ich die auch noch alle vernetze, sorry....
[Thomas Schmidt in de.sci.informatik.misc]
Lothar Kimmeringer
2003-10-26 22:09:12 UTC
Permalink
Post by Stefan Schulze
Wenn die Klasse mit der HashMap mir sagt, dass es den Key schon gibt,
wird er so lange minimal verändert (daher kamen die ,00000000[1|2]) und
dann an die entsprechende Stelle einsortiert.
Kann es denn in diesem Rahmen zu Problemen dadurch kommen?
Wenn Du spaeter mit neu erzeugten Doubles versuchst, die
Werte aus der Map zu bekommen, kann es zu Problemen kommen,
weil 1d + 0.00001d nicht zwangslaeufig 1.00001d ergibt.
Post by Stefan Schulze
Und wenn ja: Was ist denn das genaue Problem bei Doubles als Key und wie
wäre der schlauere Weg?
Das Problem ist die Darstellung von Fliesskommazahlen in
der Maschine, die Loesung ist die Verwendung eindeutiger
Schluessel.

Solange Du auf die Map aber nur per keySet().iterator()
zugreifst, sollte es keine Probleme geben.


Gruesse, Lothar
--
Lothar Kimmeringer E-Mail: ***@kimmeringer.de
PGP-encrypted mails preferred (Key-ID: 0x8BC3CD81)

Always remember: The answer is forty-two, there can only be wrong
questions!
Wanja Gayk
2003-10-25 20:16:10 UTC
Permalink
Stefan Schulze said...
Post by Stefan Schulze
Kollision beim Hashing ist doch, wenn mehrere Werte in die gleiche
"Zelle" der Hashtable geschrieben werden würden (je nach
Kollisionsbehandlung). Ausgelöst wird das doch üblicherweise durch
gleiche Hashwerte - was bei den HashMaps ja doch gleich dem eingegebenen
Key ist, oder?
Nein, eben nicht.
Eine Hasfunktion bildet grob gesagt, einen großen Zahlenraum auf einen
kleinen ab.
Nimm als Beispiel Telefonnummern als Key und Namen als Werte.
Ein Großteil der möglichen Telefonnummern ist schlicht nicht vergeben,
also lohnt es sich, statt einem Array von
1 0000 000000 0000000 Zahlen, in dem nur vieleleicht 0.7% mit
tatsächlichen Namen belegt sind, zu erzeugen, sondern man nimmt eien
Hashtable von vielleicht 5 000 000 000 Zahlen, in denen vielleicht 70%
belegt sind (die zahlen hinken, aber es geht um's Prinzip).
Das bedingt *natürlich* dass zwei unterschiedliche Nummern die gleiche
Zelle belegen wollen und hier haben wir eine Kollision.

Also was macht man?
Bei einer Kollsion (sprich: zelle ist schon belegt) holt man sich eie
Freie Zelle über einen zweiten key, der anders erzeugt ist (double
hashing), oder geht inkrementell durch die Hastable durch um eine freie
Zelle zu finden. Oder man behandelt kollisionen, indem man in jeder
Zelle eine Liste von Werten hat, statt statt eines einzelnen.

Was passiert also in meinem Telefonbuchbeispiel bei einer Kollision?

Unter einer Telefonnummer findet man in einer Zelle der Hastable zwei
Namen. Das ist natürlich uneindeutig. Da man aber mit Kollisionen
rechnen muss, packt man in eine Hashtable sinnvollerweise als Wert nicht
nur den Namen, sondern das Paar <Nummer,Name> rein. Man vergleicht nun
die Nummer des ersten gefunden Namens mit der gesuchten Nummer und wenn
das nicht passt, nimmt man den nächsten namen in der Liste (da sollte es
danpassen).
Analog geht es, beim Open-hashing (wo es keie Listen in denZTellen gibt,
sondern wo jeweils eine andere freie zelle bei einer Kollision gesucht
wird): findet unter der nummer einen Eintrag, aber die Nummer des
Eintrages passt nicht zur gesuchten Nummer, dann holt man über eine
alternative Hashfunktionm, bzw. inkrementell die möglichen alternativen
Positionen und schaut dort nach bis man es findet.

Gruss,
-Wanja-
--
Ich habe bemerkt, dass derzeit Spam mit meiner Yahoo-Adresse als
Absender durch die Gegend fliegt. Ich bin *nicht* Absender. Wer auch
immer diese Sauerei grade durchzieht, ich hoffe dass ihm möglichst bald
sein Schwanz abfault.
Paul Ebermann
2003-10-26 21:27:09 UTC
Permalink
Post by Wanja Gayk
Eine Hasfunktion bildet grob gesagt, einen großen Zahlenraum auf einen
kleinen ab.
Nimm als Beispiel Telefonnummern als Key und Namen als Werte.
Ein Großteil der möglichen Telefonnummern ist schlicht nicht vergeben,
also lohnt es sich, statt einem Array von
1 0000 000000 0000000 Zahlen, in dem nur vieleleicht 0.7% mit
tatsächlichen Namen belegt sind, zu erzeugen, sondern man nimmt eien
Hashtable von vielleicht 5 000 000 000 Zahlen, in denen vielleicht 70%
belegt sind (die zahlen hinken, aber es geht um's Prinzip).
Du hast ein Telefonbuch für die ganze Welt?
SCNR.
Post by Wanja Gayk
Das bedingt *natürlich* dass zwei unterschiedliche Nummern die gleiche
Zelle belegen wollen und hier haben wir eine Kollision.
Also was macht man?
Bei einer Kollsion (sprich: zelle ist schon belegt) holt man sich eie
Freie Zelle über einen zweiten key, der anders erzeugt ist (double
hashing), oder geht inkrementell durch die Hastable durch um eine freie
Zelle zu finden. Oder man behandelt kollisionen, indem man in jeder
Zelle eine Liste von Werten hat, statt statt eines einzelnen.
Was passiert also in meinem Telefonbuchbeispiel bei einer Kollision?
Unter einer Telefonnummer findet man in einer Zelle der Hastable zwei
Namen. Das ist natürlich uneindeutig. Da man aber mit Kollisionen
rechnen muss, packt man in eine Hashtable sinnvollerweise als Wert nicht
nur den Namen, sondern das Paar <Nummer,Name> rein. Man vergleicht nun
die Nummer des ersten gefunden Namens mit der gesuchten Nummer und wenn
das nicht passt, nimmt man den nächsten namen in der Liste (da sollte es
danpassen).
Analog geht es, beim Open-hashing (wo es keie Listen in denZTellen gibt,
sondern wo jeweils eine andere freie zelle bei einer Kollision gesucht
wird): findet unter der nummer einen Eintrag, aber die Nummer des
Eintrages passt nicht zur gesuchten Nummer, dann holt man über eine
alternative Hashfunktionm, bzw. inkrementell die möglichen alternativen
Positionen und schaut dort nach bis man es findet.
In java.util.HashMap (und genauso Hashtable) gibt
es übrigens Listen in den einzelnen Zellen.


Paul
Wanja Gayk
2003-10-27 01:55:46 UTC
Permalink
Paul Ebermann said...
Post by Paul Ebermann
Post by Wanja Gayk
Nimm als Beispiel Telefonnummern als Key und Namen als Werte.
Ein Großteil der möglichen Telefonnummern ist schlicht nicht vergeben,
also lohnt es sich, statt einem Array von
1 0000 000000 0000000 Zahlen, in dem nur vieleleicht 0.7% mit
tatsächlichen Namen belegt sind, zu erzeugen, sondern man nimmt eien
Hashtable von vielleicht 5 000 000 000 Zahlen, in denen vielleicht 70%
belegt sind (die zahlen hinken, aber es geht um's Prinzip).
Du hast ein Telefonbuch für die ganze Welt?
SCNR.
Klar, du nicht?
*grins*

[..]
Post by Paul Ebermann
In java.util.HashMap (und genauso Hashtable) gibt
es übrigens Listen in den einzelnen Zellen.
Ist das so? Ich dachte in der Hashmap würde stumpf ersetzt, im Gegensatz
zur Hashtable.

Gruss,
-Wanja-
--
Ich habe bemerkt, dass derzeit Spam mit meiner Yahoo-Adresse als
Absender durch die Gegend fliegt. Ich bin *nicht* Absender. Wer auch
immer diese Sauerei grade durchzieht, ich hoffe dass ihm möglichst bald
sein Schwanz abfault.
michael paap
2003-10-27 09:14:19 UTC
Permalink
Post by Wanja Gayk
Ist das so? Ich dachte in der Hashmap würde stumpf ersetzt, im Gegensatz
zur Hashtable.
Was meinst Du denn nun mit stumpfem Ersetzen?

"Stumpfes Ersetzen" darf bei Kollisionen nicht stattfinden, denn dabei
würden abhängig von der Hashfunktion und dem Füllungsgrad der Map für
den Benutzer völlig unvorhersehbar Informationen verloren gehen.

Oder meinst Du geschlossenes Hashing mit linearem Sondieren?

Gruß,
Michael
--
Sollte ausnahmsweise eine Mail-Antwort auf ein Posting vonnöten sein,
bitte folgende Adresse verwenden: newsreply@<Absender-Domain>.
Wanja Gayk
2003-10-27 12:48:01 UTC
Permalink
michael paap said...
Post by michael paap
Post by Wanja Gayk
Ist das so? Ich dachte in der Hashmap würde stumpf ersetzt, im Gegensatz
zur Hashtable.
Was meinst Du denn nun mit stumpfem Ersetzen?
ich meine den Ausschnitt aus dem Javadoc:

java.util.HashMap:
| public Object put(Object key, Object value)
| Associates the specified value with the specified key in this map. If
| the map previously contained a mapping for this key, the old value is
| replaced.

I Vergleich dazu kannte ich das vorher von der hashtable nicht:
java.util.HashTable:
| public Object put(Object key, Object value)
| Maps the specified key to the specified value in this hashtable.
| Neither the key nor the value can be null.

War wohl auf dem Holzweg, denn, wie du schon sagst: löschen bei
Kollision darf nicht passieren.

Gruss,
-Wanja-
--
Ich habe bemerkt, dass derzeit Spam mit meiner Yahoo-Adresse als
Absender durch die Gegend fliegt. Ich bin *nicht* Absender. Wer auch
immer diese Sauerei grade durchzieht, ich hoffe dass ihm möglichst bald
sein Schwanz abfault.
Paul Ebermann
2003-10-27 22:18:01 UTC
Permalink
Post by Wanja Gayk
michael paap said...
[ Liste bei Hash-Kollisionen ]
Post by Wanja Gayk
Post by michael paap
Post by Wanja Gayk
Ist das so? Ich dachte in der Hashmap würde stumpf ersetzt, im Gegensatz
zur Hashtable.
Was meinst Du denn nun mit stumpfem Ersetzen?
| public Object put(Object key, Object value)
| Associates the specified value with the specified key in this map. If
| the map previously contained a mapping for this key, the old value is
| replaced.
Wenn der gleiche _Schlüssel_ mehrfach verwendet wird,
wird natürlich das Objekt ersetzt.
Das ist aber etwas anderes, als wenn verschiedene
Schlüssel den gleichen Hashcode haben.
Achtung: Hashtable mit kleinem t.
Post by Wanja Gayk
| public Object put(Object key, Object value)
| Maps the specified key to the specified value in this hashtable.
| Neither the key nor the value can be null.
Naja, hier fehlt einfach etwas von der
Beschreibung. Dass ein Key immer höchstens einen
Wert hat, ist eine Eigenschaft jeder Map.


Paul

michael paap
2003-10-26 13:20:44 UTC
Permalink
Post by Stefan Schulze
Kollision beim Hashing ist doch, wenn mehrere Werte in die gleiche
"Zelle" der Hashtable geschrieben werden würden (je nach
Kollisionsbehandlung). Ausgelöst wird das doch üblicherweise durch
gleiche Hashwerte - was bei den HashMaps ja doch gleich dem eingegebenen
Key ist, oder?
Nein, eben nicht. Auch unterschiedliche Keys werden gleiche Hashwerte
ergeben, weil es mehr mögliche Keys als Plätze in der Map gibt. Durch
eine geeignete Strategie werden dann entweder mehrere Values als Liste
auf einen "Platz" gespeichert, oder es wird ein anderer Platz berechnet
(Rehashing).
Post by Stefan Schulze
Post by michael paap
Was Du meinst sind keine Kollisionen, sondern schlicht das
überschreiben eines alten Value durch einen neuen für den gleichen Key.
Was doch eben die "Kollisionsbehandlung" bei den HashMaps ist...
Das wäre fatal, s.o.

Gruß,
Michael
--
Sollte ausnahmsweise eine Mail-Antwort auf ein Posting vonnöten sein,
bitte folgende Adresse verwenden: newsreply@<Absender-Domain>.
Ortwin Glück
2003-10-26 11:32:38 UTC
Permalink
Post by Stefan Schulze
Ich füg hier Elemente in eine HashMap ein, doch dabei kommt es manchmal
dazu, dass der neue Wert einen alten einfach ersetzt.
Du kannst sicher sein, dass die HashMap implementierung fehlerfrei
arbeitet. Wo du fehler machen kannst ist bei den Object::equals und
Object::hashCode Methoden. Halte dich da einfach an die Tips aus
"Effective Java" (siehe amazon).

Odi
Lesen Sie weiter auf narkive:
Loading...