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

Question

据我所知,F#中的Map-datatype是不可变的(与数组相反).这就引出了一个问题,即Map.add函数在内部的确切作用.它是否复制整个结构以使原始结构保持不变(这将是非常低效的),还是使用更聪明的策略来确保时间复杂度仍然大致为log？不幸的是,在Microsoft文档中,虽然在某些情况下很重要,但根本没有提到复杂性之类的东西.

Answer 1

F#Map使用引擎盖下的排序平衡树.在更新期间,仅更新更新路径中涉及的节点.其余的重复使用.

仅供参考Map源代码:https://github.com/Microsoft/visualfsharp/blob/master/src/fsharp/FSharp.Core/map.fs

Answer 2

" Map.add内部是什么"的问题是您可以通过查看实现来自己回答的问题.

通常,F#Map是基于自平衡搜索树的持久数据结构.使用这种结构背后的一般思想是,在更新时只需要重写部分结构 - 而且该部分实际上是从头开始创建的 - 而不改变的子树在"旧"和"旧"之间共享更新了"结构的版本.

查找和添加操作的复杂性是O(log n),平均情况(正如您对底层树结构所期望的那样).