C语言中两个整数的快速双向散列
C语言中两个整数的快速双向散列
提问于 2012-08-03 06:17:53
我正在编写一个Linux内核模块，我需要想出一个接受两个整数作为输入的散列函数。因为代码是在内核空间中运行的，所以我没有可用的标准库。
基本上，我需要一个散列函数，其中：
hash(a, b) = c
hash(b, a) = c其中a和b的可接受输入是无符号32位整数。哈希函数应返回一个无符号的64位整数。冲突(即，散列(a，b) =c和散列(d，f) =c)也是不希望的，因为这些值将在二进制搜索树中使用。搜索的结果是一个可能结果的链表，然后在实际比较a和b的位置上迭代。因此，一些冲突是可以接受的，但冲突越少，所需的迭代就越少，运行速度也就越快。
性能也非常重要，当我编写防火墙应用程序时，这个查找将用于系统中接收到的每个数据包(整数实际上是数据包源地址和目标地址)。此函数用于查找现有的网络会话。
谢谢您抽时间见我。
回答 5
Stack Overflow用户
回答已采纳
发布于 2012-08-03 06:34:02
你如何做的伪代码：
if a>b
return (a << 32) | b;
else
return (b << 32) | a;这满足hash(a，b) == hash(b，a)，利用完整的64位空间，并且不应该有冲突...I think :)
注意不要直接移位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);
}Stack Overflow用户
发布于 2012-08-03 06:30:55
((a | b) << 32) + (a & b)是可交换的，并且应该导致最小数量的冲突。不过我还得多想一想。
Stack Overflow用户
发布于 2012-08-03 06:37:08
#define MYHASH(a,b) ( (((UINT64) max(a,b)) << 32) | ((UINT64) min(a,b)) )页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11786635
复制相关文章
相似问题
腾讯云开发者
