Hash-Funktion für String

124

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 !

:-)

lilawood
quelle
11
Wenn Ihre Hash-Tabelle 10K-Einträge enthält, warum sollten Sie Modulo 100 verwenden? 40 Kollisionen aus 130 Wörtern zu erhalten, ist bei einem so kleinen Modul nicht überraschend.
Carey Gregory
13
Siehe burtleburtle.net/bob/hash/evahash.html und partow.net/programming/hashfunctions, für die Ressourcen zu verschiedenen Hashes (von allgemein über String bis Krypto) bereitgestellt werden.
3
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 eingegeben wird ein Eimer), richtig? Du bist also nur ein bisschen darüber.
Derobert
4
@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
4
Mögliches Duplikat der guten Hash-Funktion für Strings
MJ Rayburn

Antworten:

185

Ich habe gute Ergebnisse mit djb2Dan Bernstein erzielt .

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;
}
cnicutar
quelle
37
Die in der Antwort verlinkte Seite ist sehr interessant.
Adrien Plisson
2
Wie läuft das Programm aus der while-Schleife? = S
Daniel N.
1
@ danfly09 Wenn c Null ist. Das Äquivalent von while (c = * str ++) wäre (0! = (C = * str ++))
rxantos
5
@Josepas Die Hash-Funktion sollte idealerweise einen size_toder 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.
WhozCraig
6
tolle. Dieser Algorithmus hat Murmur-Hash, FNV-Varianten-Hashes und viele andere zum Teufel geschlagen! +1
David Haim
24

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:

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 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).

Jerry Sarg
quelle
Dies ist nicht c, aber ich würde mich für Ihre Gedanken zu dieser verwandten Antwort interessieren: stackoverflow.com/a/31440118/3681880
Suragch
1
@Suragch: Seit ich dies geschrieben habe, haben einige Prozessoren begonnen, spezielle Hardware zu integrieren, um die SHA-Berechnung zu beschleunigen, was die Wettbewerbsfähigkeit erheblich erhöht hat. Ich bezweifle jedoch, dass Ihr Code so sicher ist, wie Sie denken. Beispielsweise haben IEEE-Gleitkommazahlen zwei verschiedene Bitmuster (0 und -0), die dieselben Hashes erzeugen sollten (sie werden miteinander verglichen) ).
Jerry Coffin
@ Jerry Coffin Welche Bibliothek brauche ich für die Funktion rol ()?
thanos.a
@ thanos.a: Mir ist nicht bewusst, dass es sich in einer Bibliothek befindet, aber das Rollen Ihrer eigenen erfordert nur ein oder zwei Codezeilen. Verschieben Sie einen Block nach links, den anderen nach rechts und / oder zusammen.
Jerry Coffin
8

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

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;
}
RushPL
quelle
8

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.

Nick Johnson
quelle
hsearch sucht durch Vergleichen der Strings oder der String-PTR-Adresse? Ich denke, es wird nur die ptr-Adresse überprüft? Ich habe versucht, verschiedene Zeiger zu verwenden, aber dieselbe Zeichenfolge. hsearch schlägt fehl und gibt an, dass keine Elemente gefunden wurden
mk ..
3

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:

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 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.

Wolfgang Brehm
quelle
2

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.

Pascal Cuoq
quelle
1
Die erwartete Anzahl von Hash-Kollisionen beträgt 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.
Wolfgang Brehm
2

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.

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: Stellen Sie sicher, dass Sie diese % HASHSIZEaus 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 longanstelle des einfachen unsigned(int) den Typ return und "hashval" vorzunehmen .

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 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 wird hash("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) und unordered_set(eine Hash-Set-Vorlage) verwendeten GCC C ++ 11-Hashing-Funktionen scheinen wie folgt zu sein.

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;
}
Gabriel Staples
quelle
2

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 .

Hash function    | collision rate | how many minutes to finish
==============================================================
MurmurHash3      |           6.?% |                      4m15s
Jenkins One..    |           6.1% |                      6m54s   
Bob, 1st in link |          6.16% |                      5m34s
SuperFastHash    |            10% |                      4m58s
bernstein        |            20% |       14s only finish 1/20
one_at_a_time    |          6.16% |                       7m5s
crc              |          6.16% |                      7m56s

Eine seltsame Sache ist, dass fast alle Hash-Funktionen eine Kollisionsrate von 6% für meine Daten haben.

Xiaoning Bian
quelle
Während dieser Link die Frage beantworten kann, ist es besser, die wesentlichen Teile der Antwort hier aufzunehmen und den Link als Referenz bereitzustellen. Nur-Link-Antworten können ungültig werden, wenn sich die verknüpfte Seite ändert.
thewaywewere
Für eine gute Tabelle positiv bewertet, ist es auch wichtig, den Quellcode für jeden dieser Hashes in Ihre Antwort aufzunehmen. Andernfalls können die Links unterbrochen werden und wir haben kein Glück.
Gabriel Staples
Die erwartete Anzahl von Kollisionen sollte 9,112499989700318E + 7 oder 0,103 * 960³ betragen, wenn die Hashes wirklich zufällig waren. Ich wäre also nicht überrascht gewesen, wenn sie alle um diesen Wert herum wären, aber 0,0616 * 960³ scheint ein bisschen anders zu sein, fast so, als ob die Hashes sind gleichmäßiger verteilt als zufällig erwartet, und bei einer Länge von 64 Bytes sollte diese Grenze auf jeden Fall erreicht werden. Können Sie die von Ihnen gehashten Zeichenfolgen freigeben, damit ich versuchen kann, sie zu reproduzieren?
Wolfgang Brehm
0

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.

Michael Nett
quelle
Wenn ich mich nicht irre, leidet dies unter dem gleichen Problem wie K & R 1st in Gabriels Antwort; dh "ab" und "ba" werden auf den gleichen Wert gehasht.
Johann Oskarsson