我正试图理解HAMT的细节。为了更好地理解，我已经在Java中自己实现了一个。我对Tries很熟悉，我认为我已经理解了HAMT的主要概念。
基本上，HAMT包含两种类型的节点：
键/值
Key Value Node:
K key
V value
索引
Index Node:
int bitmap (32 bits)
Node[] table (max length of 32)
- 为一个对象生成一个32位的哈希值。
- 每次以5位为一组遍历哈希值。
(0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31)注意: 最后一步（第7步）仅有2位。 - 在每一步中，找到该5位整数在位图中的位置。例如：
integer==5 bitmap==00001- 如果该位是1，则该哈希部分存在。
- 如果该位是0，则键不存在。
- 如果键存在，则通过计算位图中从0到该位置的1的数量来找到它在表中的索引。例如：
integer==6 bitmap==0101010101 index==3- 如果表指向一个键/值节点，则比较键。
- 如果表指向一个索引节点，则前进一步并转到步骤2。
我不太明白的部分是冲突检测和解决方法。在相应的论文中，他提到了这个问题：
然后将现有键插入新的子哈希表中，再添加新的键。每使用5个比特的哈希值一次，发生冲突的概率就会减少1/32。偶尔会消耗整个32位哈希，必须计算一个新的哈希来区分两个键。
如果我计算一个“新”的哈希值并将对象存储在那个新的哈希值中，你怎么能在结构中查找这个对象？进行查找时，不是会生成“初始”哈希而不是“重新计算的哈希”吗？
我肯定是漏了什么.....
顺便说一句：在我的测试中，HAMT表现相当不错，它位于哈希映射和树映射之间。
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