Fonction de hachage pour les chaînes de caractères en C

Pourquoi sommes-nous en ajoutant 'a'+1 à la chaîne?

Nous ne sommes pas en ajoutant des, nous sont soustraction. En outre, nous ne pouvons pas le faire à la chaîne, nous le faisons pour les caractères un à un.

Ici est ce qu'il fait, selon les auteurs, les intentions d': étant donné une lettre de a à z, l'expression produit le numéro de séquence de la lettre: 'a' produit 1, 'b' produit 2, 'c' produit 3, et ainsi de suite.

Malheureusement, cette mise en œuvre est cassé: lorsque la lettre est en majuscule, isalpha retourne true, mais le résultat de l'expression ne vous donne pas le numéro de lettre. En fait, si votre ordinateur utilise l'encodage qui est cohérent avec les codes ASCII, le résultat devrait être un nombre négatif.

pourquoi faisons-nous la suite: hash = ((hash << 3) + n) % SIZE

Cette multiplie l'état de la valeur de hachage par huit (maj par trois est la même que la multiplication par huit), ajoute le numéro de la lettre, puis les limites de la valeur en obtenant le reste de la division par SIZE.

Depuis la valeur réelle de la code de hachage est de peu d'intérêt, tant il est sensible aux petits changements dans la parole, vous pouvez utiliser cette fonction à la place:

int hash (const char* word)
{
    unsigned int hash = 0;
    for (int i = 0 ; word[i] != '
int hash (const char* word)
{
unsigned int hash = 0;
for (int i = 0 ; word[i] != '\0' ; i++)
{
hash = 31*hash + word[i];
}
return hash % SIZE;
}
' ; i++)
    {
        hash = 31*hash + word[i];
    }
    return hash % SIZE;
}

Cet algorithme (sans le SIZE limite) est utilisé pour le calcul des codes de hachage de Strings en Java. Il est très simple et très efficace.

OriginalL'auteur dasblinkenlight

La soustraction est une tentative de convertir les lettres en minuscules pour les numéros de 1 à 26. La virgule est converti à 27 mais les majuscules sont converties en valeurs négatives (pour le jeu de caractères ASCII), ce qui a des effets secondaires néfastes.

En effet, il est possible comportement indéfini:

• Si le char type est signé, isalpha(word[i]) a un comportement indéfini négatif char valeurs. Pour éviter ce problème, l'argument de isalpha doit être jeté comme unsigned char: isalpha((unsigned char)word[i]).

• hash = ((hash << 3) + n) % SIZE a le potentiel de comportement indéfini trop: à gauche décalage des valeurs négatives est un comportement indéfini. Vous pouvez avoir une valeur négative pour hash si le premier caractère est une lettre majuscule. Modifier le type de hash et c à unsigned int pour éviter cela.

L'expression hash = ((hash << 3) + n) % SIZE est utilisé pour combiner les bits de tous les caractères en une valeur comprise entre 0 et SIZE-1. Notez cependant que si SIZE n'est pas une valeur non signée, l'expression peut produire une valeur négative entre -SIZE+1 et -1, qui aurait probablement des effets secondaires néfastes.

Le transcodage des valeurs de caractère n'a pas vraiment d'aider à la production d'une bonne fonction de hachage.

Ici est un plus sûr de la version:

#include <limits.h>

unsigned int hash(const char *word) {
    unsigned int hash = 0, c;

    for (size_t i = 0; word[i] != '
#include <limits.h>
unsigned int hash(const char *word) {
unsigned int hash = 0, c;
for (size_t i = 0; word[i] != '\0'; i++) {
c = (unsigned char)word[i];
hash = (hash << 3) + (hash >> (sizeof(hash) * CHAR_BIT - 3)) + c;
}
return hash % SIZE;
}
'; i++) {
        c = (unsigned char)word[i];
        hash = (hash << 3) + (hash >> (sizeof(hash) * CHAR_BIT - 3)) + c;
    }
    return hash % SIZE;
}

OriginalL'auteur chqrlie