la recherche de la table de hachage de la bibliothèque C

Je n'ai vérifier les questions précédentes sur ce sujet, mais ne pouvais pas trouver une solution qui répond à mon besoin.

Ce dont j'ai besoin:

  1. Prend en charge les deux chaînes, et les n-uplets d'entiers (int tableaux en C). Si c'est un tableau d'entiers, la longueur est fixée au moment de la compilation.
  2. Rapide.
  3. Efficace en terme de mémoire. J'ai besoin de l'utiliser pour traiter les super grands ensembles de données.
  4. La capacité des tables de hachage se développer de manière dynamique. J'aime la croissance de la taille des tables de hachage pour être traitées par la bibliothèque, au lieu de moi.
  5. J'ai besoin de créer un grand nombre de tables de hachage. Et ces tables de hachage sera lié comme un arbre, que les valeurs dans une table de hachage point à d'autres tables de hachage.

Mon application est à la fois mémoire et en CPU. -- Comment je suis chanceux! 🙂

Je ne considère pas du tout C++ implémentations pour l'instant, à moins que je n'arrivais pas à trouver la moindre solution en C.

Merci!

Le plus important de la mise en œuvre de choix: avez-vous besoin d'supprime, ou est la table de hachage en magasin seulement? BTW: le redimensionnement automatique peut être un frein, pourrait conduire à Nlog(N) ou même N*N de comportement. La taille idéale est le chemin à parcourir. My application is both memory and CPU bound. : qui est presque impossible, dans mon hash-programmes intensifs (comme Wakkerbot, voir mon profil) le hachage généralement tendance à utiliser uniquement les quelques % de CPU et de peut-être 90% de la mémoire disponible. Et près de 100% de la bande passante de la mémoire, puisque j'aime séparé de chaînage...
Grâce wildplasser pour les suggestions. Il est lié à la mémoire, parce que j'ai besoin de traiter de grands ensembles de données. Il est en CPU, parce que les maths dans l'application est à coût élevé, non pas à cause de la table de hachage.
Il semble que ce soit un doublon: stackoverflow.com/questions/1138742/...

OriginalL'auteur Jian Feng | 2013-08-12

  1. 13

    Ce sujet uthash - une table de hachage pour les structures C.

    • Prend en charge les deux chaînes de caractères, entier et les tuples

    uthash n'a pas de restriction contre touches: clés et la structure peut avoir tout type de données.

    Il inclut les macros par défaut de hachage commune des types de clés, à savoir entiers et des chaînes de caractères. En outre, il fournit des macros génériques (HASH_ADD et HASH_FIND) à l'appui de tout type de données.

    • Rapide

    Il semble pour être:

    Ajouter, rechercher et supprimer sont normalement constante de temps des opérations. [...] Ce hachage vise à être minimaliste et efficace. C'est autour de 900 lignes de C.

    • Mémoire efficace

    Plus de détails ici:

    Le hachage de la poignée consomme environ 32 octets par élément sur un système 32 bits ou 56 octets par élément sur un système 64 bits. Les autres frais généraux-- les seaux et la table-- sont négligeables en comparaison.

    • La capacité des tables de hachage se développer de manière dynamique

    Il est pris en charge out-of-the-box:

    Seau d'expansion se produit automatiquement et de manière invisible, en tant que de besoin. Il n'est pas nécessaire pour l'application de savoir quand cela se produit.

    Grâce deltheil. J'aime cette uthash chose, après j'ai lu un peu dans le lien. Je vais essayer celui-là en premier.
    uthash dirait qu'il pourrait en être assez lourd augmentation de code de taille, certaines macros sont beaucoup de code.

    OriginalL'auteur deltheil

  2. 1

    Blender (les graphismes en 3D de l'application) a son propre hachage bibliothèque appelée BLI_ghash, il a quelques fonctionnalités bien utiles.

    Tout pas écrit comme une bibliothèque autonome, il n'est pas difficile à extraire, mais il peut être utile comme une référence. (note ses sous licence GPL2).

    • Utilise un pool de mémoire pour les éléments.
    • Seaux sont développés selon les besoins (automatiquement).
    • Chaque élément prend 3 points (12 ou 24 octets par élément).
    • Les fonctions de l'utilitaire pour le hachage des chaînes, les pointeurs, les ints ou peut éventuellement prendre comparer & hash rappels.
    • Expose un itérateur (faire une boucle sur tous les éléments de la ghash).
    • Expose également une BLI_gset API, basée sur BLI_ghash mais évite de stocker une valeur de pointeur.

    D'autres ajouts:

    • Pouvez réserver une taille pour éviter le redimensionnement des seaux lorsque la taille est connue à l'avance.
    • Peut calculer la qualité de la fonction de hachage (à utiliser pour tester la façon dont uniformément distribué les seaux sont).

    La seule chose qu'il ne fait pas tout à fait aussi bien qu'il le pourrait, à partir de votre description est d'allouer beaucoup de cartes, puisque chacun devient son propre pool de mémoire, mais theres pas une grosse limites que vous arrêter de partager un mempool, il n'a tout simplement pas sortir de la boîte.

    Code Source:
    BLI_ghash.c, BLI_ghash.h
    BLI_mempool.c, BLI_mempool.h

    Notes, MEM_mallocN/MEM_freeN fonctions peuvent être remplacés par des malloc/free

    OriginalL'auteur ideasman42