最快類型哈希映射

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項。