Scala - TrieMap vs Vector

Question

我读到TrieMap在scala中是基于数组映射trie，比如说读取位映射向量trie。

这两个darastructures是否都支持同一个散列树思想或者它们之间有区别？

Answer 1

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

矢量

没有参与Vector散列。索引直接描述了树中的路径。当然，矢量的占用索引是连续的。

不顾所有在生产实施scala.collection.immutable.Vector显示指针的诡计，在除了在一个水平的最后一项的载体每一个分支节点具有相同数量的儿童（在阶Vector的壳体32） 。这允许使用简单的位操作进行索引。缺点是矢量中间的拼接元素很昂贵。

HashMap的

在HashTrieMap，哈希码是路径到树。这意味着被占领的指数是不是连续的，而是均匀分布的。这需要树分支节点的不同编码。

在HashTrieMap，分支节点高达 32名儿童（但如果你有一个非常不好的哈希码分布是完全可能的，只有一个孩子的分支节点）。有一个Int位图来编码哪个孩子对应哪个位置，这意味着在HashTrieMap中查找值需要频繁调用Integer.bitCount，幸运的是现代CPU上固有的CPU。

这是一个有趣的项目，让你看看Scala的数据结构，如Vector和HashMap的内部：在使用本项目产生https://github.com/stanch/reftree

在这个答案中的图像。