7

我正在编写一个 Linux 内核模块，我需要提出一个哈希函数，它需要两个整数作为输入。因为代码在内核空间中运行，所以没有一个标准库可供我使用。

基本上，我需要一个散列函数，其中：

hash(a, b) = c
hash(b, a) = c

其中 a 和 b 可接受的输入是无符号 32 位整数。散列函数应该返回一个无符号的 64 位整数。冲突（即 hash(a, b) = c 和 hash(d, f) = c）是不可取的，因为这些值将用于二叉搜索树。搜索的结果是可能结果的链接列表，然后在实际比较 a 和 b 的位置进行迭代。所以一些碰撞是可以接受的，但碰撞越少，需要的迭代越少，运行速度就越快。

性能也非常重要，当我编写防火墙应用程序时，此查找将用于系统中收到的每个数据包（整数实际上是数据包源和目标地址）。该函数用于查找现有的网络会话。

感谢您的时间。

4

5 回答 5

6

如何做到这一点的伪代码：

if a>b
  return (a << 32) | b;
else 
  return (b << 32) | a;

这满足 hash(a,b) == hash(b,a)，利用完整的 64 位空间，并且不应该有冲突......我认为 :)

注意不要直接移位 32 位变量。改用中间 64 位缓冲区或内联强制转换：

uint64_t myhash(uint32_t a, uint32_t b)
{
    uint64 a64 = (uint64_t) a;
    uint64 b64 = (uint64_t) b;
    return (a > b) ? ((a64 << 32) | b64) : ((b64 << 32) | a64);
}
于 2012-08-02T22:34:02.077 回答
3 
((a | b) << 32) + (a & b)

是可交换的并且应该导致最小数量的冲突。不过，我必须多考虑一下……

于 2012-08-02T22:30:54.653 回答
3 
#define MYHASH(a,b) ( (((UINT64) max(a,b)) << 32) | ((UINT64) min(a,b)) )
于 2012-08-02T22:37:07.743 回答
1

怎么样((uint64_t)max(a, b) << UINT64_C(32)) | (uint64_t)min(a, b))？这将完全避免冲突，因为输入之间没有可能的重叠。不过，我不能谈论分布，因为这取决于您的输入值。

于 2012-08-02T22:40:02.447 回答
1

（一^二）| ((a ^ ~b) <<32);

于 2012-08-02T22:40:57.260 回答