声明： 本文主要内容编译自 Nick M 的英文技术分享 《Grokking Hash Array Mapped Tries (HAMTs)》。
笔者在译介的基础上，修正了原作中关于哈希冲突处理的逻辑细节，并观察了 Erlang 源码分析出 Erlang 虚拟机对 HAMT 的实际工业级优化策略。

这是一种结合了哈希表和 Tries（字典树）优势的数据结构，用于高效地存储和检索键值对。

在 HAMT 里面，Keys 都被 hash 了来确认在 Array 的位置，被称之为 hash array。为了确保高效的内存利用，如果多个 Key 在同一个 index 上冲突了，那么 trie-like（类字典树）的结构就是用来解决这种冲突的。

用个例子来解释 HAMT 怎么运作：

假设我们有一个 HAMT 来存一些单词和单词对应的定义。我们用一个简单的哈希表说明，它只有四个 Slots 来存 Value，和只用 2 个 bits 来代表 index。

我们存下面这几个键值对：

  • "apple" -> "a fruit"
  • "banana" -> "a tropical fruit"
  • "cat" -> "a small animal"

现在我们的 HAMT 还是空的：

根表 (Root Table)
+------+------+------+------+
| [00] | [01] | [10] | [11] |
+------+------+------+------+
|  空  |  空  |  空  |  空  |
+------+------+------+------+

我们开始插入第一个键值对 "apple" -> "a fruit"，"apple" 这个 Key 被哈希之后，在哈希表中的下标位置就是确定的。我们假设 "apple" 的哈希值是 32bits，但是我们只用前两个 bits 来找到在这个 Hash 表中正确的下标位置。在这个例子里面，我们假设这两个 bits 就是 01。我们一看这个下标在上面的哈希表中还是空的，于是直接存进去这个位置。

根表 (Root Table)
+------+-----------------------+------+------+
| [00] | [01]                  | [10] | [11] |
+------+-----------------------+------+------+
|  空  | "apple" -> "a fruit"  |  空  |  空  |
+------+-----------------------+------+------+

接下来我们来插入 "banana" -> "a tropical fruit"。

我们故技重施，hash 一下这个 Key，相应的 index 就能找到了。我们假设计算出来这个 Key 的哈希值是以 10 开始的，这个 10 在上面的哈希表内的位置依旧是空的，所以也是直接插入。

根表 (Root Table)
+------+-----------------------+-----------------------------+------+
| [00] | [01]                  | [10]                        | [11] |
+------+-----------------------+-----------------------------+------+
|  空  | "apple" -> "a fruit"  | "banana" -> "a trop. fruit" |  空  |
+------+-----------------------+-----------------------------+------+

最后我们来插入 "cat" -> "a small animal"。哈希一下这个 Key，确定其 index。我们假设 "cat" 的哈希值的头两位又变成了 01。哦，这个位置我们之前放入过 "apple"，发生了冲突！

正常来说，当一个传统的哈希表变满时，我们需要分配一个更大、更多的哈希表，然后重新计算并搬迁所有旧的值（re-hash），这是一个又慢又昂贵（expensive）的过程。

所以我们有没有能避免这种不得不执行 resize 操作的方法？

哈哈，HAMTs 就是来搞这个的。

与其去执行一个 resize 我们的表，不如我们直接分配一个新的子哈希表（也是只有 4 个空 Slots），我们用这个新哈希表链接到我们发生冲突的 Slots（01）位置。

这里有一个非常关键的步骤：原本在第一层 01 槽位上的 "apple" 不能继续留在原地了（因为该槽位现在要变成一个指向新子表的指针）。我们需要把原有的 "apple" 和新来的 "cat" 一起向下推（Push Down），重新分配到第二层的新哈希表里。

根表 (Root Table)
+------+--------+-----------------------------+------+
| [00] | [01]   | [10]                        | [11] |
+------+--+-----+-----------------------------+------+
|  空  |  |     | "banana" -> "a trop. fruit" |  空  |
+------+--v-----+-----------------------------+------+
          |
          v
     [指向子表的指针]
          |
          v
     子表 (Sub-Table)
     +------+------+------+------+
     | [00] | [01] | [10] | [11] |
     +------+------+------+------+
     |  空  |  空  |  空  |  空  |
     +------+------+------+------+

现在我们要把 "apple" 和 "cat" 安置在第二个表里面，但是我们需要更多的 bits 去定位它们。这种情况下，我们引入下一组 bits（第 3 和第 4 个 bits）来确定它们在第二层表的位置：

  • 我们假设 "apple" 的前 4 位哈希值是 01 00。头两位 01 帮我们找到了第一层的槽位，下两位 00 则决定了它在第二层子表中的下标为 00。
  • 我们假设 "cat" 的前 4 位哈希值是 01 10。头两位 01 帮我们找到了第一层的槽位，下两位 10 则决定了它在第二层子表中的下标为 10。
根表 (Root Table)
+------+--------+-----------------------------+------+
| [00] | [01]   | [10]                        | [11] |
+------+--+-----+-----------------------------+------+
|  空  |  |     | "banana" -> "a trop. fruit" |  空  |
+------+--v-----+-----------------------------+------+
          |
          +-------------------------+
                                    |
                                    v
                               子表 (Sub-Table)
                               +-----------------------+------+---------------------------+------+
                               | [00]                  | [01] | [10]                      | [11] |
                               +-----------------------+------+---------------------------+------+
                               | "apple" -> "a fruit"  |  空  | "cat" -> "a small animal" |  空  |
                               +-----------------------+------+---------------------------+------+

看，通过这种“向下推”和“子表局部挂载”的方法论，我们完美避免了全局的 re-hashing。如果我们继续这样搞，我们就能增加尽可能多的 values，而且不用重新分配整张大表的内存。

当我们需要查找一个值时，只需要简单地根据哈希值一路找下去。我们先看最低的两位，在根表（Root Table）寻找：

  • 如果对应位置是空，说明值不存在；
  • 如果对应位置是一个直接的值，且 Key 对上了，就直接返回；
  • 如果对应位置是一个指针（指向子表），我们就继续提取哈希值的下两位，去第二层子表里找，以此类推。

工业界是如何处理的？以 Erlang 为例

在实际的工业级编程语言实现中，比如 Erlang 的虚拟机（BEAM），对 HAMT 的处理更加极致和聪明，解决了很多现实中的性能和内存痛点：

  • 大 Map 与小 Map 的双重策略（Flatmap vs Hashmap）：
    在 Erlang 中，并不是所有的 Map 一上来就会用 HAMT。如果键值对数量很少（通常少于 32 个），Erlang 会使用一种非常简单、扁平的数组结构（称为 flatmap），因为在小数据量下，直接遍历数组比遍历树还要快。只有当元素数量超过 32 个时，它才无缝“升级”为真正的 HAMT（在源码中称为 hashmap）。
  • 用 Bitmap（位图）消灭空槽，节省内存：
    在我们上面的简化例子中，第二层表虽然只存了 2 个值，却分配了 4 个空槽。如果树很深，会浪费大量的内存。Erlang 的 HAMT 节点通常是 16 叉的（每次看 4 个 bits）。为了不浪费这 16 个槽位，Erlang 内部使用了一个 **16 位的无符号整数（Bitmap）**来标记哪些位置是有值的。物理上，它只为有值的槽位分配连续的内存，再通过极快的位运算（如 popcount 指令）计算出元素在物理内存中的实际偏移量。
  • 终极哈希冲突的兜底：
    万一遇到极罕见的“完全哈希冲突”（即两个不同的 Key，它们的 32 位或 64 位哈希值完全一样），再怎么向下建树也分不开了。Erlang 在源码中对此做了兜底：它会在树的最底部创建一个特殊的冲突节点（Collision Node），其内部退化成一个简单的链表，用来安全地容纳这些具有相同哈希值的不同 Key。

总结

通过这种方式，HAMTs 高效地用类 trie 的数据结构处理了哈希冲突，本质上这是一种结合了二进制搜索和哈希表、但是没有它们那么麻烦的东西。

在二进制搜索树中，我们每次插入新元素时，为了使搜索路径更有逻辑和高效，不得不进行复杂的旋转去重新平衡（Rebalance）。而在 HAMT 里面，元素的位置通过哈希值决定，分布更加随机，根本不需要专门去使其平衡。

至于哈希表，我们已经提及过当表太大了的时候需要重新分配更多内存和 re-hash 的问题了。HAMT 不会变得很 "full"，因为本质上这是一棵树，我们需要分配新的值只需要往上面挂子节点就行了。

HAMT 被频繁用于函数式编程语言，比如 Clojure、Scala 以及 Erlang，用来实现持久化数据结构比如 maps 和 sets。HAMT 在确保不可变性（Immutability）时提供了高效的查询、插入和删除操作。它们也很适合多线程或者多进程去同时访问和修改共享数据结构这种并发情况。这种结构性的共享特征允许高效地复制共享数据，减少了昂贵的锁机制需要。

相关链接：

Grokking Hash Array Mapped Tries (HAMTs) - by Nick M

https://github.com/erlang/otp/blob/master/erts/emulator/beam/erl_map.c