Original von deconceptional
Wenn ich nun also nach einem Key suche, muss ich ja Wissen, nach welchem Objekt ich suche, da der Key nicht eindeutig ist.

Ein Hashtable funktioniert eigentlich wie ein NSDictionary in Objective-C, oder ein Array in PHP.
Widmayer hat die Objekte wegrationalisiert und nur die Keys behandelt, also eigentlich sind bei den Zahlen (also den Keys!) noch Referenzen auf das eigentliche Objekt. Das heisst, dass wenn du den Key kennst, auch zum richtigen Objekt kommst.

Original von deconceptional
Ich folgere daraus, dass eine Hashtable ein Array ist, aus dem ich keine Objekte abrufen kann. Lieg ich da total falsch? Hab ich was uebersehen?

Ja.
Wäre ja sinnlos...

de.wikipedia.org/wiki/Hashtable#Kollisionen

Um deinen "Denkfehler" zu verdeutlichen:

Nehmen wir an, ein OObjekt hat den Hash 17. Jetzt kommt ein weiteres hinzu, welches ebenfalls 17 hat. Dieses wird an einer anderen Stelle, sagen wir mit dem Intervall 5, also bei 22 eingeordent. Noch schlimmer: 22 ist auch schon besetzt. Dann eben 27. Juuuuhuuu das ist frei.

Wenn ich jetzt nach dem Objekt suche, verfalle ich natürlich zunächst auf die 17. Ein vergleich zeigt mir jedoch: Neeeeeeee, das ist es nicht. Hmmm, Hash-Kollision? Also schauen wir mal bei 22. Das ist es aber auch nicht. Also 27. Jupp da ist es ja.

Das ist schon ein ziemlich schlechter Fall und dennoch reichen drei Vergleiche aus.

Ganz grundsätzlich: Eine Hashtable erspart einem das Suchen, weil man sofort (bzw. sehr schnell) weiß, wo sich ein Objekt befinden muss.

"müsste"

Den "Schlüssel". Der Hash-Value ist nicht eineindeutig und taugt daher nicht für die Identifizierung.
Deine Suchroutine bekommt ja einen Schlüssel übergeben, keinen Hash.

Beispiel: Wenn du in einem Dictionary das Objekt für einen Schlüssel suchst, dann liefert dir der Hash nur eine Prognose. Hast du mehrere gleiche Hashs, dann musst du halt noch den wirklichen Schlüssel vergleichen.

Also
Suche: «ZweitesObjekt»
-> Hash = 27;
Hole Objekt bei 27.
Ist es «ZweitesObjekt»
Nein
-> (Ersatz-)Hash = 29
Hole Objekt 29
Ist es «ZweitesObjekt»
Ja
Gefunden!
Hole gespeicherte Daten zum Schlüssel 29 (Nicht 27!)

Deine Frage ist nicht dumm. Du hast einfach ein Problem damit, dass ein Hash nicht eineindeutig ist. Dieses Problem zu haben ist zunächst einmal schlau.

Die einfachste Art sich eine Hashtable vorzustellen ist eine Bibliothek wo man den Titel erst Mal in einem Verzeichnis sucht. wo dann drinsteht in welchem Regal das Buch ist (Hashfunktion). Im einfachsten Fall ist das der Anfangsbuchstabe (wenn es 26 Regale gibt).

Dann geht man zum Regal und muss das Buch immer noch heraussuchen indem man alle Titel im Regal mit dem gewünschten vergleicht.

Der Unterschied bei den Hashtables im Computer zu einer gut geführten Bibliothek ist dass das Buch auch in den nächsten Regalen stehen kann. Und dass in jedem Regal nur ein Buch steht (es gibt aber auch eine Variante wo die Regale verkettete Listen sind - dann passen da beliebig viele rein).

Letztendlich sagt die Hashfunktion nur wo man mit dem Suchen sinnvollerweise beginnt (statt beim ersten Eintrag). Je genauer die Hashfunktion das vorhersagt, um so schneller findet man etwas.

Beim Einsortieren versucht man das Buch natürlich dort hinzustellen wo es die Hashfunktion empfiehlt. Oder wenn da kein Platz mehr ist halt ein Regal weiter (bzw. bei der verketteten Liste hängt man es in die Liste ein).

-- hns

Selbstverständlich wiird das gehashte Datum (hier Key) auch gespiechert. Du kannst ja nicht einfach Daten wegwerfen, weil du hashst. Ich glaube, da würde jemand ganz böse. Du kannmst den key auch nicht aus dem Hash rekonstruieren, weil er eben nicht eineindeutig ist.

Bei dem, was hns sagt, handelt es sich um einen Hash mit Containern. Jedem Eintrag in der Hashtabelle können mehrere Einträge der zu suchenden Datenmenge zugeordnet werden. Hier gehst du wie becshrieben zweischrittig vor:
1. Collection für einen Hash suchen.
2. Innerhalb der Collection suchen. (Wobei man hier wieder mit einem zweiten Wert hashen kann. Klassiker sind hier etwa Buchstaben: 1. Stufe = Anfangsbuchstabe, 2. Stufe = zweiter Buchstabe usw. Deutlich suboptimal aber ein anschauliches Beispiel.)

Bei meinem Beispiel handelt es sich um einen Hash, der nur einzelne Einträge verwaltet. Hier wird dann eben auf einen Ersatzhash ausgewichen. Das muss beim Suchen dann natürlich auch gemacht werden.