Ce qui est une bonne fonction de hachage pour les mots en anglais?

J'ai une longue liste de mots anglais et je voudrais hachage eux. Ce serait une bonne fonction de hachage? Jusqu'à présent ma fonction de hachage, on additionne les valeurs ASCII des lettres puis modulo la taille du tableau. Je suis à la recherche de quelque chose de simple et efficace.

InformationsquelleAutor Mike G | 2011-10-08
  1. 17

    Simplement la somme des lettres n'est pas une bonne stratégie car une permutation donne le même résultat.

    Celui-ci (djb2) est très populaire et fonctionne bien avec des chaînes ASCII.

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

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

    return hash;
}

    Si vous avez besoin de plus de choix et de certaines mesures de performance, lire ici.

    Ajouté: ce sont général les fonctions de hachage, où le domaine d'entrée n'est pas connue à l'avance (sauf peut-être quelques très hypothèses générales: l'exemple ci-dessus fonctionne un peu mieux avec entrée ascii), qui est le plus habituel scénario. Si vous avez connu un domaine limité (ensemble de facteurs fixes), vous pouvez faire mieux, voir Fionn de réponse.

    • 5381 est la taille de la table ?
    • Non, c'est juste une "graine", plutôt arbitraire.
    • c'est la "semence" ou la valeur de départ. Celui-ci est communément connu comme le "Times " 33" de hachage.
    • où dois-je spécifier la longueur de la table ? si elle renvoie un nombre plus grand que mon tableau ?
    • Il peut renvoyer n'importe quel valide unsigned long valeur, en théorie. C'est à vous de manipuler la table de hachage pour l'adapter à vos contraintes.
    • en général, vous n'avez pas spécifier la taille de la table dans l'algorithme de hachage (et si vous ne savez pas à ce sujet, en utiliser une déjà faite de la table...). La table peut augmenter ou diminuer en fonction du nombre d'éléments (pour de bonnes mises en œuvre), de sorte que vous venez de calculer la valeur de hachage, et de prendre le hachage modulo la taille actuelle de savoir dans quel contenant pour le mettre.

    InformationsquelleAutor leonbloy
  2. 8

    Peut-être quelque chose comme cela pourrait vous aider: http://www.gnu.org/s/gperf/

    Il génère un optimisée de la fonction de hachage pour le domaine d'entrée.

    InformationsquelleAutor Fionn
  3. 6

    Si vous n'avez pas besoin d'être cryptographique sécurisé, je vous suggère le Murmure de Hachage. Il est extrêmement rapide et d'une grande diffusion. Facile à utiliser.

    http://en.wikipedia.org/wiki/MurmurHash

    http://code.google.com/p/smhasher/wiki/MurmurHash3

    Si vous avez besoin d'un hachage cryptographique sécurisé, alors je suggère SHA1 via OpenSSL.

    http://www.openssl.org/docs/crypto/sha.html

    • +1 pour MurmurHash, savez-vous si d'une comparaison entre CityHash et MurmurHash ? J'ai entendu de bonnes choses à la fois, mais n'a jamais vu une comparaison globale, juste eu le anecdotical faits.
    InformationsquelleAutor selbie
  4. 2

    Un peu de retard, mais ici, c'est une fonction de hachage, avec une très faible taux de collision pour la version 64 bits ci-dessous, et ~près~ aussi bien pour la version 32 bits:

    uint64_t slash_hash(const char *s)
//uint32_t slash_hash(const char *s)
{
    union { uint64_t h; uint8_t u[8]; };
    int i=0; h=strlen(s);
    while (*s) { u[i%8] += *s + i + (*s >> ((h/(i+1)) % 5)); s++; i++; }
    return h; //64-bit
    //return (h+(h>>32)); //32-bit
}

    La table de hachage, les numéros sont également très uniformément réparti dans la gamme possible, sans l'agglutination que j'ai pu détecter ce qui a été vérifié à l'aide de l'aléatoire cordes.

    [modifier]
    Également testé contre les mots extraits du texte local-les fichiers combinés avec LibreOffice dictionnaire/dictionnaire des synonymes des mots (en anglais et en français - plus de 97000 des mots et des constructions) avec 0 collisions en 64 bits et 1 collision en 32 bits 🙂

    (Également par rapport à FNV1A_Hash_Yorikke, djb2 et MurmurHash2 sur les mêmes ensembles: Yorikke & djb2 n'a pas bien; slash_hash ont fait légèrement mieux que MurmurHash2 dans tous les tests)

    • C'est un raisonnable en fonction de hachage. Je vous suggérons d'éviter les sans nom de l'union. -->> union { uint64_t h; uint8_t u[8]; } uu; et des changements similaires dans le code -->> uu.h=strlen(s); ... uu.u[i%8] += ... etc
    InformationsquelleAutor slashmais