F# Map.add 的时间和空间复杂度

Question

据我所知，F#中的Map数据类型是不可变的（与数组相反）。这让我产生了一个问题，Map.add函数内部到底做了什么。它是否复制整个结构以保留原始结构（这将非常低效），还是使用了更聪明的策略来确保时间复杂度仍然大致为log n？不幸的是，在Microsoft文档中并没有提到像复杂性这样的重要信息，尽管在某些情况下它很重要。

- Florian Brinkmeyer

Answer 1

F# Map 使用平衡树来实现。在更新时，只有与更新路径相关的节点会被更新，其余节点将会被重用。

顺便提一下，Map 的源代码可以在这里看到：https://github.com/Microsoft/visualfsharp/blob/master/src/fsharp/FSharp.Core/map.fs

- Just another metaprogrammer

Answer 2

"Map.add"内部的操作是什么，你可以通过查看实现来回答这个问题。

总体而言，F#的Map是一种基于自平衡搜索树的持久化数据结构。使用这种类型的结构的一般想法是，在更新时只需要重写结构的一部分 - 而且这部分实际上是从头开始创建的 - 而不改变的子树在“旧”和“更新”的结构版本之间共享。

查找和添加操作的复杂度是O(log n)，平均情况下（就像你从底层树结构中所期望的那样）。

- scrwtp