当您需要具有最快访问/更新速度的不可变列表时，您会使用什么？如果您必须从中间访问一个元素，LinkedList 可能会很慢，并且禁止创建和重新填充它。二叉树？四叉树？
最佳答案
如果更新非常少(或集合很小)，那么在初始化后不写入的数组是值得的。在这些情况下，较低的常数因子(时间和空间)超过了线性时间更新。
除此之外，还有许多纯函数数据结构可以为这些情况提供更好的界限。 2-3 手指树(Haskell 的 Data.Sequence 背后的数据结构)就是一个例子。另一种选择是 Clojure 的 vector 和相关数据结构(例如 Relaxed Radix-Balanced Trees)，它们使用具有高扇出(32 或更多)的树来保持读取廉价和结构共享以避免太多副本。
尽管手动实现所有这些都有些棘手，尤其是在性能很重要且我不知道现有实现的情况下(我认为 Clojure 的 vector 在 Java 中使用起来并不容易或不方便)。
关于java - 数组的不可变数据结构替换，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19744998/