最快类型哈希映射

Question

的我需要散列〜从它们的2^12上的低端的空间采样15000个无符号整数，以在高端多达2^32。我还需要存储索引进行反向查找。一个简单的例子使用C++ STL是：

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

在密集的情况下，我们可以认为这是：

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

现在的问题。速度是最重要的因素在这里，但我的“M仍然在内存方面的限制。我需要在内存中存储和访问这些地图的1000年在一个低延迟应用率很高。查询应该是顺序纳秒数

我目前使用密集方法存储数据，但是我想增加需要哈希的密钥的范围为2^32，这使得密集方法存在问题。只需要在地图上存储~15000个密钥

从好的一面来看，一旦地图建好了，我再也不会插入任何东西了，以后我只会查询它，插入仍然需要相当快，但不是作为查询的关键。

一些代码，我已经试验过的：

谷歌SparseHash
谷歌DenseHash
STL unordered_map
STL地图

我不介意写我自己的哈希表。我想在得到一些专家建议之前自己解决它。

Answer 1

平均GET操作应该是下1ms的范围从具有1024个条目（349KB在存储器中），以用于888ns条目27,648（6MB在存储器中）189ns。 27K条目的最大延迟时间为44,000ns。但是，如果平均时间对您来说很重要，而且不是经常出现高延迟，那么这可能基本上就是您想要的。我认为它可以进一步优化，但不确定要取得的收益。

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"); 
} 

可以使用任何::哈希::初始化（& HT，4），但是这增加了延迟的内存使用量减少到900KB左右每15000项。