f# - 不可变字典开销？

Question

在 F# 中使用不可变字典时，添加/删除条目有多少开销？

是否会将整个存储桶视为不可变的并克隆它们并仅重新创建其项目已更改的存储桶？

即使是这种情况，似乎还需要进行大量复制才能创建新字典(？)

Answer 1

我查看了F#的实现Map<K,V>类型，我认为它被实现为 functional AVL tree .它将值存储在树的内部节点以及叶子节点中，并且对于每个节点，它确保 |height(left) - height(right)| <= 1。

            A 
         /     \
        B       C
      /   \
     D     E

我认为平均和最坏情况的复杂度都是 O(log(n)) :

插入 我们需要克隆从根到新插入元素的路径上的所有节点，树的高度最多为O(log(n)) .在“回来的路上”，树可能需要重新平衡每个节点，但这也只是 O(log(n))

删除 类似 - 我们找到元素，然后将所有节点从根节点克隆到该元素(在返回根节点的途中重新平衡节点)

请注意，在插入/删除时不需要重新平衡从根节点到当前节点的所有节点的其他数据结构在不可变场景中不会真正有用，因为无论如何您都需要为整个路径创建新节点。