Scala - TrieMap 与 Vector

Question

我读到 scala 中的 TrieMap 是基于数组映射的 trie，而 Vector 读取位映射向量 trie。

这两种数据结构是否都由相同的哈希树思想支持，或者它们之间是否存在差异？

Answer 1

有一些相似之处，但从根本上说它们是不同的数据结构:

矢量

Vector 中不涉及散列。索引直接描述进入树的路径。当然，向量的占用索引是连续的。

忽略 scala.collection.immutable.Vector 的生产实现中显示指针的所有技巧，向量中的每个分支节点都具有 相同数量的 child (在 scala Vector 的情况下为 32)。这允许使用简单的位操作进行索引。缺点是在向量中间拼接元素代价高昂。

哈希表

在 HashTrieMap 中，哈希码是进入树的路径。这意味着占用的索引不是连续的，而是均匀分布的。这需要对树分支节点进行不同的编码。

在 HashTrieMap 中，一个分支节点有最多 32 个 child (但是如果你有一个非常糟糕的散列码分布，那么完全有可能有一个分支节点只有一个 child )。有一个 Int 位图来编码哪个 child 对应哪个位置，这意味着在 HashTrieMap 中查找值需要频繁调用 Integer.bitCount ，幸运的是，它是现代 CPU 固有的 CPU。

这是一个有趣的项目，可让您查看 Vector 和 HashMap 等 Scala 数据结构的内部结构:https://github.com/stanch/reftree

此答案中的图像是使用此项目生成的。