不可变字典开销？

Question

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

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

即使是这种情况,似乎还有很多需要完成的复制才能创建新的字典(？)

Answer 1

我查看了F#Map<K,V>类型的实现,我认为它是作为一个功能AVL树实现的.它将值存储在树的内部节点以及叶子中,并且对于每个节点,它确保| height(左) - 高度(右)| <= 1.

            A 
         /     \
        B       C
      /   \
     D     E

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

• 插入我们需要克隆从根到新插入元素的路径上的所有节点,并且树的高度最多O(log(n)).在"回来的路上",树可能需要重新平衡每个节点,但这也是唯一的O(log(n))

• 删除是类似的 - 我们找到该元素,然后克隆从根到该元素的所有节点(在返回根目录的路上重新平衡节点)

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