Schneller String-Hashing-Algorithmus mit niedrigen Kollisionsraten und 32-Bit-Ganzzahlen

Murmeln Hash ist ziemlich nett.

Es gibt auch einen Netter Artikel bei eternallyconfuzzled.com .

Jenkins 'One-at-a-Time-Hash für Strings sollte ungefähr so ​​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;
}

Verwenden Sie für eine feste Zeichenfolge gperf.

Wenn sich Ihr String-Set ändert, müssen Sie eine Hash-Funktion auswählen. Dieses Thema wurde bereits diskutiert:

Was ist der beste Hashing-Algorithmus für eine stl-Zeichenfolge, wenn hash_map verwendet wird?

Eine andere Lösung, die je nach Anwendungsfall noch besser sein könnte, ist interne Zeichenfolgen. So funktionieren Symbole, z. in LISP.

Eine interne Zeichenfolge ist ein Zeichenfolgenobjekt, dessen Wert die Adresse der tatsächlichen Zeichenfolgenbytes ist. Sie erstellen also ein internes Zeichenfolgenobjekt, indem Sie eine globale Tabelle einchecken. Wenn sich die Zeichenfolge dort befindet, initialisieren Sie die interne Zeichenfolge mit der Adresse dieser Zeichenfolge. Wenn nicht, fügen Sie es ein und initialisieren dann Ihre interne Zeichenfolge.

Dies bedeutet, dass zwei interne Zeichenfolgen, die aus derselben Zeichenfolge erstellt wurden, denselben Wert haben, der eine Adresse ist. Wenn also N die Anzahl der internierten Zeichenfolgen in Ihrem System ist, sind die Merkmale:

• Langsame Konstruktion (Bedarfssuche und möglicherweise Speicherzuweisung)
• Erfordert globale Daten und Synchronisation bei gleichzeitigen Threads
• Compare ist O (1), da Sie Adressen und nicht die tatsächlichen Zeichenfolgenbytes vergleichen (dies bedeutet, dass die Sortierung gut funktioniert, aber keine alphabetische Sortierung erfolgt).

Prost,

Carl

Für ein gutes Fach ist es nie zu spät und ich bin sicher, dass die Leute an meinen Ergebnissen interessiert sind.

Ich brauchte eine Hash-Funktion und nachdem ich diesen Beitrag gelesen und einige Nachforschungen über die hier angegebenen Links angestellt hatte, kam ich zu dieser Variante von Daniel J Bernsteins Algorithmus, mit der ich einen interessanten Test durchführte:

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;
}
</ code>

Bei dieser Variante werden Zeichenfolgen mit Hashes behandelt, wobei der Groß- und Kleinschreibung nicht Rechnung getragen wird. "Clave" ist "Schlüssel" auf Spanisch. Das Spanisch tut mir leid, aber es ist meine Muttersprache und das Programm ist darauf geschrieben.

Nun, ich habe ein Programm geschrieben, das Benutzernamen von 'test_aaaa' bis 'test_zzzz' generiert. Um die Zeichenfolgen zu verlängern, habe ich ihnen eine zufällige Domain in dieser Liste hinzugefügt: 'cloud-nueve.com', 'yahoo.com "," gmail.com "und" hotmail.com ". Daher würde jeder von ihnen so aussehen:

 
 [email protected], [email protected], 
 [email protected], [email protected] und so weiter. 
 

Hier ist die Ausgabe des Tests - "Kollision zwischen XXX und XXX" bedeutet "Kollision zwischen XXX und XXX". 'palabras' bedeutet 'words' und 'Total' ist in beiden Sprachen gleich.

 
 Buscando Colisiones ... 
 Colision entre '[email protected]' y '[email protected]' (1DB903B7) 
 Colision entre ' [email protected] 'y' [email protected] '(2F5BC088) 
 Colision entre' [email protected] 'y' [email protected] '(51FD09CC) 
 Colision Entre '[email protected]' y '[email protected]' (52F5480E) 
 Colision Entre '[email protected]' y '[email protected]' (74FF72E2) 
 Colision entre '[email protected]' y '[email protected]' (7FD70008) 
 Colision entre '[email protected] y' [email protected] '(9BD351C4) 
 Colision entre '[email protected]' und '[email protected]' (A86953E1) 
 Colision entre '[email protected] und' [email protected] '( BA6B0718) 
 Colision entre '[email protected]' y '[email protected]' (D0523F88) 
 Colision entre '[email protected] y' [email protected] '( DEE0 8108) 
 Total de Colisiones: 11 
 Total de Palabras: 456976 
 

Das ist nicht schlecht, 11 Kollisionen von 456.976 (natürlich mit den vollen 32 Bit als Tabellenlänge).

Das Ausführen des Programms mit 5 Zeichen (von 'test_aaaaa' bis 'test_zzzzz') hat tatsächlich nicht genügend Speicherplatz, um die Tabelle zu erstellen. Unten ist die Ausgabe. "Keine Heumemoria für Einfügung XXXX (Einfügung XXX)" bedeutet "Es ist kein Speicher mehr zum Einfügen von XXX (Einfügung XXX) vorhanden". Grundsätzlich ist malloc () an diesem Punkt gescheitert.

 
 Keine Heumemoria para insertar 'test_epjcv' (insertadas 2097701). 
 
 Buscando Colisiones ... 
 
 .. .451 "Colision" -Saiten ... 
 
 Gesamtzahl der Colisiones: 451 
 Gesamtzahl der Palabras: 2097701 
 

Das bedeutet nur 451 Kollisionen mit 2.097.701 Saiten. Beachten Sie, dass in keinem Fall mehr als 2 Kollisionen pro Code aufgetreten sind. Ich bestätige, dass es ein großartiger Hash für mich ist, da ich die Login-ID in eine 40-Bit-ID für die Indizierung umwandeln muss. Ich verwende dies also, um die Anmeldeinformationen in einen 32-Bit-Hash umzuwandeln, und verwende die zusätzlichen 8 Bits, um bis zu 255 Kollisionen pro Code zu verarbeiten, die beim Betrachten der Testergebnisse fast unmöglich zu generieren wären.

Hoffe, das ist nützlich für jemanden.

EDIT:

Da die Testbox AIX ist, führe ich sie mit LDR_CNTRL = MAXDATA = 0x20000000 aus, um mehr Arbeitsspeicher und eine längere Laufzeit zu erzielen. Die Ergebnisse sind hier:

Buscando Colisiones ... Gesamtanzahl der Colisiones: 2908 Gesamtanzahl der Palabras: 5366384

Das ist 2908 nach 5.366.384 Versuchen !!

SEHR WICHTIG: Beim Kompilieren des Programms mit -maix64 (also 64 Bit ohne Vorzeichen) beträgt die Anzahl der Kollisionen in allen Fällen 0 !!!

Warum verwenden Sie nicht einfach Boost-Bibliotheken? Ihre Hashing-Funktion ist einfach zu bedienen und die meisten Dinge in Boost werden bald Teil des C++ - Standards sein. Einiges davon ist schon.

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");
}

Sie finden boost unter boost.org

Bob Jenkins hat viele Hash-Funktionen zur Verfügung , die alle schnell sind und niedrige Kollisionsraten haben.

Schauen Sie sich GNU gperf an.

Die Hsieh -Hash-Funktion ist ziemlich gut und enthält einige Benchmarks/Vergleiche als allgemeine Hash-Funktion in C. Je nachdem, was Sie möchten (es ist nicht ganz offensichtlich), möchten Sie möglicherweise Folgendes in Betracht ziehen: cdb stattdessen.