Wie funktioniert diese Hash-Funktion? Sind diese Zahlen zufällig?

Question

Ich lese gerade K & R "Die C-Programmiersprache" Buch. In „Structures“ Kapitel unter dem Unterthema von „Table Lookup“ (Seite 144), fand ich diese Hash-Funktion zu erzeugen

#define HASHSIZE 101 

struct nlist { 
    struct nlist *next; 
    char *name; 
    char *defn; 
} 

static struct nlist *hashtab[HASHSIZE]; 

unsigned hash(char *s) 
{ 
    unsigned hashval; 

    for (hashval = 0; *s != '\0'; s++) 
     hashval = *s + 31 * hashval; 
    return hashval % HASHSIZE; 
} 

Was ich nicht verstehe ist, was diese Funktion tatsächlich der Fall ist.

Ich denke, es erzeugt eine eindeutige Adresse (als Index auf Hashtab) für die angegebene Zeichenfolge (char * s).

Aber ich denke, zwei verschiedene Strings können den gleichen Index gegeben werden, da (Hashval% HASHSIZE) ist die angegebene Adresse (203% 101 = 405% 101 = 1).

Und warum wird HASHSIZE 101 und hashval mit 31 multipliziert? Warum nicht 100 oder 32?

Answer 1

Was ich nicht verstehe ist, was diese Funktion tatsächlich tut?

Es Hashes im Grunde die Zeichenfolge durch den char *s Zeiger zeigten, bis er das Ende der Saite auftritt, welche durch die '\0' Nullzeichen gekennzeichnet ist. Mit anderen Worten, es berechnet (oder Karten) eine gegebene Eingabezeichenfolge zu einem ganzzahligen Wert.

Sie können auch sehen, dass es dies tut, indem sie in der Zeichenfolge (dh die s++) durch jedes Zeichen gehen, so dass die Zeit Komplexität dieser Funktion linear abhängig von Stringlänge --oder O(N) - und dass sie vermeidet Erzeugen eines Wertes, der über die Grenzen des Arrays mit der letzten Modulusoperation hinausgeht.

Ich denke, es generiert eine eindeutige Adresse (als Index für Hashtab) für die angegebene Zeichenfolge (char * s).

Es nimmt den Eingangswert (das heißt die Zeichenfolge gehasht wird) und verwendet es die Index im Array, um herauszufinden, in dem die Zeichenkette angeordnet werden sollen. Es erzeugt also technisch keine Adresse, weil die Funktion keinen Zeiger zurückgibt. Das Wort Offset wäre hier genauer.

Aber ich denke, zwei verschiedene Strings können den gleichen Index gegeben werden, da (Hashval% HASHSIZE) ist die angegebene Adresse (203% 101 = 405% 101 = 1).

Wahr. Dies wird als Kollision bezeichnet. Hash-Funktionen zu schreiben, die Kollisionen gut vermeiden, ist nicht einfach. In den meisten Diskussionen werden Methoden zur Kollisionsauflösung angezeigt, um diese Fälle zu behandeln. Eine Methode könnte beispielsweise sein, jedes Array-Element in einen Zeiger auf eine verknüpfte Liste umzuwandeln, in der die Elemente, die kollidiert sind (d. H. Den Hashed-Index-Wert haben), angehängt werden. Es gibt andere Methoden, aber das ist eine andere Diskussion.

Idealerweise würde perfect hash functions verwendet werden, weil sie zu garantiert werden nie den gleichen Hash-Wert für zwei verschiedene Eingänge erzeugen, so dass eine Kollisionsauflösung nicht erforderlich.

Es gibt Buchkapitel zu diesen Themen, vor allem, wenn es um die Suche geht. Vielleicht möchten Sie diese lesen.

Und warum HASHSIZE ist 101 und Hashval wird mit 31 multipliziert (warum nicht 100 oder 32)?

Wegen 101 und 31 sind prime Zahlen und daher weniger wahrscheinlich Kollisionen am Ende Erzeugung durch Multiplikation/sich in der gleichen Eimer wie eine vorhergehende und verschiedene, Kettenteilungs.

Answer 2

Hash-Funktionen generierten möglicherweise den gleichen Hash-Wert für verschiedene Zeichenfolgen. Deshalb wird ein collision resolution benötigt.

Über den Wert für HASHSIZE und hashval: Ich bin kein Experte in Hash-Funktionen, aber in den wenigen, die ich gelesen habe, wurden die verwendeten Zahlen empirisch erhalten. Sie können die answer zu diesem anderen Thema lesen, das könnte Ihnen helfen.