草庐IT

java - 哈希数组映射树 (HAMT)

coder 2023-05-17 原文

我正在努力了解 HAMT 的详细信息.我会有 implemented one myself in Java只是为了理解。我对 Tries 很熟悉，我想我掌握了 HAMT 的主要概念。

基本上，

两种类型的节点:

键/值

Key Value Node:
  K key
  V value

索引

Index Node:
  int bitmap (32 bits)
  Node[] table (max length of 32)
  1. 为对象生成 32 位哈希。
  2. 一次遍历 5 位哈希。 (0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31) 注意:最后一步(第 7 步)只有 2 位。
  3. 在每一步中，找到该 5 位整数在位图中的位置。例如整数==5 位图==00001
    1. 如果该位为 1，则该部分哈希存在。
    2. 如果该位为 0，则 key 不存在。
  4. 如果键存在，则通过计算位图中 0 和位置之间的 1 的数量来找到它在表中的索引。例如整数==6 位图==0101010101 索引==3
    1. 如果表指向键/值节点，则比较键。
    2. 如果表指向一个 inode ，则向前一步执行 2。

我不太了解的部分是碰撞检测和缓解。在链接的论文中，他提到了这一点:

The existing key is then inserted in the new sub-hash table and the new key added. Each time 5 more bits of the hash are used the probability of a collision reduces by a factor of 1/32. Occasionally an entire 32 bit hash may be consumed and a new one must be computed to differentiate the two keys.

如果我要计算一个"new"哈希并将对象存储在该新哈希中；你怎么能在结构中查找对象？在进行查找时，它不会生成“初始”哈希而不是“重新计算的哈希”吗？

我一定是错过了什么.....

顺便说一句:HAMT 的性能相当不错，在我的测试中它位于 HashMap 和 TreeMap 之间。

Data Structure                    Add time   Remove time     Sorted add time Sorted remove time   Lookup time     Size     
Java's Hash Map                   38.67 ms   18 ms           30 ms           15 ms                16.33 ms        8.19 MB        
HAMT                              68.67 ms   30 ms           57.33 ms        35.33 ms             33 ms           10.18 MB       
Java's Tree Map                   86.33 ms   78 ms           75 ms           39.33 ms             76 ms           8.79 MB        
Java's Skip List Map              111.33 ms  106 ms          72 ms           41 ms                72.33 ms        9.19 MB

最佳答案

HAMT 是一种出色且高性能的结构，尤其是在需要不可变对象(immutable对象)时，即每次修改后都会创建一个数据结构的新副本!

至于你关于哈希冲突的问题，我找到了一个 C# implementation (现在是错误的)显示了它是如何工作的:在每次哈希冲突时，都会重新哈希键并递归重试查找，直到达到最大迭代限制。

目前我还在函数式编程环境中探索 HAMP 并学习现有代码。 Haskell as Data.HshMap 中有几个 HAMT 的引用实现在 Clojure as PersistenceHashMap .

网络上还有一些其他更简单的实现不处理冲突，但它们有助于理解这个概念。他们在Haskell和 OCaml

我找到了 nice summary article article用图片和原始链接描述 HAMT research papers作者:菲尔·巴格威尔。

相关点:

在 F# 中实现 HAMT 时，我注意到 popCount 函数实现描述了 here与链接中下一个答案中描述的幼稚实现相比，确实很重要，并且提供了 10-15%。不是很好，但免费午餐。

相关的 IntMap 结构(Haskell 及其 port to F#)在键可以是整数并且它们实现相关的 PATRICIA/Radix 时非常好。 trie .

我相信所有这些实现都非常适合在这些示例中学习高效的不可变数据结构和函数式语言 - 它们真的很相配!

关于java - 哈希数组映射树 (HAMT)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19714795/

javaHAMTnoreferrernoopenernofollowalgorithmdata-structureshashtrie

有关java - 哈希数组映射树 (HAMT)的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  3. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  4. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  5. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  6. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  7. 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

  8. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

  9. 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"=>

  10. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

随机推荐