Frage zu Hashmaps
-
Hallo zusammen
Ich habe eine kurze Frage in Bezug auf eine Hashmaps. In meinen Unterlagen steht, dass man gelöschte Elemente innerhalb der Hasmap mit einem AVAILABLE Objekt füllen muss. Meine Frage ist nun: warum ist dieser Schritt nötig? Wieso kann ich das entsprechende Element nicht einfach löschen und gut ist?Beim linear Probing wird ja so lange sequentiell gesucht, bis entweder null oder AVAILABLE oder das ensprechende Objekt mit dem passenden Schlüssel gefunden wurde. Aber eben, wieso ist das mit diesem AVAILABLE Objekt nun nötig?
-
was denn für unterlagen???
zeichenunterlagen?
-
Ein AVAILABLE Objekt sagt mir gar nichts. Wichtig beim löschen aus Hashmaps ist, dass du die gelöschte Stelle im Hash als frei markierst - z.B. mit null. Würdest du das nicht machen, könntest du nicht feststellen ob ein Schlüssel im Hash einen Wert hat oder nicht.
-
Ishildur schrieb:
Beim linear Probing wird ja so lange sequentiell gesucht, bis entweder null oder AVAILABLE oder das ensprechende Objekt mit dem passenden Schlüssel gefunden wurde. Aber eben, wieso ist das mit diesem AVAILABLE Objekt nun nötig?
Das Problem ist die Objektsuche.
Nehmen wir an, du hast mal für ein Objekt eine ungünstige rehash folge von 4 rehashes.
Wenn nun das Objekt am rehash platz 2 gelöscht werden würde und das Objekt auf "leer" gesetzt wird, passiert folgendes bei der Objektsuche:
Der algo rehasht , und beim zweiten rehash findet er ein leeres feld->Objekt nicht in der hashmap.
gibt es nun ein "gelöscht" oder "available" feld, dann wüsste der algo: "an der stelle war schonmal ein Objekt, weiteres rehashen könnte sich lohnen", und findet das Objekt dann nach dem 4. rehash.
Sicherlich könnte man auch grundsätzlich die rehash folge immer komplett durchlaufen lassen, bis klar ist, dass das Element nicht in der map ist. Dann würde das testen, ob ein Objekt vorhanden ist im zweifelsfall aber enorm teuer werden.
-
@otze
Jetzt wo du es sagst, leuchtet es mir ein! Danke vielmals!
Ich erinnere mich nun auch, dass unser Professor genau diese Problematik erklärt hatte. Ich habs wohl einfach vergessen!
-
Nach meiner Erfahrung ist Chaining fast immer schneller auch wenn man resizen muss. Da hat man das Problem einfach nicht.
-
Ponto schrieb:
Nach meiner Erfahrung ist Chaining fast immer schneller auch wenn man resizen muss. Da hat man das Problem einfach nicht.
Ein Stichwort: Locality of reference. Das kann ganz enorme Probleme mit sich bringen.
Übrigens verwechselst Du was: Die Größe ändern muss man in erster Linie dann, wenn man *kein* Chaining verwendet, weil sonst das Array irgendwann voll ist.
-
Wenn man Geschwindigkeit haben will, dann muss man auch bei Chaining Resizing betreiben.
-
Ponto schrieb:
Wenn man Geschwindigkeit haben will, dann muss man auch bei Chaining Resizing betreiben.
Daher schrieb ich „in erster Linie“. Trotzdem würde ich Double Hashing nicht so schnell abtun.
/EDIT: Das gilt allerdings nur, solange man die Lösch-Operation nicht braucht.