C语言 哈希函数对ip分片进行哈希

Question

我必须将传入的ipv4片段散列到大小为20的静态结构数组中。用于散列的字段有:IP- id(16位)、Protocol(8位)、Source IP Address(32位)和Destination IP Address(32位)。哈希应该是快速的，在c中实现起来不是很复杂。在这种情况下，一个好的哈希函数是什么?

Answer 1

如果我理解正确，你只想要20个可能的哈希值，你可以直接对你的数据使用模算子(%)。

如果您的数据分布是有利的，并且您将它们存储为整数，则可以使用hash = ip_fragment % 20。

似乎无论如何都会发生很多碰撞，所以你可以保持简单。

Answer 2

如果您可以假设所有参数都不相关且分布均匀，那么您可以将您感兴趣的字段的所有字节加在一起，最后对结果取20的模。然而，如果你有双向流，这意味着两个方向都被散列到相同的值(因为交换字段在这个简单的算法中并不重要)。你应该看看快速的通用散列算法，比如MurmurHash。

但是，如果哈希表中只有20个条目，那么很可能会发生冲突。如果收到的数据包之间在时间上有很强的相关性，例如，您很可能在一行中收到许多具有相同头的数据包，那么您最好只使用一个(或几个)缓存条目，仅记录最后一个(唯一的)接收的头，然后您立即将下一个数据包与这些缓存条目进行比较，而不做任何散列。

不要忘记测量您正在使用的散列或缓存方法的实际性能。

Answer 3

% 20确实是次优的。像这样的简单散列:

uint_32_t ip_fragment_hash(uint16_t ip_id, uint8_t ip_proto, uint32_t ip_src, uint32_t ip_dst)
{
  return (ip_id << 16 | ip_proto) ^ ip_src ^ ip_dst;
}

是5个amd64指令(shift, mov, xor, xor, or, xor)。但加上% 20，你得到14条指令，包括一个扩展乘法。把它设为32，然后折叠:

uint32_t ip_fragment_hash(uint16_t ip_id, uint8_t ip_proto, uint32_t ip_src, uint32_t ip_dst)
{
  uint32_t h = (ip_id << 16 | ip_proto) ^ ip_src ^ ip_dst;
  h = h ^ (h >> 5) ^ (h >> 10) ^ (h >> 15)  ^ (h >> 20) ^ (h >> 25) ^ (h >> 30);
  return h % 32;
}