Vorteil von auf Primzahlen skalierten Hashmaps?

[xZise]

Vermutlich was von beiden Das letzte and muss ja sein, damit man nur die untersten 10 bit verwendet.

Aber bei den Restlichen bin ich mir unsicher ob es xor tut.

MfG
Fabian

[Namenloser]

Zitat von xZise:

Vermutlich was von beiden Das letzte and muss ja sein, damit man nur die untersten 10 bit verwendet.

Das letzte and muss natürlich bleiben

Zitat von xZise:

Aber bei den Restlichen bin ich mir unsicher ob es xor tut.

Am sichersten ist es wahrschenlich, auf solche Spielchen ganz zu verzichten, und davon auszugehen, dass der Hash die Bits gut durchgeschüttelt hat.

[alzaimar]

Hi
Essentiell ist natürlich die Hash-Funktion. Wieso ich Primzahlen als Hashgröße verwende, liegt mit ziemlicher Sicherheit daran, as ich zunächst mit Integer-Hashmaps gearbeitet habe. Ich meine mich zu erinnern, dann auch bei Strings eine Verbesserung ggü einer willkürlichen Verdopplung gemessen habe. Das ist aber mittlerweile so lange her, das ich es nicht mehr genau weiss.

Probiers doch einfach aus.

[idefix2]

Zitat:

Würde nicht xor mehr Sinn ergeben?

Entschuldige, natürlich habe ich xor gemeint. Bis auf ganz hinten, das letzte and muss bleiben, wie Du richtig geschrieben hast.

Zitat:

Am sichersten ist es wahrschenlich, auf solche Spielchen ganz zu verzichten

Am sichersten ist es, irgend so etwas zu machen, weil damit die niederwertigen Bits von allen Buchstaben des Strings zum Tragen kommen, oder doch mit einer ungeraden Feldgrösse und modulo-Arithmetik zu operieren. Aber notwendig ist es wahrscheinlich nicht.

Die Hashfunktion von Alzaimar rotiert die Zeichen bei jedem Buchstaben 4-Bit-weise nach links, dadurch bleiben, je nach grösse des Hashfeldes, die Hälfte oder mehr der Buchstaben völlig unberücksichtigt, wenn Du einfach nur die höherwertigen Bits "weg-and-est". Das muss nicht unbedingt schaden, aber mit einem xor über alle vier Bytes des Resultats bist Du ebenso auf der sicheren Seite wie mit einem Feld mit ungerader Grösse und Modulo-Arithmetik, wobei die zweite Variante wahrscheinlich geringfügig langsamer sein wird.

[Namenloser]

So

dank euch habe ich's jetzt geschafft, meine Hashmap zu implementieren. Erst mal habe ich nur die Basisklasse und zum Testen ein normales String-zu-String-Dictionary erstellt. Die von mir eigentlich benötigte Widestring-Objekt-Variante ist noch nicht dabei, sollte sich aber nun recht einfach implementieren lassen.

Ich habe die Hashmap mitsamt Test-Dateien mal angehängt. Nicht wundern, dass im kompilierten Test-Projekt noch ein paar andere Tests angezeigt werden - diese stammen aus meinem Hauptprojekt, wofür ich die Hashmap eigentlich brauche. Ihr könnt sie also einfach ignorieren.

Würde mich über Feedback freuen!

PS: Hat jemand einen Tipp für eine gute WideString-Hashfunktion? Kann/sollte ich dafür die ELF-Hashfunktion weiterbenutzen, oder muss ich die irgendwie anpassen?

[himitsu]

Was soll denn der Hast so für Spezifikationen?

in meinem himXML steckt ein kleiner mutierter WideString-ELF-Hash (ich glaub das war mal einer ... hatte mir dafür mal eine AnsiHash-Funktion angepaßt, welche ich beim Hagen fand)

siehe (am Ende der himXML.pas)
Class Function TXHelper.CalcHash(Const S: TWideString): LongWord; allerdings hat diese ein paar spezielle Erweiterungen/Anpassungen, aber das läßt sich ja ändern
- einige bestimmte Steuerzeichen (*?\) schalten das Hashen ab
- es kann ein CaseInsensitiver Hash erstellt werden

PS: http://www.delphipraxis.net/137894-e...nicode-ok.html

[Namenloser]

Danke, ich werd's mir mal anschauen.