不可变映射使用哪种数据结构？

Question

我知道普通的可变映射是如何工作的(使用哈希表)，我知道不可变列表是如何工作的(递归链表)，以及它们相对于可变列表的优势(不会弄乱原始的常量时间追加)，但是不可变映射(例如Scala的)是如何工作的呢？

我知道在生成新映射时不干扰原始映射的优势，但是底层数据结构是如何工作的，以及它们具有什么样的性能特征，例如，与可变哈希表相比？有没有人们用来实现这些的标准数据结构，我可以去CLRS/wikipedia上查一下？

Answer 1

持久哈希映射是使用一种称为的结构实现的。这是originally proposed by Phil Bagwell (他是EPFL的Scala小组的成员)，但实际上是由Clojure首先实现的。2010年，当2.8问世时，它冲击了scala。

Dan Spiewak写了一个great talk on functional data structures，其中非常清晰地解释了散列trie的机制(以及银行家队列等其他东西)！他还在谈话中很好地解释了渐近的big-O性能。

去年10月，Phil在London scala Lift Off上做了另一次演讲，这一次是关于并行持久数据结构。

持久排序映射是通过 tree实现的

Answer 2

它可以是树(红-黑)或散列映射。它们的访问特性取决于底层实现。对于读访问，树是O(log )；散列映射是O(1)。