C中两个整数的快速双向散列

Question

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

基本上,我需要一个散列函数,其中:

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

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

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

感谢您的时间.

Answer 1

关于如何做到的伪代码:

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);
}