haskell - 插入新绑定时是否复制了整个地图？

Question

我想更好地了解例如Data.Map 的实习生。当我在 Map 中插入一个新绑定时，由于数据的不变性，我得到一个与旧数据结构相同的新数据结构加上新绑定。

我想了解这是如何实现的。编译器最终是否通过复制整个数据结构来实现这一点，例如数百万个绑定？通常可以说可变数据结构/数组（例如 Data.Judy）或命令式编程语言在这种情况下表现更好吗？在字典/键值存储方面，不可变数据有什么优势吗？

Answer 1

Map建立在树数据结构之上。基本上，构造了一个新值Map，但它几乎完全由指向旧结构的指针填充。由于 Haskell 中的值永远不会改变，因此这是一种安全且非常重要的优化，称为共享。

这意味着您可以拥有相同数据结构的许多相似版本，但只有不同的树的分支会被重新存储；其余的只是指向分支原始副本的指针。当然，如果你扔掉旧的，Map你改变的分支将被垃圾收集器回收。

共享是不可变数据结构性能的关键。您可能会发现这篇 Wikipedia 文章很有帮助；它有一些启发性的图表，显示了修改后的数据如何通过共享来表示。

Answer 2

不。文档Data.Map.insert说明插入需要O(log n)时间。如果它必须复制整个结构，就不可能满足这个界限。

Answer 3

Data.Map 不复制旧地图；它（懒惰地）分配 O(log N) 个新节点，这些节点指向（并因此共享）大部分旧地图。

因为“更新”地图不会破坏旧版本，所以这种数据结构在构建并发算法时为您提供了更大的自由。