哈希数组映射Trie

Question

我正试图让我的头脑围绕着一个哈姆特的细节。我会用Java自己实现一个，只是为了理解。我熟悉尝试，我想我得到了HAMT的主要概念。

基本上，

两种类型的节点：

Key Value Node:
  K key
  V value

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

null

null

我不太明白的部分是碰撞检测和缓解。在链接的论文中，他暗示了这一点：

然后将现有键插入到新的子哈希表中，并添加新键。每使用5个以上的散列比特，冲突的概率就减少1/32倍。偶尔，可能会消耗整个32位哈希，必须计算一个新的哈希来对两个密钥进行加密。

如果我要计算一个“新的”散列，并将对象存储在新的散列中；您如何能够在结构中查找对象？在进行查找时，它是否会生成“初始”哈希而不是“重新计算的哈希”。

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

我想你可能漏掉了这篇论文的两个部分。第一个是紧靠您引用的位之前的位：

否则密钥将与现有密钥冲突。在这种情况下，必须用子哈希表替换现有密钥，并计算现有密钥的下一个5位哈希。如果仍然存在碰撞，则重复此过程，直到没有碰撞发生。

因此，如果表中有对象A，并添加冲突的对象B，它们键冲突的单元格将是指向另一个子表（它们不冲突的地方）的指针。

接下来，您链接的论文的第3.7节描述了在运行前32位的末尾时生成新哈希的方法：

哈希函数被定制为提供32位哈希。该算法要求散列可以扩展到任意位数。这是通过将键与表示trie级别的整数重新组合来实现的，零是根。因此，如果两个键确实给出了相同的初始哈希，那么重新哈希的概率为2^32中的1。