不可变映射使用什么样的数据结构？

Question

我知道普通的可变映射表是如何工作的（使用哈希表），我也知道不可变的列表是如何工作的（递归链接列表），以及它们相对于可变列表的优势（在不破坏原始列表的情况下常数时间附加），但是不可变的映射表（例如Scala）是如何工作的？

我知道在生成新映射表时不破坏原始映射表的优点，但底层数据结构是如何工作的，它们有哪些性能特征，例如与可变哈希表相比？人们使用哪种标准数据结构来实现这些数据结构，我可以在CLRS /维基百科上查找吗？

- Li Haoyi

---

CLRS和几乎所有的数据结构/算法教材都严重偏向于可变性和不纯性。Chris Okasaki 确实写了有关函数式数据结构的书籍，这是基于他早期的论文工作并加以扩展。其他你应该查看的作品包括Phil Bagwell和Rich Hickey的作品。 - Jörg W Mittag

Answer 1

持久化哈希映射使用一种名为哈希trie的结构来实现。它最初是由Phil Bagwell（他是EPFL Scala小组的成员）提出的，但实际上是由Clojure首先实现的。它在2.8于2010年推出时进入了Scala。

Dan Spiewak有一个关于函数式数据结构的精彩演讲，其中非常清晰地解释了哈希trie的机制（以及其他东西，如银行家队列）！他还在演讲中很好地解释了渐近大O性能。

去年十月，Phil在伦敦scala Lift Off上再次发表了关于并行持久化数据结构的演讲。

持久化有序映射通过 红黑树 实现。

- oxbow_lakes

---

通常，持久化数据结构依赖于结构共享（例如，持久化cons列表共享它们的尾部）。通常，您可以使用树来实现。如果您了解持久化cons列表的工作原理，那么您已经完成了一半：毕竟，列表只是一个在任何地方只有一个分支的退化树。（或者说，树是列表的一般化，其中每个单元格可以有多个后继。） - Jörg W Mittag

我认为有趣的信息是如何将理解与基于哈希的访问有关联。 - oxbow_lakes

Answer 2

它可以是一棵树（红黑树）或哈希映射。它们的访问特性取决于底层实现。对于读取访问，树的时间复杂度为O(log n)；哈希映射的时间复杂度为O(1)。

- duffymo