Hashing Speicherverfahren

[cracker0dks]

Hi
bei manchen Java Collections werden mit dem Hashingverfahren Daten abgelegt.
Ich hab jetzt mal versucht es zu verstehen... aber komm mit dem Sinn des ganzen nicht klar.

Also ich hab doch einen Hash-Table, dort stehen meine Hash des gespeicherten Objekts und die Zieladresse (also quasy ein Zeiger auf den Speicherplatz des Objekts)

Das Objekt selber liegt irgendwo im speicher.

Jetzt ist doch der einzige Vorteil, dass ich beim sequenziellen durchlauf meiner HashTabell nicht so lange brauche...

Doch da ich das gesuchte Objekt erst durch die Hash-funktion schleusen muss und dann noch zur speicheradresse springen muss, kommt doch das mindestens auf den gleichen aufwand raus ?

Bitte berichtigen... fals ich was falsch verstanden habe.

Danke

[Christian Marquardt]

Jetzt ist doch der einzige Vorteil, dass ich beim sequenziellen durchlauf meiner HashTabell nicht so lange brauche...

Das eben passiert nicht

http://de.wikipedia.org/wiki/Hashtabelle

[cracker0dks]

Also errechne ich anhand des Gesuchten objekts und der Hash-funktion die Speicheradresse...

aber (Wikipediazitat)

Zum Berechnen dieses Hashwertes wird ein Schlüssel benötigt, der dieses Objekt eindeutig identifiziert

Der Hashwert selber ist doch der Schlüssel, der ein Objekt eindeutig identifiziert.
(nicht 100% eindeutig, aber das ist ein anderes Prob)

Für was unterscheiden die zwischen Schlüssel und Hash wenns doch eigendlich das gleiche ist? ( und wie sieht dieser Schlüssel aus?)

Danke

[Christian Marquardt]

Ich finde die Erklärung bei Wiki ganz anschaulich, und weiss nicht so recht, wie man es besser erklären kann.

Um etwas in einem Hash zu speichern wird ein Algorithmus genutzt, der den Speicherort berechnet. Um so einen Speicherort bestimmten zu können, muss dann das Objekt, welches gespeichert werden soll, irgendein "Alleinstellungsmerkmal" (Schlüssel) mitbringen, damit der Ort berechnet werden kann.
Nehmen wir an, wir wollten einstellige Ziffern ablegen. Wir könnten nun den Ziffernwert als Schlüssel nehmen. Der Speicherplatz wird berechnet mit der Formel Ziffernwert *2

D.h. Ziffer 1 wird an Speicherplatz 2 abgelegt, Ziffer 2 an Platz 4 usw.

Der Hashwert ist dann hier 2 und 4.

[cracker0dks]

JA... also

A: Der Schlüssel ist das Objekt, ein Teil des objektes oder auch das Objekt koprimiert bzw anderst verwurstelt.

B: Ist doch total Sinnfrei das Ergebnis (wie in deinem bsp) noch mal 2 zu nehem oder sonst irgend ein Quatsch mit zu machen. Wenn ich mit allen Ergebnissen (aus A) das selbe mache hab ich doch garnix mit erreicht!

Ich könnte auch einfach in deinem Bsp als Hashwert 1 und 2 nehmen und im Speicher auch 1 und 2 stehen haben.!

Die Frage ist: Warum muss ich den Schlüssel (aus A) noch einmal durch einmal durch eine Hashfunktion schicken, wenn er das Objekt doch schon eindeutig identifiziert?

[Christian Marquardt]

B: Ist doch total Sinnfrei das Ergebnis (wie in deinem bsp) noch mal 2 zu nehem oder sonst irgend ein Quatsch mit zu machen. Wenn ich mit allen Ergebnissen (aus A) das selbe mache hab ich doch garnix mit erreicht!

Das mit der Multiplikation war ein Beispiel! Und anscheinend hast du einen wichtigen Satz überlesen: Das Objekt muss erstmal ein Alleinstellungsmerkmal haben. Du kannst in einer Hashmap nicht zweimal den String "Hallo" als Schlüssel ablegen.

Die Frage ist: Warum muss ich den Schlüssel (aus A) noch einmal durch einmal durch eine Hashfunktion schicken, wenn er das Objekt doch schon eindeutig identifiziert?

Damit du die Position findest, wo du es ablegen kannst. Es geht nicht um die Identifizierung, sondern um die Ablage

[cracker0dks]

Das mit der Multiplikation war ein Beispiel! Und anscheinend hast du einen wichtigen Satz überlesen: Das Objekt muss erstmal ein Alleinstellungsmerkmal haben. Du kannst in einer Hashmap nicht zweimal den String "Hallo" als Schlüssel ablegen.

Ja gut das Problem besteht so oder so bei der ablage 2 gleicher Objekte oder auch einfach so durch Zufall!

Damit du die Position findest, wo du es ablegen kannst. Es geht nicht um die Identifizierung, sondern um die Ablage

Ok wenn die Hashfunktion dann eine Adresse ausspuckt wo das Objekt hingespeichert werden soll, ist das ne Erklärung!

[Christian Marquardt]

Ja gut das Problem besteht so oder so bei der ablage 2 gleicher Objekte oder auch einfach so durch Zufall?

Eine Hashmap nimmt keine zwei gleichen Objekte an. Es gibt Implementationen eines Hash, der gleiche Objekt annimmt und diese auch ablegt. Üblichweise bekommt man dann auch wieder zwei zurück, wenn man sie ausliest.

Es kann aber das Problem entstehen das zwei verschiedene Objekte durch die Berechnung den gleichen Hashwert bekommen -> steht bei Wikipedia -> Kollision

[cracker0dks]

Ok danke glaub habs im prinzip jetzt gerafft... Danke