0

我需要散列从低端 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;

现在解决问题。速度是这里最重要的因素，但我在内存方面仍然受到限制。我需要将 1000 个这些映射存储在内存中，并在低延迟应用程序中以高速率访问。查询应该是有序的纳秒。

我目前使用密集方法存储数据。但是，我想将需要散列到 2^32 的键的范围增加，这使得密集方法有问题。请记住，我只需要在地图中存储约 15000 个键。

从好的方面来说，一旦地图建成，我就再也不会在里面插入任何东西了。我只会在以后查询它。插入仍然需要相当快，但不如查询那么关键。

我尝试过的一些代码是：

Google SparseHash
Google DenseHash
STL unordered_map
STL 映射

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

4

1 回答 1

0

平均 GET 操作应该在 1 毫秒以下，从 189ns 到 1024 个条目（内存中 349KB）到 888ns 到 27,648 个条目（6MB 在内存中）。具有 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");
}

您可以使用anything::hash::init(&ht, 4) 将内存使用量减少到每15000 个条目大约900kb，但这会增加延迟。

于 2013-11-24T19:00:12.267 回答