scala - Scala 不可变索引序列是如何实现的，它们的操作复杂度如何？

Question

我依稀记得在某处读到 Scala 的不可变索引序列操作是 O(log n)，但是对数的底足够大，因此对于所有实际目的，操作几乎就像 O(log n) em>O(1)。是真的吗？

IndexedSeq 是如何实现的？

Answer 1

immutable.IndexedSeq 的默认实现是Vector。这是 relevant documentation 的摘录关于它的实现:

Vectors are represented as trees with a high branching factor (The branching factor of a tree or a graph is the number of children at each node). Every tree node contains up to 32 elements of the vector or contains up to 32 other tree nodes. Vectors with up to 32 elements can be represented in a single node. Vectors with up to 32 * 32 = 1024 elements can be represented with a single indirection. Two hops from the root of the tree to the final element node are sufficient for vectors with up to 2^15 elements, three hops for vectors with 2^20, four hops for vectors with 2^25 elements and five hops for vectors with up to 2^30 elements. So for all vectors of reasonable size, an element selection involves up to 5 primitive array selections. This is what we meant when we wrote that element access is “effectively constant time”.

immutable.HashSet 和 immutable.HashMap 使用类似的技术实现。