Scala中VectorMap的工作原理是什么？与ListMap有何区别？

• 你猜测的结构完全正确：VectorMap 是典型的「双存储结构」不可变集合，底层由两部分组成：
  1. 按插入顺序存储所有键值对条目的不可变Vector
  2. 负责将键映射到对应条目在Vector中下标的不可变哈希表
• 查找操作的常数时间复杂度来源：
  查找时先通过哈希表获取键对应下标，这个操作平均时间复杂度为O(1)；再通过下标直接访问Vector中的条目，而Vector的下标访问本身就是有效常数时间复杂度，两者结合后整体查找符合官方标注的常数时间要求。
• 和ListMap的核心差异：
  ListMap底层是纯链表结构，没有额外的索引层，查找任意键都需要从链表头开始逐节点比对，时间复杂度稳定为O(n)，自然和带哈希索引的VectorMap有本质性能差距。
• 额外补充：
  作为不可变集合，VectorMap的增/删操作会同时生成新的Vector和新的哈希表，两个底层结构都支持高效的结构共享，所以修改操作开销也很低，同时还能完美保留插入顺序，遍历的时候直接迭代Vector即可，解决了普通不可变HashMap遍历顺序不固定的问题。

注意：这里的常数时间是平均复杂度，极端哈希冲突场景下会出现性能退化，但工程场景下发生概率极低。

内容的提问来源于stack exchange，提问作者Thomas