c - IPv4/6 地址的快速哈希函数

Question

我正在用 C 编写程序，它设计得很快。

我想存储数据流中IP地址出现的次数。例如，我将分析 100MB 的二进制文件，其中包含大约 2 000 000 个 IP 地址(但程序可能也会用于 x-GB 文件)。

我的想法是使用哈希表，所以我需要这些哈希函数:

20b_int indexToIPv4HashTable = hashIPv4(32b_int addr4);
20b_int indexToIPv6HashTable = hashIPv6(128b_int addr6);

我认为当这个函数有时会发生冲突时这不是问题(我将使用单独的链接来解决这个问题)。

• 我应该使用哪些哈希函数？
• 使用哈希表来解决这个问题是个好主意吗？

小数学:

• 20b 索引 = 1 048 576 个元素(够吗？)
• 32b 元素 = 4B 元素 = 4MB 表大小(当程序运行在 有电脑吗？)

注意: IP 地址可能已指定掩码。例如:IPv4/24 --> 现在只有 2^24 个不同的 IPv4 地址，而不是 2^32 个。 设置掩码后，我应该使用不同的哈希表大小吗？

绝对优先考虑的是速度。

Answer 1

顺便说一句，我假设您指的是 4Gb，而不是上面 32 位索引大小的 4Mb。另外，假设每个条目只需要一个字节(最多 255 次点击)

在不知道地址分布的情况下，很难知道哪个哈希值更好。如果它们或多或少随机分布在地址空间上(是的，我知道大多数 IPv6 地址都没有分配)，只需选择地址的一些位并使用它即可。

例如，对于 ipv4，在地址中选择均匀分布的 5 个 4 位区域，对于 v6，从中间某处选择最低 16 位 + 4 位。

但是如果您在现代 x86 上使用 crc32 指令几乎肯定会产生足够好的哈希值，而且速度很快。

#define HASH_MASK ((1<<20)-1)

static inline int hash32( unsigned int foo )
{
  return __builtin_ia32_crc32si( 0, foo ) & HASH_MASK;
}

static inline int hash128( const char *data )
{
  int res = 0, i;
  for( i=0; i<4; i++, data+=4 )
    res = __builtin_ia32_crc32si( res, *(int32_t *)data ); 
  return res & HASH_MASK;
}

请注意，这是非常不可移植的，它不仅只能在 x86 上运行，而且只能在某些 x86 机器上运行(如果您使用 gcc，它还需要 -msse4.2)。

注意一点:除非您每秒处理大量条目(我的意思是很多)，否则哈希函数的速度不太重要。 散列桶中数据的传播可能会产生影响，但即使是链表桶散列表的简单的非调整大小实现也能够每秒处理至少数亿次点击，除非链接达到 100 以上长的。 事实上，读取文件的硬盘驱动器的速度很可能是限制因素。