La fonction par défaut provient de std :: hash. Je me demande s'il existe de meilleures fonctions de hachage pour économiser du temps de calcul? pour les clés entières ainsi que les clés de chaîne.Existe-t-il des fonctions de hachage plus rapides pour unordered_map/set en C++?
J'ai essayé City Hash de Google pour les clés entières et les chaînes de caractères, mais ses performances sont un peu moins bonnes que celles de std :: hash.
Vous devez expliquer «mieux» dans quel sens? La fonction de hachage la plus rapide serait simplement utiliser la valeur, mais cela est inutile. Une réponse plus spécifique dépend de vos contraintes de mémoire et des probabilités de collision que vous êtes prêt à accepter. Notez également que les fonctions de hachage intégrées sont construites différemment pour différents types, et par conséquent, j'attends que les fonctions de hachage pour int et string soient déjà optimisées au sens général pour la complexité temporelle et la probabilité de collision.
Mon but est de réduire le CPU global. Donc, je suppose que (1) le calcul de hachage lui-même est rapide; (2) la collision est faible. Je ne sais pas si je suis sur la bonne voie. – SuperBald
@superbald: la question est pourquoi pensez-vous que vous pouvez faire mieux? Les fonctions standard de la bibliothèque ont été écrites par des programmeurs extrêmement intelligents, soucieux de produire les meilleures fonctions de bibliothèque possibles. Si vous pouvez faire mieux, c'est probablement parce que vous savez quelque chose sur vos données qui peuvent être exploitées pour améliorer les performances de ce jeu de données particulier. Mais vous n'avez fourni aucune idée de ce qui pourrait rendre vos clés plus faciles à hacher. L'implémentation standard de la bibliothèque doit fonctionner correctement sur un large éventail de données, et si rien ne vous rend la vôtre spéciale, elle fonctionnera aussi bien avec la vôtre. – rici
Être en STL ne veut pas dire que c'est le meilleur. par exemple, la carte de hachage open source de Google et la carte arborescente qui sont souvent meilleures que std. Je ne suis pas sûr de la fonction de hachage. Donc, posé cette question. – SuperBald
Les fonctions std :: hash ont déjà de bonnes performances. Je pense que vous devriez essayer les fonctions de hachage open source.
Cochez cette case https://github.com/Cyan4973/xxHash. Je cite de sa description: "xxHash est un algorithme de Hash Extrêmement Rapide, fonctionnant à des limites de vitesse de RAM, qui complète avec succès la suite de tests SMHasher qui évalue les qualités de collision, de dispersion et de hasard des fonctions de hachage. toutes les plates-formes (petit/grand endian). "
Aussi ce fil d'une autre question sur ce site: Fast Cross-Platform C/C++ Hashing Library. FNV, Jenkins et MurmurHash sont connus pour être rapides.
De manière générale, vous pouvez écrire une fonction de hachage plus rapide si vous savez quelque chose de spécifique sur les données que vous avez hachées. Comme un exemple stupide, si vous ne traitez que deux valeurs entières, 17 et 535, vous pouvez les réduire à 0 et 1 trivialement, et cela sera plus rapide que n'importe quelle fonction de hachage qui traite la gamme complète des valeurs entières. Alors qu'est-ce qui est spécial au sujet des valeurs que vous avez hachées? –
fermer une question si votre problème est résolu est toujours une bonne idée :) –