scala - Scala Vector 中的结构共享

Question

Scala 中的结构共享 List简单易懂。但是 Scala Vector是比列表更复杂的数据结构。 Scala 中如何实现结构共享Vector ?

Answer 1

Vector 基本上是一棵树(trie)，每一层都有 32 个宽的分支。例如，如果您有一个包含 3000 个元素的 Vector 并且您想要索引元素 2045，例如，它会转换为 100000010101在二进制中，它会将其分解为 5 位块以用作树的索引:10 (即 2)在第一个分支然后 00000 (即 0)在下一个，最后是 10101 (即 21)在终端分支中，然后是数据。

鉴于这种结构，很容易看出如何在结构上共享事物:您可以共享任何未更改的子树。因此，如果您使用不同的元素 2045 创建一个新向量，则不必更改所有 3000 个元素，而是“仅”重新创建三个大小为 32 的数组:终端一个被替换为更新其元素 21 的副本；那么它的父级必须被一个在索引 0 中具有这个新子级的副本替换；那么它的父级必须用索引 2 中的正确子树替换。

现在，只要向量中的元素超过 32 个，这就提供了相当多的结构共享，但这仍然是一个相当大的开销。因此，向量末尾的添加是特殊情况，因此您只需添加到现有数组。旧的 Vectors 仍然指向那个数组，但他们认为结束更早(并且那部分没有改变)所以它可以正常工作。

有一个更复杂但类似的方案，允许以类似的方式在向量的前面添加(基本上，通过在前面留下空间并通过索引和偏移量跟踪指向的位置以及索引方案)。

但是，实现的技巧并不能允许在前后交替添加，因此每次添加都可以有效地重建树。制作一个具有更好结构共享的版本是可能的，但访问速度可能会慢一些。