Scala - TrieMap 与 Vector
Scala - TrieMap vs Vector
我读到 TrieMap 在 scala 中是基于数组映射的 trie，而 Vector 读取位映射向量 trie。
这两种数据结构是否都由相同的哈希树思想支持，或者它们之间有区别吗？
有一些相似之处，但从根本上说它们是不同的数据结构：
向量
Vector 中不涉及散列。索引直接描述进入树的路径。当然，向量的占用索引是连续的。
忽略 scala.collection.immutable.Vector 的生产实现中显示指针的所有技巧，向量中除最后一个分支节点外的每个分支节点都具有 相同数量的 children（如果是 scala Vector，则为 32）。这允许使用简单的位操作进行索引。缺点是在向量中间拼接元素很昂贵。
HashMap
在 HashTrieMap 中，哈希码是进入树的路径。这意味着占用的索引不是连续的，而是均匀分布的。这需要对树分支节点进行不同的编码。
在一个HashTrieMap中，一个分支节点有最多32children（但是如果你有一个非常糟糕的哈希码分布，它完全是可能只有一个 child) 的分支节点。有一个Int位图要编码哪个child对应哪个位置，这意味着在HashTrieMap中查找值需要频繁调用Integer.bitCount，幸好是一个CPU现代 CPUs.
的固有特征
这是一个有趣的项目，可让您查看 Scala 数据结构的内部结构，例如 Vector 和 HashMap：https://github.com/stanch/reftree
此答案中的图像是使用此项目生成的。
我读到 TrieMap 在 scala 中是基于数组映射的 trie，而 Vector 读取位映射向量 trie。
这两种数据结构是否都由相同的哈希树思想支持，或者它们之间有区别吗？
有一些相似之处，但从根本上说它们是不同的数据结构：
向量
Vector 中不涉及散列。索引直接描述进入树的路径。当然，向量的占用索引是连续的。
忽略 scala.collection.immutable.Vector 的生产实现中显示指针的所有技巧，向量中除最后一个分支节点外的每个分支节点都具有 相同数量的 children（如果是 scala Vector，则为 32）。这允许使用简单的位操作进行索引。缺点是在向量中间拼接元素很昂贵。
HashMap
在 HashTrieMap 中，哈希码是进入树的路径。这意味着占用的索引不是连续的，而是均匀分布的。这需要对树分支节点进行不同的编码。
在一个HashTrieMap中，一个分支节点有最多32children（但是如果你有一个非常糟糕的哈希码分布，它完全是可能只有一个 child) 的分支节点。有一个Int位图要编码哪个child对应哪个位置，这意味着在HashTrieMap中查找值需要频繁调用Integer.bitCount，幸好是一个CPU现代 CPUs.
这是一个有趣的项目，可让您查看 Scala 数据结构的内部结构，例如 Vector 和 HashMap：https://github.com/stanch/reftree
此答案中的图像是使用此项目生成的。