草庐IT

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

coder 2023-06-18 原文

我正在编写一个 Linux 内核模块，我需要想出一个以两个整数作为输入的散列函数。因为代码在内核空间中运行，所以我无法使用任何标准库。

基本上，我需要一个哈希函数，其中:

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

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

性能也极其重要，在我编写防火墙应用程序时，系统中接收到的每个数据包都会使用此查找(整数实际上是数据包的源地址和目标地址)。此函数用于查找现有的网络 session 。

感谢您的宝贵时间。

最佳答案

如何实现的伪代码:

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

关于c - C中两个整数的快速双向散列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11786635/

中两个section64uintclinuxmodulekernel

有关c - C中两个整数的快速双向散列的更多相关文章

  1. ruby - 将散列转换为嵌套散列 - 2

    这道题是thisquestion的逆题.给定一个散列，每个键都有一个数组，例如{[:a,:b,:c]=>1,[:a,:b,:d]=>2,[:a,:e]=>3,[:f]=>4,}将其转换为嵌套哈希的最佳方法是什么{:a=>{:b=>{:c=>1,:d=>2},:e=>3,},:f=>4,} 最佳答案 这是一个迭代的解决方案，递归的解决方案留给读者作为练习:defconvert(h={})ret={}h.eachdo|k,v|node=retk[0..-2].each{|x|node[x]||={};node=node[x]}node[

  2. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  3. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  4. ruby - 按值降序排列散列，然后按升序键入 ruby - 2

    我有这样的哈希trial_hash={"key1"=>1000,"key2"=>34,"key3"=>500,"key4"=>500,"key5"=>500,"key6"=>500}我按值降序排列:my_hash=trial_hash.sort_by{|k,v|v}.reverse我现在是这样理解的:[["key1",1000],["key4",500],["key5",500],["key6",500],["key3",500],["key2",34]]但我希望当值相同时按键的升序排序。我该怎么做？例如:上面的散列将以这种方式排序:[["key1",1000],["key3",500

  5. ruby - 这两个 Ruby 类初始化定义有什么区别？ - 2

    我正在阅读一本关于Ruby的书，作者在编写类初始化定义时使用的形式与他在本书前几节中使用的形式略有不同。它看起来像这样:classTicketattr_accessor:venue,:datedefinitialize(venue,date)self.venue=venueself.date=dateendend在本书的前几节中，它的定义如下:classTicketattr_accessor:venue,:datedefinitialize(venue,date)@venue=venue@date=dateendend在第一个示例中使用setter方法与在第二个示例中使用实例变量之间是

  6. ruby-on-rails - 使用 ruby​​ 将多个实例变量转换为散列的更好方法？ - 2

    我收到格式为的回复#我需要将其转换为哈希值(针对活跃商家)。目前我正在遍历变量并执行此操作:response.instance_variables.eachdo|r|my_hash.merge!(r.to_s.delete("@").intern=>response.instance_eval(r.to_s.delete("@")))end这有效，它将生成{:first="charlie",:last=>"kelly"},但它似乎有点hacky和不稳定。有更好的方法吗？编辑:我刚刚意识到我可以使用instance_variable_get作为该等式的第二部分，但这仍然是主要问题。

  7. ruby - 在 Ruby 中将整数格式化为固定长度的字符串 - 2

    有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的

  8. ruby - 具有两个参数的 block - 2

    我从用户Hirolau那里找到了这段代码:defsum_to_n?(a,n)a.combination(2).find{|x,y|x+y==n}enda=[1,2,3,4,5]sum_to_n?(a,9)#=>[4,5]sum_to_n?(a,11)#=>nil我如何知道何时可以将两个参数发送到预定义方法(如find)？我不清楚，因为有时它不起作用。这是重新定义的东西吗？ 最佳答案 如果您查看Enumerable#find的文档，您会发现它只接受一个block参数。您可以将它发送两次的原因是因为Ruby可以方便地让您根据它的“并行赋

  9. ruby - 如何根据长度将路径数组转换为嵌套数组或散列 - 2

    我需要根据字符串路径的长度将字符串路径数组转换为符号、哈希和数组的数组给定以下数组:array=["info","services","about/company","about/history/part1","about/history/part2"]我想生成以下输出，对不同级别进行分组，根据级别的结构混合使用符号和对象。产生以下输出:[:info,:services,about:[:company,history:[:part1,:part2]]]#altsyntax[:info,:services,{:about=>[:company,{:history=>[:part1,:pa

  10. Ruby:如何使用带有散列的 'send' 方法调用方法？ - 2

    假设我有一个类A，里面有一些方法。假设stringmethodName是这些方法之一，我已经知道我想给它什么参数。它们在散列中{'param1'=>value1,'param2'=>value2}所以我有:params={'param1'=>value1,'param2'=>value2}a=A.new()a.send(methodName,value1,value2)#callmethodnamewithbothparams我希望能够通过传递我的哈希以某种方式调用该方法。这可能吗？ 最佳答案 确保methodName是一个符号，而

随机推荐