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

Question

我正在努力了解 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     

Answer 1

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 .

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