Scala - TrieMap与矢量

Question

我TrieMap在scala中读到了基于数组映射的trie,同时Vector读取位映射向量trie.

这两种结构都是由哈希特里的相同想法支持还是它们之间存在差异？

Answer 1

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

向量

没有涉及散列Vector.索引直接描述了进入树的路径.当然,矢量的占用指数是连续的.

忽略生产实现中显示指针的所有技巧,scala.collection.immutable.Vector除了最后一个级别的向量中的每个分支节点具有相同数量的子节点(在scala的情况下为32 Vector).这允许使用简单的位操作进行索引.缺点是矢量中间的拼接元素很昂贵.

HashMap中

在HashTrieMap中,哈希码是树的路径.这意味着占用的指数不是连续的,而是均匀分布的.这需要树分支节点的不同编码.

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

这是一个有趣的项目,让您看斯卡拉数据结构的内部,例如Vector和HashMap:https://github.com/stanch/reftree

这个答案中的图像是使用这个项目生成的.