Ich arbeite an einer Hash-Tabelle in C-Sprache und teste die Hash-Funktion für Zeichenfolgen.
Die erste Funktion, die ich versucht habe, ist das Hinzufügen von ASCII-Code und die Verwendung von Modulo (% 100), aber ich habe beim ersten Datentest schlechte Ergebnisse erzielt: 40 Kollisionen für 130 Wörter.
Die endgültigen Eingabedaten enthalten 8 000 Wörter (es handelt sich um ein Wörterbuch, das in einer Datei gespeichert ist). Die Hash-Tabelle wird als int-Tabelle [10000] deklariert und enthält die Position des Wortes in einer txt-Datei.
Die erste Frage ist, welcher der beste Algorithmus für Hashing-Strings ist. und wie man die Größe der Hash-Tabelle bestimmt?
Danke im Voraus !
:-)
Antworten:
Ich habe gute Ergebnisse mit
djb2
Dan Bernstein erzielt .quelle
size_t
oder einen anderen vorzeichenlosen Wert zurückgeben (z. B. den vorzeichenlosen Long in diesem Code). Der Aufrufer ist dafür verantwortlich, das Ergebnis modulo zu nehmen, um es an die Hash-Tabelle anzupassen. Der Anrufer steuert den Tabellen-Slot, in den gehasht wird. nicht die Funktion. Es wird nur eine vorzeichenlose Nummer zurückgegeben.Erstens, Sie in der Regel nicht nicht wollen einen verschlüsselten Hash für eine Hash - Tabelle verwenden. Ein Algorithmus, der nach kryptografischen Standards sehr schnell ist, ist nach Hash-Tabellen-Standards immer noch unerträglich langsam.
Zweitens möchten Sie sicherstellen, dass jedes Bit der Eingabe das Ergebnis beeinflussen kann / wird. Eine einfache Möglichkeit, dies zu tun, besteht darin, das aktuelle Ergebnis um eine bestimmte Anzahl von Bits zu drehen und dann den aktuellen Hash-Code mit dem aktuellen Byte zu XOR. Wiederholen Sie diesen Vorgang, bis Sie das Ende der Zeichenfolge erreicht haben. Beachten Sie, dass die Rotation im Allgemeinen auch kein gerades Vielfaches der Bytegröße sein soll.
Unter der Annahme des allgemeinen Falls von 8-Bit-Bytes können Sie beispielsweise um 5 Bit drehen:
Bearbeiten: Beachten Sie auch, dass 10000 Slots selten eine gute Wahl für eine Hash-Tabellengröße sind. Normalerweise möchten Sie eines von zwei Dingen: Sie möchten entweder eine Primzahl als Größe (erforderlich, um die Richtigkeit bei einigen Arten der Hash-Auflösung sicherzustellen) oder eine Potenz von 2 (so kann das Reduzieren des Werts auf den richtigen Bereich mit einer einfachen Methode erfolgen Bitmaske).
quelle
Wikipedia zeigt eine nette String-Hash-Funktion namens Jenkins One At A Time Hash. Es werden auch verbesserte Versionen dieses Hashs zitiert.
quelle
Es gibt eine Reihe vorhandener Hashtabellenimplementierungen für C, von der C-Standardbibliothek hcreate / hdestroy / hsearch bis zu denen in APR und glib , die auch vorgefertigte Hash-Funktionen bereitstellen. Ich würde dringend empfehlen, diese zu verwenden, anstatt Ihre eigene Hashtabelle oder Hash-Funktion zu erfinden. Sie wurden stark für gängige Anwendungsfälle optimiert.
Wenn Ihr Datensatz jedoch statisch ist, besteht Ihre beste Lösung wahrscheinlich darin, einen perfekten Hash zu verwenden . gperf generiert für Sie einen perfekten Hash für einen bestimmten Datensatz.
quelle
djb2 hat 317 Kollisionen für dieses 466k englische Wörterbuch, während MurmurHash keine für 64-Bit-Hashes und 21 für 32-Bit-Hashes hat (ungefähr 25 sind für 466k zufällige 32-Bit-Hashes zu erwarten). Meine Empfehlung ist die Verwendung von MurmurHash, falls verfügbar, es ist sehr schnell, da es mehrere Bytes gleichzeitig benötigt. Wenn Sie jedoch eine einfache und kurze Hash-Funktion zum Kopieren und Einfügen in Ihr Projekt benötigen, würde ich empfehlen, jeweils eine Byte-Version von Murmeln zu verwenden:
Die optimale Größe einer Hash-Tabelle ist - kurz gesagt - so groß wie möglich und passt dennoch in den Speicher. Da wir normalerweise nicht wissen oder nachschlagen möchten, wie viel Speicher uns zur Verfügung steht und sich möglicherweise sogar ändert, beträgt die optimale Größe der Hash-Tabelle ungefähr das Zweifache der erwarteten Anzahl von Elementen, die in der Tabelle gespeichert werden sollen. Wenn Sie viel mehr zuweisen, wird Ihre Hash-Tabelle schneller, aber bei schnell sinkenden Renditen wird Ihre Hash-Tabelle exponentiell langsamer, wenn Sie sie kleiner machen. Dies liegt daran, dass es für Hash-Tabellen einen nichtlinearen Kompromiss zwischen räumlicher und zeitlicher Komplexität gibt , mit einem optimalen Auslastungsfaktor von 2 sqrt (2) = 0,58 ... anscheinend.
quelle
Erstens, sind 40 Kollisionen für 130 Wörter, die auf 0..99 gehasht wurden, schlecht? Sie können kein perfektes Hashing erwarten, wenn Sie nicht speziell dafür vorgehen. Eine gewöhnliche Hash-Funktion hat die meiste Zeit nicht weniger Kollisionen als ein Zufallsgenerator.
Eine Hash-Funktion mit einem guten Ruf ist MurmurHash3 .
In Bezug auf die Größe der Hash-Tabelle hängt es wirklich davon ab, welche Art von Hash-Tabelle Sie im Sinn haben, insbesondere, ob die Buckets erweiterbar oder ein Slot sind. Wenn Buckets erweiterbar sind, haben Sie wieder die Wahl: Sie wählen die durchschnittliche Bucket-Länge für die Speicher- / Geschwindigkeitsbeschränkungen, die Sie haben.
quelle
n - m * (1 - ((m-1)/m)^n) = 57.075...
. 40 Kollisionen sind besser als zufällig zu erwarten (46 bis 70 bei einem p-Score von 0,999). Die fragliche Hash-Funktion ist einheitlicher als wenn sie zufällig wäre oder wir ein sehr seltenes Ereignis erleben.Obwohl es mit ziemlicher Sicherheit besser ist
djb2
, wie von cnicutar auf stackoverflow vorgestellt , lohnt es sich auch, die K & R- Hashes zu zeigen:1) Anscheinend ein schrecklicher Hash-Algorithmus, wie in K & R 1st Edition ( Quelle ) vorgestellt.
2) Wahrscheinlich ein ziemlich anständiger Hash-Algorithmus, wie er in K & R Version 2 vorgestellt wird (von mir auf S. 144 des Buches verifiziert); NB: Stellen Sie sicher, dass Sie diese
% HASHSIZE
aus der return-Anweisung entfernen, wenn Sie vorhaben, den Modul außerhalb des Hash-Algorithmus auf Ihre Array-Länge zu dimensionieren. Außerdem empfehle ich Ihnen,unsigned long
anstelle des einfachenunsigned
(int) den Typ return und "hashval" vorzunehmen .Beachten Sie, dass aus den beiden Algorithmen hervorgeht, dass ein Grund dafür, dass der Hash der 1. Ausgabe so schrecklich ist, darin besteht , dass die Reihenfolge der Zeichenfolgen NICHT berücksichtigt wird und
hash("ab")
daher der gleiche Wert wie zurückgegeben wirdhash("ba")
. Dies ist jedoch beim Hash der 2. Ausgabe nicht der Fall, der (viel besser!) Zwei verschiedene Werte für diese Zeichenfolgen zurückgeben würde.Die für
unordered_map
(eine Hash-Tabellenvorlage) undunordered_set
(eine Hash-Set-Vorlage) verwendeten GCC C ++ 11-Hashing-Funktionen scheinen wie folgt zu sein.Code:
quelle
Ich habe diese Hash-Funktionen ausprobiert und das folgende Ergebnis erhalten. Ich habe ungefähr 960 ^ 3 Einträge, jeder 64 Bytes lang, 64 Zeichen in unterschiedlicher Reihenfolge, Hashwert 32bit. Codes von hier .
Eine seltsame Sache ist, dass fast alle Hash-Funktionen eine Kollisionsrate von 6% für meine Daten haben.
quelle
Eine Sache, die ich mit guten Ergebnissen verwendet habe, ist die folgende (ich weiß nicht, ob sie bereits erwähnt wurde, weil ich mich nicht an ihren Namen erinnern kann).
Sie berechnen eine Tabelle T mit einer Zufallszahl für jedes Zeichen im Alphabet Ihres Schlüssels [0,255] vor. Sie haben Ihren Schlüssel 'k0 k1 k2 ... kN' gehasht, indem Sie T [k0] x oder T [k1] x oder ... x oder T [kN] nehmen. Sie können leicht zeigen, dass dies so zufällig ist wie Ihr Zufallszahlengenerator und rechnerisch sehr machbar. Wenn Sie wirklich auf eine sehr schlechte Instanz mit vielen Kollisionen stoßen, können Sie das Ganze einfach mit einem neuen Stapel von Zufallszahlen wiederholen.
quelle