我读到 scala 中的 TrieMap
是基于数组映射的 trie,而 Vector
读取位映射向量 trie。
这两种数据结构是否都由相同的哈希树思想支持,或者它们之间是否存在差异?
最佳答案
有一些相似之处,但从根本上说它们是不同的数据结构:
矢量
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
此答案中的图像是使用此项目生成的。
关于Scala - TrieMap 与 Vector,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37185648/