algorithm - 为什么 Haskell Maps 实现为平衡二叉树而不是传统的哈希表？

Question

根据我对 Haskell 的有限了解，Maps(来自 Data.Map)似乎应该像其他语言中的字典或哈希表一样使用，但仍被实现为自平衡二叉搜索树。

这是为什么？使用二叉树将查找时间减少到 O(log(n)) 而不是 O(1)，并且要求元素在 Ord 中。当然是有充分理由的，那么使用二叉树有什么好处呢？

还有:

在哪些应用中二叉树会比哈希表差很多？反过来呢？在很多情况下，其中一个会比另一个更可取吗？ Haskell 中有传统的哈希表吗？

Answer 1

如果没有可变状态，哈希表就无法有效实现，因为它们基于数组查找。 key 被散列，散列确定存储桶数组的索引。在没有可变状态的情况下，将元素插入到哈希表中会变成 O(n)，因为必须复制整个数组(替代的非复制实现，如 DiffArray，introduce a significant performance penalty)。二叉树实现可以共享它们的大部分结构，因此插入时只需要复制几个指针。

Haskell 当然可以支持传统的哈希表，前提是更新在合适的 monad 中。 hashtables package可能是使用最广泛的实现。

二叉树和其他非变异结构的一个优点是它们是持久的:可以保留数据的旧副本而无需额外的簿记。例如，这可能在某种交易算法中很有用。它们也是自动线程安全的(尽管更新在其他线程中不可见)。