内存地址近完美或完美散列c

我有一个从0xc0003000到0xc04a0144的内存地址列表，列表中有很多空缺和< 4096个条目。它在编译时已知，我想为它做一个完美的散列。内存地址近完美或完美散列c

然而，查找完美的哈希在线给我提供的信息主要与散列字符串有关，而且他们似乎翻译不好。

为了清楚我希望能够在运行时获得内存地址并快速检查它是否在哈希中。目前我正在使用平均约8个循环的二进制搜索来找到答案。

任何想法我应该叫什么树？

来源

2012-07-26 Digital Powers

如何平衡树，像B树或红黑测试？ – Rsh 2012-07-26 20:23:24

你尝试过“bitset”吗？ – jxh 2012-07-26 20:23:59

我认为基数树是稀疏整数值搜索的最佳搜索树。 – 2012-07-26 20:24:50

下面是一个示例gperf程序。我在样本数据中包含了一个NUL和一个换行符，以证明它们不会导致它失败。

%{ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <inttypes.h> 
#include <arpa/inet.h> 
%} 
%% 
"\xc0\x01\x02\x03" 
"\xc0\xff\xff\xff" 
"\xc0\xff\x00\xff" 
"\xc0\x0a\xff\xff" 
%% 
int main(int argc, const char **argv) 
{ 
    int i; 

    for(i=1;i<argc;++i) { 
     uint32_t addr = ntohl(strtoul(argv[i], 0, 16)); 
     if(in_word_set((char *)&addr, 4)) 
      printf("0x%08"PRIx32" is in the list.\n", htonl(addr)); 
     else 
      printf("0x%08"PRIx32" is not in the list.\n", htonl(addr)); 
    } 
    return 0; 
}

另存为addrs.gperf，编译和

gperf -l addrs.gperf > addrs.c 
gcc addrs.c -o addrs 
./addrs c0000000 c0010203 c0ffffff c00affff c0ff0aff c0ffff00 c0ff00ff

来源

2012-07-27 20:31:36

如果gperf实际上是为了这个目的而设计的，它看起来会更干净，并且运行速度更快一些。 – 2012-07-27 20:41:27

这对我所做的工作很好，比二分查找（10,000,000个循环）快大约40％。基数树最终大致等于二进制搜索，但稍微好一些。 – 2012-07-27 21:50:58

内存地址近完美或完美散列c

回答

相关问题