2

我正在用 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。设置掩码时，我应该使用不同的哈希表大小吗？

绝对优先的是速度。

4

1 回答 1

3

顺便说一句，我假设您的意思是 4Gb，而不是 4Mb 的 32 位索引大小。此外，假设每个条目只需要一个字节（最多 255 次命中）

在不知道地址分布的情况下，很难知道哪个散列会更好。如果它们或多或少随机分布在地址空间中（并且，是的，我知道大多数 IPv6 地址都没有分配），只需选择地址的几位并使用它。

例如，为 ipv4 选择五个均匀分布在地址中的 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+长。事实上，读取文件的硬盘驱动器的速度很可能是限制因素。

于 2014-02-27T13:45:09.687 回答