Super haute performance C/C++ hash map (tableau, dictionnaire)

Question

J'ai besoin de la carte primitive clés (int, peut-être long) struct valeurs dans une haute performance de hachage carte de la structure de données.

Mon programme sera quelques centaines de ces cartes, et chaque carte aura généralement tout au plus quelques milliers d'entrées. Cependant, les cartes seront "rafraîchissant" ou le "barattage" constamment; imaginer le traitement de millions d' add et delete de messages par seconde.

Ce que les bibliothèques en C ou C++ ont une structure de données qui correspond à ce cas d'utilisation? Ou, comment voulez-vous recommandent la construction de votre propre? Merci!

Answer 1

Je vous recommande d'essayer Google SparseHash et voir si cela convient à vos besoins. Ils ont une mémoire efficace la mise en œuvre d'un optimisé pour la vitesse. J'ai fait un test il y a longtemps, c'était la meilleure table de hachage de la mise en œuvre des ressources disponibles en termes de vitesse (mais avec les inconvénients).

Answer 2

Ce que les bibliothèques en C ou C++ ont une structure de données qui correspond à ce cas d'utilisation? Ou, comment voulez-vous recommandent la construction de votre propre? Merci!

Découvrez la LGPL avais Judy tableaux. Jamais utilisé moi-même, mais a été annoncée pour moi à quelques reprises.

Vous pouvez également essayer de référence des conteneurs STL (std::classes hash_map, etc). En fonction de plate-forme/mise en œuvre et le code source de réglage (préallouer autant que vous le pouvez gestion dynamique de la mémoire est cher), ils pourraient être assez performant.

Aussi, si les performances de la solution finale, l'emporte sur le coût de la solution, vous pouvez essayer de commander le système avec suffisamment de RAM pour tout mettre dans la plaine de tableaux. Les performances de l'accès par index est imbattable.

Ajouter/supprimer des opérations sont beaucoup (100x), plus fréquentes que l'opération d'acquisition.

Que les conseils que vous pouvez vous concentrer sur l'amélioration des algorithmes d'abord. Si les données ne sont écrites, de ne pas lire, alors, pourquoi écrire?

Answer 3

Suffit d'utiliser boost::unordered_map (ou tr1 etc) par défaut. Ensuite, le profil de votre code et de voir si ce code est le goulot d'étranglement. C'est alors seulement que je leur propose précisément d'analyser vos besoins afin de trouver un substitut plus rapide.

Answer 4

Si vous avez un programme multithread, vous pouvez trouver quelques bonnes tables de hachage en intel fil blocs de construction de la bibliothèque. Par exemple, tbb::concurrent_unordered_map a la même api que std::unordered_map, mais il a pour principales fonctions sont thread-safe.

Aussi jeter un oeil sur facebook la folie de la bibliothèque, il a la haute performance simultanée de la table de hachage et de sauter de la liste.

Answer 5

à partir d'android sources (donc sous licence Apache 2)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

regardez hashmap.c, choisir d'inclure ou d'cutils/table de hachage.h, si vous n'avez pas besoin de fil de sécurité, vous pouvez supprimer mutex code, un exemple de mise en œuvre est en libcutils/str_parms.c