Algorithme de hachage de chaîne rapide avec de faibles taux de collision avec un entier de 32 bits

Question

J'ai beaucoup de choses nommées non liées que je voudrais faire des recherches rapides contre. Un "aardvark" est toujours un "aardvark" partout, donc hacher la chaîne et réutiliser le nombre entier fonctionnerait bien pour accélérer les comparaisons. L'ensemble des noms est inconnu (et change avec le temps). Qu'est-ce qu'un algorithme de hachage de chaîne rapide qui générera de petites valeurs (32 ou 16 bits) et aura un faible taux de collision?

J'aimerais voir une implémentation optimisée spécifique à C / C ++.

Answer 1

Murmur Hash est plutôt sympa.

Answer 2

Une des variantes de FNV devrait répondre à vos exigences. Ils sont rapides et produisent des sorties assez uniformément distribuées.

Answer 3

Pour un ensemble de chaînes fixe, utilisez gperf.

Si votre jeu de chaînes change, vous devez choisir une fonction de hachage. Ce sujet a déjà été discuté:

http://stackoverflow.com/questions/98153/

Answer 4

Il existe également un bel article sur eternallyconfuzzled.com .

Le hachage One-at-a-Time pour chaînes de Jenkins devrait ressembler à ceci:

 #include <stdint.h>

uint32_t hash_string(const char * s)
{
    uint32_t hash = 0;

    for(; *s; ++s)
    {
    	hash += *s;
    	hash += (hash << 10);
    	hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}
 

Answer 5

Une autre solution qui pourrait être encore mieux en fonction de votre cas d'utilisation est interné chaînes. C'est la façon dont les symboles sont par exemple Lisp.

Un interné chaîne est une chaîne de caractères de l'objet dont la valeur est l'adresse de la chaîne d'octets. Ainsi, vous créez une interné objet string en vérifiant dans un tableau global: si la chaîne est là, de l'initialisation de l'interné de la chaîne à l'adresse de cette chaîne. Si non, vous l'insérez, puis initialiser votre internés de la chaîne.

Cela signifie que les deux internés chaînes construit à partir de la même chaîne de caractères ont la même valeur, qui est une adresse. Donc, si N est le nombre d'internés des chaînes dans votre système, les caractéristiques sont les suivantes:

• Lente construction (besoins de recherche et, éventuellement, l'allocation de mémoire)
• Nécessite des données globales et de synchronisation dans le cas de threads simultanés
• Comparer est O(1), parce que vous êtes en comparant les adresses, pas de chaîne réelle octets (ce qui signifie que le tri fonctionne bien, mais il ne sera pas un tri par ordre alphabétique).

Cheers,

Carl