Quelle est la meilleure fonction de hachage pour l'algorithme de Rabin-Karp ?

Question

Je cherche une fonction de hachage efficace pour l'algorithme de Rabin-Karp. Voici mon code actuel (langage de programmation C).

static bool f2(char const *const s1, size_t const n1, 
               char const *const s2, size_t const n2)
{
    uintmax_t hsub = hash(s2, n2);
    uintmax_t hs   = hash(s1, n1);
    size_t   nmax = n2 - n1;

    for (size_t i = 0; i < nmax; ++i) {
        if (hs == hsub) {
            if (strncmp(&s1[i], s2, i + n2 - 1) == 0)
                return true;
        }
        hs = hash(&s1[i + 1], i + n2);
    }
    return false;
}

J'ai envisagé quelques implémentations en C de Rabin-Karp, mais il y a des différences entre tous les codes. Ma question est donc la suivante : quelles sont les caractéristiques qu'une fonction de hachage Rabin-Karp devrait avoir ?

Answer 1

Un hachage extrêmement performant est le hachage bernstein. Il surpasse même de nombreux algorithmes de hachage populaires.

unsigned bernstein_hash ( void *key, int len )
{
    unsigned char *p = key;
    unsigned h = 0;
    int i;

    for ( i = 0; i < len; i++ )
        h = 33 * h + p[i];

    return h;
}

Bien entendu, vous pouvez essayer d'autres algorithmes de hachage, comme décrit ici : Fonction de hachage sur NIST

Note : Il n'a jamais été expliqué pourquoi le 33 est beaucoup plus performant que toutes les autres constantes "plus logiques".

Pour votre intérêt : Voici une bonne comparaison des différents algorithmes de hachage : strchr comparaison des algorithmes de hachage

Answer 2

Quelles sont les caractéristiques que doit avoir une fonction de hachage Rabin-Karp ?

Rabin-Karp a besoin d'un hachis roulant . Le hash le plus facile à rouler est une somme mobile. Adler-32 et Buzhash sont également assez simples et donnent de meilleurs résultats qu'une somme mobile.

N'importe laquelle de ces techniques de hachage par roulement devrait fonctionner pour Rabin-Karp :

• Somme en mouvement
  • supprimer l'octet le plus ancien par soustraction
  • ajouter un nouvel octet par addition
• Hachage par roulement polynomial
  • supprimer l'octet le plus ancien par soustraction
  • ajouter un nouvel octet à l'aide de la multiplication et de l'addition
• Empreinte digitale de Rabin
  • un hachage roulant polynomial dont le polynôme est irréductible sur GF(2)
• Hachage de tabulation
  • supprimer l'octet le plus ancien à l'aide d'une table de recherche et d'un xor
  • ajouter un nouvel octet avec une table de recherche et un xor
• Polynôme cyclique alias Buzhash
  • hachage de tabulation basé sur des décalages circulaires
• Somme de contrôle Adler-32
  • la somme de contrôle n'est pas roulante par défaut, mais elle peut être facilement ajustée pour "rouler".
  • supprimer l'octet le plus ancien par deux soustractions
  • ajouter un nouvel octet avec deux ajouts

Answer 3

Pour les problèmes liés aux petits alphabets, tels que la recherche de séquences d'acides nucléiques (par ex. alphabet = {A, T, C, G, U} ), nt-Hash peut être une bonne fonction de hachage. Elle utilise l'opération binaire, qui est plus rapide, et la mise à jour de hachage par roulement, et elle donne également des valeurs de hachage distribuées uniformes.

Answer 4

Considérant que les responsables de l'implémentation du JDK de Java auraient réfléchi, j'ai cherché à savoir quelle fonction y est utilisée.

Depuis ~ Java 19, https://github.com/openjdk/jdk/blob/jdk-19+23/src/java.base/share/classes/java/lang/String.java#L2326

La fonction de mise à jour est :

h' = 31 * h + c

La valeur initiale est 0.