Le type le plus rapide de la table de hachage

Question

J'ai besoin de hachages ~ 15000 entiers non signés qui sont échantillonnés à partir de l'espace de 2^12 sur le bas, jusqu'à 2^32 sur le haut de gamme. J'ai également besoin de stocker l'index pour une recherche inversée. Un exemple naïf en utilisant STL C++ serait:

std::map<unsigned int, std::set<unsigned int /* unique indices */> > m; 

Dans le cas dense, on pourrait penser à cela comme:

std::vector<std::set<unsigned int /* unique indices */> > v; 

Maintenant le problème. La vitesse est le facteur le plus important ici, mais je suis encore limité en termes de mémoire: je vais devoir stocker 1000 de ces cartes en mémoire et accéder à un débit élevé dans une application à faible latence. Je stocke actuellement les données en utilisant la méthode dense, mais je voudrais augmenter la gamme de clés qui doivent être hachées à 2^32 ce qui rend la méthode dense problématique. Sur le plan positif, une fois la carte créée, je n'y insèrerai plus rien, je ne l'interrogerai que plus tard, les insertions doivent toujours être assez rapides. , mais pas aussi critique que la requête

Une partie du code que j'ai expérimenté sont:

Google sparsehash
Google DenseHash
STL unordered_map
STL carte

Je ne me dérange pas d'écrire ma propre table de hachage. Je voulais obtenir des conseils d'experts avant de m'y attaquer moi-même.

Answer 1

L'opération GET moyenne doit être inférieure à 1 ms, de 189ns avec 1024 entrées (349 Ko en mémoire) à 888ns pour 27 648 entrées (6 Mo en mémoire). La latence maximale sur une entrée avec 27k entrées est de 44 000ns. Mais, si le temps moyen est ce qui compte pour vous et pas un temps de latence élevé, c'est peut-être ce que vous voulez. Je pense qu'il peut être optimisé davantage, mais pas sûr des gains à réaliser.

typedef unsigned int uintptr; 
typedef unsigned int uint32; 
typedef unsigned short uint16; 
typedef unsigned char uint8; 


namespace anything { namespace linklist { 
typedef struct _HDR { 
    void    *next; 
    void    *prev; 
} HDR; 

void *next(void *ptr) { 
    if (ptr == 0) { 
     return 0; 
    } 
    return ((void**)ptr)[0]; 
} 

void add(void **chain, void *toadd) { 
    ((void**)toadd)[0] = *chain; 
    ((void**)toadd)[1] = 0;   /* set previous */ 

    /* set previous link if valid pointer */ 
    if (*chain) 
     ((void**)*chain)[1] = toadd; 

    *chain = toadd; 
} 
}} 

namespace anything{ namespace hash { 
    typedef struct _B { 
     MASS_LL_HDR llhdr; 
     uint32   id; 
     union { 
     struct _B *chain; 
     uintptr  value; 
     }; 
    } B; 

    typedef struct _HT { 
     B  *buckets; 
     uint16 depth; 
     uint8 bbl; 
    } HT; 

    void init(HT *ht, uint8 bbl) { 
     ht->buckets = 0; 
     ht->bbl = bbl; 
    } 

    void _free(B **chain, uint16 dcnt, uint16 dcntmax, uint32 *_m) { 
     B  *ba, *_ba; 

     for (ba = *chain, _ba = 0; ba; ba = _ba) { 
     _ba = (B*)mass_ll_next(ba); 

     if (dcnt < dcntmax - 1) { 
      _free(&ba->chain, dcnt + 1, dcntmax, _m); 
      *_m = *_m + 1; 
      dfree(ba); 
     } 
     } 

     /* zero the chain out */ 
     *chain = 0; 
    } 

    void free(HT *ht) { 
     uint32  m; 
     uint16  dm; 

     dm = (sizeof(uintptr) * 8)/ht->bbl; 
     m = 0; 

     _free(&ht->buckets, 0, dm, &m); 
    } 

    int get(HT *ht, uintptr k, uintptr *v) { 
     uintptr  a; 
     B    *ba, **cur; 

     uint16   bi, lcnt; 
     uint32   mask; 

     lcnt = (sizeof(uintptr) * 8)/ht->bbl; 

     cur = &ht->buckets; 

     mask = ~(~0 << ht->bbl); 

     for (bi = 0; bi < lcnt; ++bi) { 

     a = (k >> (bi * ht->bbl)) & mask; 

     for (ba = *cur; ba; ba = (B*)mass_ll_next(ba)) { 
      if (ba->id == a) { 
       break; 
      } 
     } 

     if (!ba) { 
      return 0; 
     } 

     cur = &ba->chain; 
     } 

     *v = ba->value; 
     return 1; 
    } 

    void put(HT *ht, uintptr k, uintptr v) { 
     uintptr  a; 
     B    *ba, **cur; 

     uint16   bi, lcnt; 
     uint32   mask; 

     lcnt = (sizeof(uintptr) * 8)/ht->bbl; 

     cur = &ht->buckets; 

     mask = ~(~0 << ht->bbl); 

     for (bi = 0; bi < lcnt; ++bi) { 

     a = (k >> (bi * ht->bbl)) & mask; 

     for (ba = *cur; ba; ba = (B*)mass_ll_next(ba)) { 
      if (ba->id == a) { 
       break; 
      } 
     } 

     if (!ba) { 
      ba = (B*)dmalloc(sizeof(B)); 
      ba->id = a; 
      ba->chain = 0; 
      mass_ll_add((void**)cur, ba); 
     } 

     cur = &ba->chain; 
     } 

     ba->value = v; 
    } 
}} 

anything::hash::HT  ht; 
anything::hash::init(&ht, 1); 
anything::hash::put(&ht, key, value); 
if (!anything::hash::get(&ht, key, &value) { 
    printf("not found!\n"); 
} 

Vous pouvez réduire l'utilisation de la mémoire à environ 900kb par 15000 entrées en utilisant tout :: hachage :: init (& ht, 4), mais cela augmente le temps d'attente.