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

我正在写一个Linux内核模块,我需要拿出一个哈希函数,它需要两个整数input。 由于代码在内核空间中运行,所以没有任何标准库可供我使用。

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

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

a和b的可接受input是无符号的32位整数。 散列函数应该返回一个无符号的64位整数。 碰撞(即,散列(a,b)= c和散列(d,f)= c)也是不可取的,因为这些值将用于二叉search树中。 search的结果是一个可能结果的链表,然后在实际比较a和b的地方进行迭代。 所以有些碰撞是可以接受的,但碰撞越less,迭代次数越less,运行速度越快。

性能也是非常重要的,这个查找将用于我写一个防火墙应用程序(整数实际上是数据包源和目标地址)在系统中接收到的每个数据包。 该function用于查找现有的networking会话。

感谢您的时间。

你可以做到的伪代码:

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

这满足散列(a,b)==散列(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); } 
 #define MYHASH(a,b) ( (((UINT64) max(a,b)) << 32) | ((UINT64) min(a,b)) ) 
 ((a | b) << 32) + (a & b) 

是可交换的并且应该导致最小数量的碰撞。 尽管如此,我还是要多想一想

如何((uint64_t)max(a, b) << UINT64_C(32)) | (uint64_t)min(a, b)) ((uint64_t)max(a, b) << UINT64_C(32)) | (uint64_t)min(a, b)) ? 这将完全避免碰撞,因为输入之间不存在可能的重叠。 我不能说分配,因为这取决于你的输入值。

(a ^ b)| ((a ^ b)<< 32);