HashMap Fragen

[Otz]

Hallo zusammen,

ich verwende gerade eine HashMap und dabei sind mir einige Punkte unklar.

1.
Beim einfügen wird ja die Speicherstelle anhand der hashfunktion festgelegt. muss ich diese Hashfunktion von Hand definieren oder gibt es eine default Hashfunktion die man dabei verwenden kann.

2.
Wie ist die Laufzeit beim Lesen von bereits eingefügten Werten einer HashMap?

3.
Kann es sein, dass unterschiedliche Keys auf die selbe Speicherstelle verweisen und somit Kollisionen entstehen? Wie kann dies vermieden werden?


vielen dank

 

[rme]

Hallo,

zu 1: Ja, es gibt eine Default-Hashfunktion. Sie nimmt die Adresse des Objekts im virtuellen Speicher als Hash-Wert. Das führt zu unschönen Effekten, wenn man nicht nur Identität, sondern auch Gleichheit abbilden möchte - dann muss es man es selbst machen.

zu 2: Die ist durchschnittlich konstant, weil die aufwändigeren Operationen beim Einfügen gemacht werden. Es kann allerdings selten mal Fälle geben, in denen auch das Finden eines Wertes O(n) benötigt, nämlich wenn es viele Kollisionen gab. Bei einer TreeMap wäre es im schlimmsten Fall O(log n) - dafür ist das Einfügen aber auch entsprechend langsamer. Man muss also sehr genau vorher wissen, was mit der HashMap im Laufe ihres Lebens passiert, um die beste Implementierung zu wählen.

zu 3: Ja, die Kollisionen werden aber durch Sondierung von der Java-Implementierung behandelt - je nach Art der HashMap in einem Baum, einer linearen Liste oder einem Array. Ganz verhindern kannst du es nur, indem du die hashCode-Methode überschreibst und so an deine Klasse anpasst, dass nur bei Gleichheit bzw. Identität der gleiche Hash-Wert entsteht.

Edit: Noch ein paar Dinge ergänzt.

 

[stg]

Kleine Korrektur: Kollisionen lassen sich nicht komplett vermeiden. Das ist Natur von HashFunktionen, dagegen kannst du nichts machen. Das liegt ganz einfach daran, dass du (praktisch) unbegenzt verschiedene Objekte auf einen relativ kleinen Satz von Schlüsseln (den Wertebereich von von

int

) abbildest.
Du musst bei der Implementierung von deinen HashFunktionen in erster Linie darauf achten, dass die häufig auftretenden Möglichkeiten gut über den gesamten Wertebereich von Integer verteilt sind. Damit kommt es in der Praxis selten zu Kollisionen, verhindern kannst du sie aber niemals komplett. (Es sei denn es sind weniger als 2^32 verschiedene Ausprägungen möglich, aber dann ist die Frage sowieso recht sinnfei)

 

[rme]

Kleine Korrektur: Es gibt heutzutage moderne Verfahren, in denen es keine Kollisionen gibt - perfektes Hashing kombiniert mit Geburtstags-Hashing. Da sind bei amortisierter Analyse alle Operationen in O(1). Das Verfahren ist aber so modern, dass es in Java noch nicht Einzug gehalten hat. Allerdings ist die Implementierung gar nicht so schwer: Kuckucks-Hashing ? Wikipedia

(Kurzfassung: Man nimmt einfach mehrere Hash-Tabellen - wenn es in Tabelle i schon vorhanden ist, speichert man es in Tabelle i +1 usw.)

 

[stg]

Man kann das natürlich immer weiter austüfteln und verbessern, aber grundsätzlich kann man niemals vollständig Kollisionsfrei hashen. Wenn ich doppelt so viele Leute in einen Zug stecke, wie es Sitzplätze gibt, dann müssen zwangsläufig welche stehen oder auf dem Schoß von Mitreisenden sitzen
Ich spreche da allerdings natürlich von der Theorie. Praktisch kann man vermutlich auf aktuellen Maschinen gar nicht so viele verschiedene Objekte erzeugen, wie es solcherlei verschiedene "Sitzplätze" gibt. Dann ist die Idee vom Kuckucks-Hashing, sofern ich den Artikeln grad richtig aufgefasst habe, einfach eine andere Hashfunktion zu wählen, bis es passt, natürlich klever.

 

[rme]

Langsam wird's Off-Topic, aber gut Wenn wir in der Theorie von einer Turing-Maschine ausgehen, könnten wir mit einer 2-Band-Maschine kollisionsfrei bleiben - es wird nämlich nur eine neue Hash-Funktion gewählt, sondern auch eine zweite Tabelle. Wenn in der ersten Tabelle beim Einfügen eine Kollision auftritt, wird in der 2. mit einer anderen Hash-Funktion geschaut. Wenn es dort auch eine Kollision gibt, wird die ganze Tabelle mit einer anderen Hash-Funktion neu erzeugt - und das so lange, bis es passt. Das Geburtstags-Paradoxon liefert die nötige Schranke dafür, dass das nicht sehr oft passieren muss. Wenn es keine freien Plätze mehr gibt, wird die Größe der Tabelle verdoppelt. Das klingt natürlich recht langsam - aber es passiert so selten, dass man es mittels amortisierter Analyse in O(1) machen kann.

Da die Bänder der Turing-Maschine unbegrenzt sind, gibt es auch kein Platzproblem oder ein Verlassen des int-Wertebereichts. Also ist es eigentlich eher so, dass das Verfahren in der Theorie perfekt ist, aber in der Praxis durch die Größe int² beschränkt ist.

 

[Ruzmanz]

Du widersprichst dir selbst, denn die Funktionsweise der Hashfunktion erklärst du richtig. Eine Kollision tritt dann auf, wenn du zwei unterschiedliche "Objekte" unter einem Wert ablegen willst. Und wenn diese Kollision aufgetreten ist, kannst du deinen Wertebereich vergrößern, eine zweite Hashfunktion wählen, usw.

Eine Hash-Funktion bildet per Definition eine größere Menge auf einer kleineren ab. Somit folgt, dass bei einer unendlichen Eingabemenge diese nicht kollisionsfrei abgelegt werden kann. Die große des Speichers spielt dabei keine Rolle. In der Praxis wird er dennoch als Orientierung genutzt, um nicht den kompletten RAM für 10 Objekte belegen zu müssen ...

 

[rme]

Gut, dann eben präziser: Kollisionen lassen sich nicht vermeiden, aber die Notwendigkeit einer Sondierung in Datenstrukturen, die beim Suchen nach Werten für eine Verlangsamung sorgen, lässt sich vermeiden.

Ich bezog mich auf Kollisonen innerhalb der Datenstruktur HashMap, nicht der Hash-Funktion selbst. Also das Vorhandensein von doppelten Hash-Werten innerhalb der Struktur. Und das lässt sich wie oben beschrieben vermeiden.

 

[nvidia]

[...] Das Verfahren ist aber so modern, dass es in Java noch nicht Einzug gehalten hat. Allerdings ist die Implementierung gar nicht so schwer: Kuckucks-Hashing ? Wikipedia

Es mag zwar modern sein, jedoch durch die heutige, mehrstufige Speicherarchitektur bedingt, in der Praxis öfter mal langsamer als lineares hashing. Die Artikel dazu kann jeder selbst googlen.

@OT
Allgemein sollte man nicht vergessen das O(x) die obere Grenze ist, es gibt aber noch Omega (untere Beschränkung) und Theta (mittlere Beschränkung) die gerne mal weggelassen werden, für eine objektive Beurteilung aber auch nötig wären. Diese Grenzen sind aber oft wesentlich komplizierter aufzustellen genauso wie die Faktoren. Es ist zwar nett das oft ein O(x) vorgefunden wird, in der Realität aber ein k*O(x) ist und k recht stark variieren kann. Ein Beispiel dafür wäre Heapsort vs. Quicksort, beides n*(log n) wird Heapsort jedoch recht naiv implementiert läuft es langsamer als QS, aber immernoch im Bereich n*(log n).[1]

[1] Auf die Schnelle gesucht, Heapsort, Quicksort, and Entropy