哈希数组映射三重奏 （HAMT）

我正试图了解HAMT的细节。我自己在Java中实现了一个，只是为了理解。我熟悉Trys，我想我了解HAMT的主要概念。

基本上

两种类型的节点：

键/值

Key Value Node:
  K key
  V value

指数

Index Node:
  int bitmap (32 bits)
  Node[] table (max length of 32)

1. 为对象生成 32 位哈希。
2. 一次单步执行 5 位哈希。 注意：最后一步（第7步）只有2位。(0-4, 5-9, 10-14, 15-19, 20-24, 25-29, 30-31)
3. 在每个步骤中，查找该 5 位整数在位图中的位置。例如：integer==5 bitmap==00001
   1. 如果位是 1，则哈希的该部分存在。
   2. 如果位为 0，则不存在键。
4. 如果该键存在，则通过计算位图中介于 0 和位置之间的 1 的数目来查找表中的索引。例如：integer==6 bitmap==0101010101 index==3
   1. 如果表指向键/值节点，则比较键。
   2. 如果表指向索引节点，请转到 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