Hash-Funktion für String

Lesezeit: 13 Minuten

lilawoods Benutzeravatar
Fliederholz

Ich arbeite an einer Hash-Tabelle in C-Sprache und teste die Hash-Funktion für Zeichenfolgen.

Die erste Funktion, die ich ausprobiert habe, besteht darin, ASCII-Code hinzuzufügen und Modulo (% 100), aber beim ersten Test der Daten habe ich schlechte Ergebnisse: 40 Kollisionen für 130 Wörter.

Die endgültigen Eingabedaten enthalten 8000 Wörter (es handelt sich um ein Wörterbuch, das in einer Datei gespeichert wird). Die Hash-Tabelle wird als deklariert int table[10000] und enthält die Position des Wortes in einer .txt-Datei.

  • Welches ist der beste Algorithmus zum Hashing von Strings?
  • Und wie bestimmt man die Größe der Hash-Tabelle?

  • Wenn Ihre Hash-Tabelle 10.000 Einträge hat, warum sollten Sie Modulo 100 verwenden? 40 Kollisionen aus 130 Wörtern herauszuholen, ist bei einem so kleinen Modul nicht überraschend.

    – Carey Gregory

    5. Oktober 2011 um 19:24 Uhr

  • Sehen burtleburtle.net/bob/hash/evahash.html und partow.net/programming/hashfunctions Dafür gibt es Ressourcen zu verschiedenen Hashings (von allgemein über String bis hin zu Krypto).

    Benutzer166390

    5. Oktober 2011 um 19:33 Uhr


  • Um @CareyGregory zu verdeutlichen: Sie erkennen, dass als grundlegende mathematische Wahrheit 130 Elemente in 100 Eimern (dh Mod 100) 30 Kollisionen erzeugen müssen (wobei die Kollision jedes Mal gezählt wird, wenn ein zweites, drittes usw. Element eingefügt wird ein Eimer), richtig? Du bist also nur knapp darüber.

    – Derobert

    5. Oktober 2011 um 19:34 Uhr


  • @lilawood: OK, das habe ich mir gedacht, aber um ein besserer Test zu sein, sollten Sie 80 Wörter mit einer Hash-Tabelle mit 100 Einträgen verwenden. Das würde Ihnen die gleichen Proportionen wie Ihre Live-Daten geben und keine Kollisionen erzwingen.

    – Carey Gregory

    5. Oktober 2011 um 21:29 Uhr

  • Mögliches Duplikat von Good Hash Function for Strings

    – MJ Rayburn

    2. September 2017 um 1:01 Uhr

Ich hatte gute Ergebnisse mit djb2 von Dan Bernstein.

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

  • Die in der Antwort verlinkte Seite ist sehr interessant.

    – Adrian Plisson

    5. Oktober 2011 um 19:31 Uhr

  • wie läuft das programm aus der while-schleife?? =S

    – Daniel N.

    19. Mai 2015 um 1:30 Uhr

  • @danfly09 Wenn c null ist. Das Äquivalent von while(c = *str++) wäre (0 != (c = *str++))

    – Rxantos

    5. Juli 2015 um 19:58 Uhr

  • @Josepas Die Hash-Funktion sollte idealerweise a zurückgeben size_t oder ein anderer Wert ohne Vorzeichen (z. B. der vorzeichenlose lange Wert in diesem Code). Das Anrufer ist dafür verantwortlich, Modulo des Ergebnisses zu nehmen, um es an die Hash-Tabelle anzupassen. Der Anrufer kontrolliert den Tabellenplatz, zu dem gehasht wird; nicht die Funktion. Es gibt nur eine unsignierte Zahl zurück.

    – WhozCraig

    18. August 2016 um 6:58 Uhr


  • toll. Dieser Algorithmus schlägt Murmur-Hash, FNV-Varianten-Hashes und viele andere um die Wette! +1

    – David Haim

    4. September 2016 um 14:40 Uhr

Benutzeravatar von Jerry Coffin
Jerry Sarg

Erstens tun Sie das im Allgemeinen nicht einen kryptografischen Hash für eine Hash-Tabelle verwenden möchten. Ein Algorithmus, das ist sehr schnell nach kryptografischen Standards 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 rotieren und dann den aktuellen Hash-Code mit dem aktuellen Byte XOR zu machen. Wiederholen Sie dies, bis Sie das Ende der Saite erreichen. Beachten Sie, dass Sie dies im Allgemeinen tun nicht möchten, dass die Rotation auch ein gerades Vielfaches der Bytegröße ist.

Wenn Sie beispielsweise den üblichen Fall von 8-Bit-Bytes annehmen, könnten Sie um 5 Bit rotieren:

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

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 Korrektheit bei einigen Arten von Hash-Auflösungen sicherzustellen) oder eine Potenz von 2 (daher kann der Wert auf den richtigen Bereich mit einer einfachen Bitmaske).

  • Dies ist nicht c, aber ich würde mich für Ihre Gedanken zu dieser verwandten Antwort interessieren: stackoverflow.com/a/31440118/3681880

    – Suragch

    15. Juli 2015 um 21:24 Uhr

  • @Suragch: Seit ich dies geschrieben habe, haben einige Prozessoren damit begonnen, entweder spezielle Hardware zur Beschleunigung der SHA-Berechnung zu integrieren, was sie viel wettbewerbsfähiger gemacht hat. Allerdings bezweifle ich, dass Ihr Code so sicher ist, wie Sie denken – zum Beispiel haben IEEE-Gleitkommazahlen zwei verschiedene Bitmuster (0 und -0), die dieselben Hashes erzeugen sollten (sie werden als gleichwertig miteinander verglichen ).

    – Jerry Sarg

    15. Juli 2015 um 22:02 Uhr

  • @Jerry Coffin welche Bibliothek brauche ich für die Funktion rol()?

    – thanos.a

    28. März 2020 um 15:50 Uhr

  • @thanos.a: Mir ist nicht bekannt, dass es sich in einer Bibliothek befindet, aber das Rollen Ihrer eigenen erfordert nur ein oder zwei Zeilen Code. Verschieben Sie einen Block nach links, den anderen Block nach rechts und/oder sie zusammen.

    – Jerry Sarg

    29. März 2020 um 4:40 Uhr

  • @thanos.a, du kannst es wie von Hand rollen static inline unsigned rol(unsigned r, int k) {return (r << k) | (r >> (32 - k));} (unter der Annahme von 32-Bit-Ganzzahlen). Zumindest GCC auf x86-64 kompiliert dies zu einer Anweisung.

    – Vonbrand

    22. Juli 2021 um 0:27 Uhr

Wikipedia zeigt eine nette String-Hash-Funktion namens Jenkins One At A Time Hash. Es zitiert auch verbesserte Versionen dieses Hashs.

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

Benutzeravatar von Andriy Makukha
Andri Makukha

Ich wollte die Antwort von Xiaoning Bian überprüfen, aber leider hat er seinen Code nicht gepostet. Also habe ich eine kleine Testsuite implementiert und verschiedene kleine Hash-Funktionen auf der Liste von ausgeführt 466.000 englische Wörter um die Anzahl der Kollisionen für jeden zu sehen:

Hash function      |     Collisions | Time (words) | Time (file)
=================================================================
CRC32              |    23 (0.005%) |      112 ms  |      38 ms
MurmurOAAT         |    26 (0.006%) |       86 ms  |      10 ms
FNV hash           |    32 (0.007%) |       87 ms  |       7 ms
Jenkins OAAT       |    36 (0.008%) |       90 ms  |       8 ms
DJB2 hash          |   344 (0.074%) |       87 ms  |       5 ms
K&R V2             |   356 (0.076%) |       86 ms  |       5 ms
Coffin             |   763 (0.164%) |       86 ms  |       4 ms
x17 hash           |  2242 (0.481%) |       87 ms  |       7 ms
-----------------------------------------------------------------
MurmurHash3_x86_32 |    19 (0.004%) |       90 ms  |       3 ms

Ich habe Zeit für beides eingeschlossen: alle Wörter einzeln zu hashen und die gesamte Datei aller englischen Wörter einmal zu hashen. Ich habe auch eine komplexere enthalten MurmurHash3_x86_32 in meinen Test als Referenz.

Fazit:

  • Es gibt fast keinen Sinn die beliebte DJB2-Hash-Funktion für Strings auf der Intel x86-64-Architektur (oder AArch64 für diese Angelegenheit) zu verwenden. Da es viel mehr Kollisionen hat als ähnliche Funktionen (MurmurOAAT, FNV und Jenkins OAAT) bei sehr ähnlichem Durchsatz. Bernsteins DJB2 schneidet auf kurzen Saiten besonders schlecht ab. Beispiel Kollisionen: Liz/MHz, Bon/COM, Rey/SEX.

Testcode:

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINE 2048
#define SEED    0x12345678

uint32_t DJB2_hash(const uint8_t *str)
{
    uint32_t hash = 5381;
    uint8_t c;
    while ((c = *str++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash;
}

uint32_t FNV(const void* key, int len, uint32_t h)
{
    // Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
    h ^= 2166136261UL;
    const uint8_t* data = (const uint8_t*)key;
    for(int i = 0; i < len; i++)
    {
        h ^= data[i];
        h *= 16777619;
    }
    return h;
}

uint32_t MurmurOAAT_32(const char* str, uint32_t h)
{
    // One-byte-at-a-time hash based on Murmur's mix
    // Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
    for (; *str; ++str) {
        h ^= *str;
        h *= 0x5bd1e995;
        h ^= h >> 15;
    }
    return h;
}

uint32_t KR_v2_hash(const char *s)
{
    // Source: https://stackoverflow.com/a/45641002/5407270
    uint32_t hashval = 0;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval;
}

uint32_t Jenkins_one_at_a_time_hash(const char *str, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += str[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

uint32_t crc32b(const uint8_t *str) {
    // Source: https://stackoverflow.com/a/21001712
    unsigned int byte, crc, mask;
    int i = 0, j;
    crc = 0xFFFFFFFF;
    while (str[i] != 0) {
        byte = str[i];
        crc = crc ^ byte;
        for (j = 7; j >= 0; j--) {
            mask = -(crc & 1);
            crc = (crc >> 1) ^ (0xEDB88320 & mask);
        }
        i = i + 1;
    }
    return ~crc;
}

inline uint32_t _rotl32(uint32_t x, int32_t bits)
{
    return x<<bits | x>>(32-bits);      // C idiom: will be optimized to a single operation
}

uint32_t Coffin_hash(char const *input) { 
    // Source: https://stackoverflow.com/a/7666668/5407270
    uint32_t result = 0x55555555;
    while (*input) { 
        result ^= *input++;
        result = _rotl32(result, 5);
    }
    return result;
}

uint32_t x17(const void * key, int len, uint32_t h)
{
    // Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
    const uint8_t * data = (const uint8_t*)key;
    for (int i = 0; i < len; ++i)
    {
        h = 17 * h + (data[i] - ' ');
    }
    return h ^ (h >> 16);
}

uint32_t apply_hash(int hash, const char* line)
{
    switch (hash) {
    case 1: return crc32b((const uint8_t*)line);
    case 2: return MurmurOAAT_32(line, SEED);
    case 3: return FNV(line, strlen(line), SEED);
    case 4: return Jenkins_one_at_a_time_hash(line, strlen(line));
    case 5: return DJB2_hash((const uint8_t*)line);
    case 6: return KR_v2_hash(line);
    case 7: return Coffin_hash(line);
    case 8: return x17(line, strlen(line), SEED);
    default: break;
    }
    return 0;
}

int main(int argc, char* argv[])
{
    // Read arguments
    const int hash_choice = atoi(argv[1]);
    char const* const fn = argv[2];

    // Read file
    FILE* f = fopen(fn, "r");

    // Read file line by line, calculate hash
    char line[MAXLINE];
    while (fgets(line, sizeof(line), f)) {
        line[strcspn(line, "\n")] = '\0';   // strip newline
        uint32_t hash = apply_hash(hash_choice, line);
        printf("%08x\n", hash);
    }
    fclose(f);

    return 0;
}

PS Eine umfassendere Übersicht über Geschwindigkeit und Qualität moderner Hash-Funktionen finden Sie in SMHasher-Repository von Reini Urban (rurban). Beachten Sie die Spalte „Qualitätsprobleme“ in der Tabelle.

Es gibt eine Reihe vorhandener Hashtable-Implementierungen für C, von der C-Standardbibliothek hcreate/hdestroy/hsearch bis zu denen in der APR und glatt, die auch vorgefertigte Hash-Funktionen bereitstellen. Ich würde dringend empfehlen, diese zu verwenden, anstatt eine eigene Hashtabelle oder Hashfunktion zu erfinden. Sie wurden stark für gängige Anwendungsfälle optimiert.

Wenn Ihr Datensatz jedoch statisch ist, ist Ihre beste Lösung wahrscheinlich die Verwendung von a perfektes Hasch. gperf generiert für Sie einen perfekten Hash für einen bestimmten Datensatz.

  • hsearch sucht durch Vergleichen der Zeichenfolgen oder der Zeichenfolge ptr address? Ich denke, es wird nur die PTR-Adresse überprüft? Ich habe versucht, verschiedene Zeiger, aber denselben String-Wert zu verwenden. hsearch schlägt fehl und gibt an, dass keine Elemente gefunden wurden

    – Sandeep

    5. Juli 2016 um 13:45 Uhr

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 (etwa 25 sind für 466k zufällige 32-Bit-Hashes zu erwarten). Meine Empfehlung ist die Verwendung MurmurHash falls verfügbar, ist es sehr schnell, weil es mehrere Bytes gleichzeitig aufnimmt. Aber wenn Sie eine einfache und kurze Hash-Funktion zum Kopieren und Einfügen in Ihr Projekt benötigen, würde ich empfehlen, die One-Byte-at-a-Time-Version von murmurs zu verwenden:

uint32_t inline MurmurOAAT32 ( const char * key)
{
  uint32_t h(3323198485ul);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e995;
    h ^= h >> 15;
  }
  return h;
}

uint64_t inline MurmurOAAT64 ( const char * key)
{
  uint64_t h(525201411107845655ull);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e9955bd1e995;
    h ^= h >> 47;
  }
  return h;
}

Die optimale Größe einer Hash-Tabelle ist – kurz gesagt – so groß wie möglich, während sie noch in den Speicher passt. Da wir normalerweise nicht wissen oder nachschlagen möchten, wie viel Speicher wir zur Verfügung haben, und sich dieser sogar ändern kann, beträgt die optimale Hash-Tabellengröße ungefähr das Doppelte der erwarteten Anzahl von Elementen, die in der Tabelle gespeichert werden sollen. Wenn Sie viel mehr als das zuweisen, wird Ihre Hash-Tabelle schneller, aber bei schnell abnehmenden Erträgen wird Ihre Hash-Tabelle, wenn Sie sie kleiner machen, exponentiell langsamer. Dies liegt daran, dass es eine nichtlineare gibt Kompromiss zwischen räumlicher und zeitlicher Komplexität für Hash-Tabellen mit einem optimalen Ladefaktor von 2-sqrt (2) = 0,58 … anscheinend.

  • hsearch sucht durch Vergleichen der Zeichenfolgen oder der Zeichenfolge ptr address? Ich denke, es wird nur die PTR-Adresse überprüft? Ich habe versucht, verschiedene Zeiger, aber denselben String-Wert zu verwenden. hsearch schlägt fehl und gibt an, dass keine Elemente gefunden wurden

    – Sandeep

    5. Juli 2016 um 13:45 Uhr

djb2 ist gut

Obwohl djb2wie es auf stackoverflow von cnicutar präsentiert wird, ist mit ziemlicher Sicherheit besser, ich denke, es lohnt sich, das zu zeigen K&R Hashes auch:

Einer der K&R-Hashes ist schrecklich, einer ist wahrscheinlich ziemlich gut:

  1. Offenbar A abscheulich Hash-Algorithmus, wie in K&R 1st Edition vorgestellt. Dies ist einfach eine Summe aller Bytes in der Zeichenfolge (Quelle):
    unsigned long hash(unsigned char *str)
    {
        unsigned int hash = 0;
        int c;
    
        while (c = *str++)
            hash += c;
    
        return hash;
    }
    
  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: Unbedingt entfernen % HASHSIZE aus der return-Anweisung, wenn Sie vorhaben, die Modulus-Größenanpassung an Ihre Array-Länge außerhalb des Hash-Algorithmus durchzuführen. Außerdem empfehle ich Ihnen, den Typ return und “hashval” zu machen unsigned longoder noch besser: uint32_t oder uint64_tstatt einfach unsigned (Int.). Dies ist ein einfacher Algorithmus, der berücksichtigt Byte-Reihenfolge von jedem Byte in der Zeichenfolge, indem Sie diesen Algorithmusstil ausführen: hashvalue = new_byte + 31*hashvaluefür alle Bytes im String:
    unsigned hash(char *s)
    {
        unsigned hashval;
    
        for (hashval = 0; *s != '\0'; s++)
            hashval = *s + 31*hashval;
        return hashval % HASHSIZE;
    }
    

Beachten Sie, dass aus den beiden Algorithmen klar hervorgeht, dass ein Grund, warum der Hash der 1. Ausgabe so schrecklich ist, darin besteht, dass er Zeichenfolgenzeichen NICHT berücksichtigt bestellenAlso hash("ab") würde daher denselben Wert zurückgeben wie hash("ba"). Das ist nicht also mit dem Hash der 2. Ausgabe, der (viel besser!) Zwei verschiedene Werte für diese Zeichenfolgen zurückgeben würde.

Die GCC C++11-Hashing-Funktion, die von der std::unordered_map<> Template-Container-Hash-Tabelle ist Ausgezeichnet.

Die GCC C++11-Hashing-Funktionen, die für verwendet werden unordered_map (eine Hash-Tabellenvorlage) und unordered_set (eine Hash-Set-Vorlage) wie folgt aussehen.

Code:

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}

MurmerHash3 von Austin Appleby ist Beste! Es ist sogar eine Verbesserung gegenüber seinem gcc C++11 std::unordered_map<> Hash oben verwendet.

Es ist nicht nur das Beste von allen, sondern Austin hat MurmerHash3 öffentlich zugänglich gemacht. Siehe meine andere Antwort dazu hier: Was ist die Standard-Hash-Funktion, die in C++ std::unordered_map verwendet wird?.

Siehe auch

  1. Andere Hashtabellen-Algorithmen zum Ausprobieren und Testen: http://www.cse.yorku.ca/~oz/hash.html. Dort erwähnte Hash-Algorithmen:
    1. djb2
    2. sdbm
    3. verlieren verlieren (K&R 1. Auflage)

1424730cookie-checkHash-Funktion für String

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy