我正在编写一个Linux内核模块,我需要想出一个接受两个整数作为输入的散列函数。因为代码是在内核空间中运行的,所以我没有可用的标准库。
基本上,我需要一个散列函数,其中:
hash(a, b) = c
hash(b, a) = c其中a和b的可接受输入是无符号32位整数。哈希函数应返回一个无符号的64位整数。冲突(即,散列(a,b) =c和散列(d,f) =c)也是不希望的,因为这些值将在二进制搜索树中使用。搜索的结果是一个可能结果的链表,然后在实际比较a和b的位置上迭代。因此,一些冲突是可以接受的,但冲突越少,所需的迭代就越少,运行速度也就越快。
性能也非常重要,当我编写防火墙应用程序时,这个查找将用于系统中接收到的每个数据包(整数实际上是数据包源地址和目标地址)。此函数用于查找现有的网络会话。
谢谢您抽时间见我。
发布于 2012-08-03 06:30:55
((a | b) << 32) + (a & b)是可交换的,并且应该导致最小数量的冲突。不过我还得多想一想。
https://stackoverflow.com/questions/11786635
复制相似问题