16 Bit Hashfunktion schnell und ohne Modulo?
-
Hi!
Ich benutze momentan als 16 Bit Integer Hashfunktion von 4 Byte-Worten eines Strings die Fowler/Noll FNV Hashfunktion, die ohne Modulo auskommt. Der Modulo macht als nämlich viel langsamer. MurmerHash funktioniert leider erst ab 32 Bit und mit Modulo. Weiß jemand vielleicht eine schnellere Hashfunktion ohne Modulo? Vielen Dank im voraus.
Gruß
kjesse
-
Hä??? Die Worte sind zusammenhanglos. Die beiden vorgeschlagenen Wege sind sich zu unähnlich.
Was ist Dein Begehr? Hashen für Hashtables, für Passwörter, zur Signierung oder zur Dateiidentifikation?
Und was haste für Einschränkungen? Eine CPU, die nur 16-bittig rechnen kann? Kann sie multiplizieren?
-
Ich suche eine schnelle Hashfunktion, die ohne eine Division durch eine Primzahl auskommt, weil die Division immer teuer ist. Ich habe als Input für die Hashfunktion einen String von 4 Characters. Der Hashwert soll eine Zahl zwischen 0 und 65535 sein. FNV macht das, ist mir aber nicht schnell genug.
-
Na von 32 auf 16 bit runter ist doch einfach. Erste Idee wäre: Interpretier die Zeichen als 2 16-bit-Werte und bilde das XOR. Wenn das zu viele Kollisionen erzeugt (bei ASCII-Zeichen nicht unwahrscheinlich) shiftest Du vorher halt noch ein bisschen hin und her.
Edit:
volkard schrieb:
Was ist Dein Begehr? Hashen für Hashtables, für Passwörter, zur Signierung oder zur Dateiidentifikation?
Die Frage hast Du übrigens noch nicht beantwortet. Je nachdem ist mein Vorschlag brauchbar oder nicht.
-
Da Du nicht mehr verrätst hier ein recht universeller Viertakter:
unsigned short hash(char data[4]){ return 2654435761**(int*)data; }
-
Ich baue einen Kompressor um Textdateien von > 1 GB (erstmal nur ASCII) effizient d.h. vor allem auch sehr schnell zu komprimieren und später zu dekomprimieren. Nach einem bestimmten Algorithmus. Ich gehe Byte für Byte durch und schreibe für ein Wort d.h. eine Sequenz von 4 Bytes meines ASCII-Strings den Offset in eine Tabelle von 65536 Einträgen (16 Bit). Vorher bilde ich aus dem Wort einen Hashvalue. Dafür benötige ich eine sehr schnelle Hashfunktion. Der Dekompressor arbeitet ganz ohne Hashtabelle.
-
Darf ich mal neugierig nachfragen, wie dein Kompressor funktioniert? Vielleicht hast du dich nur schlecht ausgedrückt, aber die paar Sachen die man erahnen kann klingen abenteuerlich.
-
Es ist nicht abenteuerlich. Alles funktioniert soweit. Ich kann eine 16 MB Datei in 175 ms auf 6 MB komprimieren und in 35 ms wieder dekomprimieren. Zum Speichern der Offset brauche ich eine Hashfunktion, die aus 4 Zeichen eine Zahl von 0...65536 erzeugt. In einer Hashtabelle mit diesem Index wird der Offset gespeichert und später abgefragt. Leider ist der Flaschenhals des Kompressors noch die Hashfunktion, was die Performance anbetrifft. FNV ohne Division war bei mir am schnellsten. Ich habe noch Bob Jenkins u. SuperFastHash ausprobiert. Die waren aber doppelt so langsam.
-
Du willst also 4 * ASCII (7-Bit) = 28 Bit eindeutig in 16 Bit wandeln und zurück?
-
DirkB schrieb:
Du willst also 4 * ASCII (7-Bit) = 28 Bit eindeutig in 16 Bit wandeln und zurück?
Möglich ist das schon, wenn man die Redundanzen von vielen solchen Quartetts benutzt. So wie das klingt hat er die häufigen Kombinationen (fest?) im Programm eingebaut.
-
Nein. Das muss nicht eindeutig sein, da verschiedene Wörter (ASCII a 4 Bytes) den gleichen Hashwert liefern können. Ich habe dann Doppelte im Kompressor, die zu Homonymen führen können. Mein Komprimat wird durch Kollisionen etwas schlechter. MurmurHash war noch etwas besser, aber er benutzt 32 Bit und ich muss durch eine Primzahl teilen. Dadurch nicht schnell genug.
