Schneller String-Hashing-Algorithmus mit geringen Kollisionsraten mit 32-Bit-Integer [geschlossen]
https://stackoverflow.com/questions/114085
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe viele unabhängige benannte Dinge, die ich gegen eine schnelle Suche tun möchten. Ein „Erdferkel“ ist immer ein „Erdferkel“ überall, so die Zeichenfolge Hashing und die ganze Zahl Wiederverwendung gut Vergleiche zu beschleunigen funktionieren würde. Die ganze Reihe von Namen ist nicht bekannt (und Änderungen im Laufe der Zeit). Was ist eine schnelle String Hashing-Algorithmus, der kleine generiert (32 oder 16) Bit-Werte und haben einen niedrigen Kollisionsrate?
Ich möchte eine optimierte Implementierung spezifisch für C / C ++ sehen.
Lösung
Einer der FNV Varianten Ihre Anforderungen entsprechen sollte. Sie sind schnell und produzieren ziemlich gleichmäßig verteilt Ausgänge.
Andere Tipps
Murmur Hash ist sehr schön.
Für eine feste String-Set Verwendung gperf.
Wenn Ihre String-Set Änderungen haben Sie eine Hash-Funktion wählen. Das Thema wird diskutiert vor:
Was ist der beste Hashing-Algorithmus auf einem stl Zeichenfolge zu verwenden, wenn hash_map mit?
Es gibt auch einen rel="noreferrer"> unter eternallyconfuzzled.com .
Jenkins' One-at-a-Time-Hash für Strings sollte wie folgt aussehen:
#include <stdint.h>
uint32_t hash_string(const char * s)
{
uint32_t hash = 0;
for(; *s; ++s)
{
hash += *s;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Eine andere Lösung, die noch besser je nach Anwendungsfall werden könnte, ist internierten Strings . Dies ist, wie Symbole arbeiten z.B. in Lisp.
Ein internierten String ist ein String-Objekt, dessen Wert die Adresse des aktuellen String-Bytes. So erstellen Sie eine interniert String-Objekt, indem sie in einer globalen Tabelle Überprüfung: wenn die Zeichenfolge in es ist, initialisieren Sie die internierten String an die Adresse dieser Zeichenfolge. Wenn nicht, Sie legen Sie sie, und dann interniert String initialisieren.
Das bedeutet, dass zwei internierten Strings aus dem gleichen String aufgebaut werden den gleichen Wert haben, die eine Adresse ist. Also, wenn N die Anzahl der internierten Strings in Ihrem System ist, sind die Merkmale:
- Langsam Konstruktion (benötigt Lookup und möglicherweise Speicherzuweisung)
- Benötigt globale Daten und die Synchronisation im Fall von gleichzeitigen Threads
- Vergleichen ist O (1), da Sie Adressen sind zu vergleichen, nicht unbedingt die String-Bytes (dies bedeutet, funktioniert gut, aber es wird nicht eine alphabetische Sortierung Sortierung).
Cheers,
Carl
Warum gehst du nicht einfach benutzen Boost-Bibliotheken ? die Hash-Funktion ist einfach zu bedienen und die meisten Sachen in-Boost wird bald Teil des C ++ Standard sein. Einige davon ohnehin schon ist.
Boost-Hash ist so einfach wie
#include <boost/functional/hash.hpp>
int main()
{
boost::hash<std::string> string_hash;
std::size_t h = string_hash("Hash me");
}
Hier finden Sie Boost bei boost.org
Es ist nie zu spät für ein gutes Thema, und ich bin sicher, die Leute auf meine Erkenntnisse interessieren würde.
ich brauchte eine Hash-Funktion und nach dem Lesen dieser Nachricht und ein wenig Forschung über die Zusammenhänge hier gegebenen tun, kam ich mit dieser Variante von Daniel J. Bernstein-Algorithmus, den ich verwenden, um einen interessanten Test durchführen:
unsigned long djb_hashl(const char *clave)
{
unsigned long c,i,h;
for(i=h=0;clave[i];i++)
{
c = toupper(clave[i]);
h = ((h << 5) + h) ^ c;
}
return h;
}
Diese Variante Hashes Strings, den Fall zu ignorieren, die mein Bedürfnis entspricht die Hashing-Benutzer-Anmeldeinformationen anmelden. ‚Clave‘ ist ‚Schlüssel‘ in Spanisch. Es tut mir leid für die spanische, aber es ist meine Muttersprache und das Programm wird auf ihn geschrieben wird.
Nun, schrieb ich ein Programm, das Benutzername von ‚test_aaaa‘ auf ‚test_zzzz‘ generieren, und -nach die Saiten macht länger- ich eine zufällige Domain in dieser Liste hinzugefügt zu ihnen: ‚cloud-nueve.com‘, ' yahoo.com‘, 'gmail.com' und 'hotmail.com'. jeder von ihnen würde daher wie folgt aussehen:
test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, test_aaac@gmail.com, test_aaad@hotmail.com and so on.Hier
ist der Ausgang des Test -'Colision entre XXX XXX y‘bedeutet‚Kollision von XXX und XXX‘. 'Palabras' bedeutet 'Worte' und 'Total' ist das gleiche in beiden Sprachen -.
Buscando Colisiones...
Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
Total de Colisiones: 11
Total de Palabras : 456976
Das ist nicht schlecht, 11 Kollisionen von 456.976 (off natürlich den vollen 32-Bit als Tischlänge verwendet wird).
Ausführen des Programms mit 5 Zeichen, also von ‚test_aaaaa‘ auf ‚test_zzzzz‘, läuft tatsächlich aus dem Speicher den Aufbau der Tabelle. Unten ist der Ausgang. 'No Heu memoria para insertar XXXX (insertadas XXX)' bedeutet 'Es gibt keine Speicher links XXX (XXX eingefügt) einzufügen'. Grundsätzlich malloc () schlug fehl an diesem Punkt.
No hay memoria para insertar 'test_epjcv' (insertadas 2097701).
Buscando Colisiones...
...451 'colision' strings...
Total de Colisiones: 451
Total de Palabras : 2097701
Was bedeutet, nur 451 Kollisionen auf 2.097.701 Saiten. Beachten Sie, dass in keiner der Gelegenheiten gibt pro Code mehr als zwei Kollisionen waren. Was ich bestätige es eine große Hash für mich ist, wie das, was ich den Login-ID zu einer 40-Bit-eindeutigen ID für die Indizierung zu konvertieren ist. Also ich benutze diese die Anmeldeinformationen zu einer 32-Bit-Hash zu konvertieren und verwenden, um die zusätzlichen 8 Bits auf 255 Kollisionen pro Code Griff nach oben, die an den Testergebnissen lookign wäre fast unmöglich zu erzeugen.
Hope dies ist nützlich, um jemanden.
EDIT:
Wie die Testbox AIX ist, ich laufe es mit LDR_CNTRL = MAXDATA = 0x20000000 ihm mehr Arbeitsspeicher geben und es länger laufen, die Ergebnisse sind hier:
Buscando Colisiones ... Insgesamt de Colisiones: 2908 Insgesamt de Palabras: 5366384
Das ist 2908 nach 5.366.384 versucht !!
SEHR WICHTIG : Kompilieren des Programms mit -maix64 (so unsigned long 64 Bits), die Anzahl der Kollisionen ist 0 für alle Fälle !!!
Hier finden Sie aktuelle GNU gperf .
Bob Jenkins hat viele Hash-Funktionen zur Verfügung , von denen alle schnell sind und niedrige Kollisionsraten.
Sie können sehen, was .NET nutzt auf dem String.GetHashCode () -Methode mit Reflektor.
Ich würde eine Vermutung Gefahr, dass Microsoft viel Zeit Optimierung dafür ausgegeben. Auch sie haben in all der MSDN-Dokumentation gedruckt, dass sie unterliegt die ganze Zeit ändern. So klar ist es auf ihrer "Performance Zwicken Radar"; -)
Wäre ziemlich trivial zu portieren zu C ++ zu würde ich gedacht haben.
Es gibt einige gute Diskussion in dieser vorheriger Frage
Und ein schöner Überblick darüber, wie Hash-Funktionen zu wählen, sowie Statistiken über die Verteilung von mehreren gewöhnlichsten hier
Beschrieben ist hier eine einfache Möglichkeit, es selbst zu implementieren: http : //www.devcodenote.com/2015/04/collision-free-string-hashing.html
Ein Ausschnitt aus dem Beitrag:
, wenn wir sagen, einen Zeichensatz Kapital englischer Buchstaben, dann die Länge des Zeichensatzes ist 26, wobei A durch die Zahl 0, B durch die Zahl 1, C durch die Nummer 2 und so weiter bis Z dargestellt werden könnte Jetzt durch die Zahl 25, wann immer wir eine Reihe von diesem Zeichensatz auf eine eindeutige Nummer zuordnen möchten, führen wir die gleiche Umwandlung wie wir im Fall des binären Formats taten
CRC-32 . Es gibt etwa eine Billion Links auf Google für sie.
