草庐IT

c++ - knuth 乘法哈希

coder 2024-02-12 原文

这是 Knuth 乘法哈希的正确实现吗。

int hash(int v)
{
    v *= 2654435761;
    return v >> 32;
}

乘法溢出会影响算法吗？

如何提高该方法的性能？

最佳答案

Knuth 乘法哈希用于根据整数 k 计算 {0, 1, 2, ..., 2^p - 1} 中的哈希值。

假设p在0到32之间，算法是这样的:

  • 将 alpha 计算为最接近 2^32 (-1 + sqrt(5))/2 的整数。我们得到 alpha = 2 654 435 769。

  • 计算 k * alpha 并将结果对 2^32 求模:

    k * alpha = n0 * 2^32 + n1 其中 0 <= n1=""><>

  • 保留n1的最高p位:

    n1 = m1 * 2^(32-p) + m2 其中 0 <= m2="">< 2^(32="" -="">

因此，Knuth 乘法算法在 C++ 中的正确实现是:

std::uint32_t knuth(int x, int p) {
    assert(p >= 0 && p <= 32);

    const std::uint32_t knuth = 2654435769;
    const std::uint32_t y = x;
    return (y * knuth) >> (32 - p);
}

忘记将结果移动 (32 - p) 是一个重大错误。因为您将失去哈希的所有良好属性。它会将偶数序列转换为偶数序列，这将非常糟糕，因为所有奇数槽都将保持空闲状态。这就像拿一瓶好酒和可乐混合。顺便说一句，网络上到处都是错误引用 Knuth 并使用 2 654 435 761 的乘法而不取高位的人。我刚打开 Knuth，他从来没有说过这样的话。看起来有些自认为“聪明”的人决定取一个接近 2 654 435 769 的质数。

请记住，大多数哈希表实现不允许在其接口(interface)中使用这种签名，因为它们只允许

uint32_t hash(int x);

并减少 hash(x) 模 2^p 以计算 x 的哈希值。这些哈希表不能接受 Knuth 乘法哈希。这可能是为什么这么多人忘记采用更高的 p 位而完全破坏算法的原因。 因此，您不能将 Knuth 乘法哈希与 std::unordered_map 或 std::unordered_set 一起使用。但我认为那些哈希表使用素数作为大小，因此 Knuth 乘法哈希在这种情况下没有用。使用 hash(x) = x 将非常适合这些表。

来源:“Introduction to Algorithms, third edition”，Cormen 等人，13.3.2 p:263

资料来源:“计算机编程艺术，第 3 卷，排序和搜索”，D.E.高德纳，6.4 p:516

关于c++ - knuth 乘法哈希，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11871245/

ampknuthcodesectionc++algorithmhash

有关c++ - knuth 乘法哈希的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  3. ruby - 如何在 Grape 中定义哈希数组？ - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

  4. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  5. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  6. ruby - 在 Ruby 中创建按公共(public)键值分组的新哈希 - 2

    假设我有一个在Ruby中看起来像这样的哈希:{:ie0=>"Hi",:ex0=>"Hey",:eg0=>"Howdy",:ie1=>"Hello",:ex1=>"Greetings",:eg1=>"Goodday"}有什么好的方法可以将它变成如下内容:{"0"=>{"ie"=>"Hi","ex"=>"Hey","eg"=>"Howdy"},"1"=>{"ie"=>"Hello","ex"=>"Greetings","eg"=>"Goodday"}} 最佳答案 您要求一个好的方法来做到这一点，所以答案是:一种您或同事可以在六个月后理解

  7. ruby - ruby 乘法语句中星号中断语法前的空格 - 2

    在添加一些空格以使代码更具可读性时(与上面的代码对齐)，我遇到了这个:classCdefx42endendm=C.new现在这将给出“错误数量的参数”:m.x*m.x这将给出“语法错误，意外的tSTAR，期待$end”:2/m.x*m.x这里的解析器到底发生了什么？我使用Ruby1.9.2和2.1.5进行了测试。 最佳答案 *用于运算符(42*42)和参数解包(myfun*[42,42])。当你这样做时:m.x*m.x2/m.x*m.xRuby将此解释为参数解包，而不是*运算符(即乘法)。如果您不熟悉它，参数解包(有时也称为“spl

  8. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  9. ruby-on-rails - 使用作为方法的值在 ruby​​ 中搜索哈希 - 2

    我在搜索我的值是方法的散列时遇到问题。我只是不想运行plan_type与键匹配的方法。defmethod(plan_type,plan,user){foo:plan_is_foo(plan,user),bar:plan_is_bar(plan,user),waa:plan_is_waa(plan,user),har:plan_is_har(user)}[plan_type]end目前如果我传入“bar”作为plan_type，所有方法都会运行，我怎么能只运行plan_is_bar方法呢？ 最佳答案 这个变体怎么样？defmethod

  10. 键删除后 ruby​​ 哈希内存泄漏 - 2

    你好，我无法成功如何在散列中删除key后释放内存。当我从哈希中删除键时，内存不会释放，也不会在手动调用GC.start后释放。当从Hash中删除键并且这些对象在某处泄漏时，这是预期的行为还是GC不释放内存？如何在Ruby中删除Hash中的键并在内存中取消分配它？例子:irb(main):001:0>`ps-orss=-p#{Process.pid}`.to_i=>4748irb(main):002:0>a={}=>{}irb(main):003:0>1000000.times{|i|a[i]="test#{i}"}=>1000000irb(main):004:0>`ps-orss=-p

随机推荐