|
(Moderator)
Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
Delphi 2007 Enterprise
|
Re: Stack, Queue und Map
19. Jun 2006, 14:18
Nee, stimmt auch nicht.
Du nimmst einen Hash (egal ob MD5, CRC oder sonst was) und mappst den auf die aktuelle Hash-Tabellengröße runter.
TableIndex := Md5Hash(aString) Mod MyTableSize;
Dabei kommt es zwangsläufig zu Kollisionen, da ein sehr großer Zahlenraum, auf einen wesentlich kleineren Zahlenraum abgebildet werden. Wichtig für eine Hash-Funktion ist nur, das sie die zu erwartenden Strings gleichverteilt im Zahlenraum der Hashtabelle abbildet.
Um dies zu erreichen, benötigt mal also erstens eine gute Hashfunktion, und zweitens geeignete Tabellengrößen. Hier haben sich Primzahlen als sehr gut erwiesen.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
|