c - c中内存地址的近乎完美或完美散列

Question

我有一个从 0xc0003000 到 0xc04a0144 的内存地址列表，列表中有很多间隙和 < 4096 个条目。它在编译时就知道了，我想为它做一个完美的哈希。

然而，在网上查找完美散列给我的信息主要与散列字符串相关，而且它们似乎翻译得不好。

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

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

Answer 1

这是一个示例 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