Vous avez une bonne fonction de hachage pour une table de hachage C ++?
https://stackoverflow.com/questions/628790
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai besoin d'une implémentation de la fonction de hachage axée sur la performance en C ++ pour une table de hachage que je vais coder. J'ai déjà regardé autour de moi et je n'ai trouvé que des questions demandant ce qui constitue une bonne fonction de hachage & "En général &"; J'ai examiné CRC32 (mais où trouver une bonne implémentation?) Et quelques algorithmes de cryptographie. Ma table, cependant, a des exigences très spécifiques.
Voici à quoi ressemblera le tableau:
100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
examples: "become" "and he" ", not "
La priorité numéro un de ma table de hachage est la recherche rapide (récupération). Une insertion rapide n’est pas importante, mais une recherche rapide s’accompagnera. La suppression n’est pas importante et le re-hachage n’est pas une chose sur laquelle je vais me pencher. Pour gérer les collisions, je vais probablement utiliser un chaînage séparé comme décrit ci-après ici . J'ai déjà consulté cet article , mais je souhaiterais connaître l'opinion de ceux qui ont traité de tels tâche avant.
La solution
Vous pensez maintenant vouloir un hachage et quelque chose de rapide qui pourrait fonctionner dans votre cas, car vos chaînes ne font que 6 caractères, vous pouvez utiliser cette magie:
size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
return (*(size_t*)str)>> precision;
}
CRC est pour slowpokes;)
Explication: Cela fonctionne en convertissant le contenu du pointeur de chaîne en & "; Ressemblez à &"; un size_t (int32 ou int64 basé sur la correspondance optimale pour votre matériel). Ainsi, le contenu de la chaîne est interprété comme un nombre brut, vous n'avez plus à vous soucier des caractères, et vous décalez ensuite la précision requise (vous ajustez ce nombre pour obtenir les meilleures performances. J'ai trouvé que 2 fonctionne bien pour le hachage des chaînes. ensemble de quelques milliers).
Aussi, la partie la plus intéressante est tout compilateur décent sur du matériel moderne qui va hacher une chaîne comme celle-ci en une instruction d'assemblage, difficile à battre;)
Autres conseils
Ce polynôme simple fonctionne étonnamment bien. Je l’ai reçu de Paul Larson de Microsoft Research qui a étudié une grande variété de fonctions de hachage et de multiplicateurs de hachage.
unsigned hash(const char* s, unsigned salt)
{
unsigned h = salt;
while (*s)
h = h * 101 + (unsigned) *s++;
return h;
}
salt doit être initialisé sur une valeur choisie aléatoirement avant la création de la table de hachage pour se défendre contre attaques par table de hachage . Si ce n'est pas un problème pour vous, utilisez simplement 0.
La taille de la table est également importante pour minimiser les collisions. On dirait que le vôtre va bien.
Boost.Functional / Hash pourrait être de utiliser pour vous. Je ne l'ai pas essayé, je ne peux donc pas en garantir les performances.
Boost dispose également d'une bibliothèque CRC .
Je chercherais un Boost.Unordered en premier (ie boost :: unordered_map < >). Il utilise des cartes de hachage au lieu d'arbres binaires pour les conteneurs.
Je pense que certaines implémentations STL ont un hash_map < > conteneur dans l'espace de noms stdext.
La taille de votre table dictera quelle taille hachage vous devriez utiliser. Vous souhaitez bien sûr minimiser les collisions. Je ne suis pas sûr de ce que vous spécifiez en fonction du nombre maximal d'éléments et de la capacité (ils me semblent identiques). Quoi qu'il en soit, l'un ou l'autre de ces chiffres suggère qu'un hachage 32 bits serait suffisant. Vous pourriez vous en sortir avec le CRC16 (~ 65 000 possibilités), mais vous auriez probablement beaucoup de collisions à gérer. Par ailleurs, une collision peut être plus rapide à gérer qu’un hachage CRC32.
Je dirais, allez avec CRC32. Vous ne manquerez pas de documentation et de code exemple. Puisque vous avez déterminé vos maximums et que la vitesse est une priorité, utilisez un tableau de pointeurs. Utilisez le hachage pour générer un index. En cas de collision, incrémentez l’index jusqu’à atteindre un panier vide .. simple et rapide.
Puisque vous stockez des mots anglais, la plupart de vos caractères seront des lettres et il n’y aura pas beaucoup de variation dans les deux bits les plus significatifs de vos données. En plus de cela, je voudrais garder les choses très simples, en utilisant simplement XOR. Après tout, vous ne recherchez pas une force cryptographique, mais juste une distribution raisonnablement égale. Quelque chose dans ce sens:
size_t hash(const std::string &data) {
size_t h(0);
for (int i=0; i<data.length(); i++)
h = (h << 6) ^ (h >> 26) ^ data[i];
}
return h;
}
De plus, avez-vous regardé std :: tr1 :: hash en tant que fonction de hachage et / ou std :: tr1 :: unordered_map en tant qu'implémentation d'une table de hachage? Leur utilisation constituerait probablement une économie de travail considérable par rapport à la mise en place de vos propres classes.
La priorité numéro un de ma table de hachage est la recherche rapide (récupération).
Eh bien, vous utilisez la bonne structure de données, car la recherche dans une table de hachage est O (1)! :)
Le CRC32 devrait bien se passer. L'implémentation n'est pas si complexe, elle repose principalement sur les XOR. Assurez-vous simplement qu’il utilise un bon polynôme.
Que diriez-vous de quelque chose de simple:
// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];
// Hash function for six character strings.
int hash(const char *str)
{
int ret = 0, mult = 1;
for (const char *p = str; *p; *p++, mult *= 32) {
assert(*p >= 0 && *p < 256);
ret += mult * hashLookup[*p];
}
return ret;
}
Cela suppose des inits de 32 bits. Il utilise 5 bits par caractère, donc la valeur de hachage ne contient que 30 bits. Vous pourriez peut-être résoudre ce problème en générant six bits pour le premier ou les deux premiers caractères. Si votre jeu de caractères est suffisamment petit, vous n’avez peut-être pas besoin de plus de 30 bits.
Si vous devez rechercher des chaînes courtes et que l’insertion n’est pas un problème, vous pouvez peut-être utiliser un arbre B ou 2-3, vous ne gagnerez pas beaucoup en hachage dans votre cas.
Pour ce faire, vous devez placer une lettre dans chaque nœud. Vous devez donc d'abord rechercher le nœud & "a &"; puis cochez & "a &"; est les enfants de & "; p &"; et ses enfants de & "p &"; puis de & "l &"; puis " e " ;. Dans les cas où vous avez & "; Pomme &"; et " appliquer " vous devez rechercher le dernier nœud (car la seule différence réside dans le dernier & "; e &" et & "y &";)
Mais dans la plupart des cas, vous pourrez obtenir le mot après quelques étapes seulement (& "xylophone &"; > & "x & "- > &"; ylophone & ";), afin que vous puissiez optimiser comme ceci. Cela peut être plus rapide que le hachage
Depuis C ++ 11, C ++ fournit un std::hash< string >( string ) . C’est probablement une fonction de hachage efficace qui fournit une bonne distribution des codes de hachage pour la plupart des chaînes.
De plus, si vous envisagez d'implémenter une table de hachage, vous devriez maintenant envisager d'utiliser un C ++ std::unordered_map à la place.
