20

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

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

还：

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

4

4 回答 4

29

如果没有可变状态，哈希表就无法有效实现，因为它们基于数组查找。键被散列，散列确定了桶数组的索引。在没有可变状态的情况下，将元素插入哈希表会变成 O(n)，因为必须复制整个数组（替代的非复制实现，如 DiffArray，会带来显着的性能损失）。二叉树实现可以共享它们的大部分结构，因此只需要在插入时复制几个指针。

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

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

于 2013-09-20T04:31:55.337 回答
11

传统的哈希表在其实现中依赖于内存突变。可变内存和引用透明性已经结束，因此将哈希表实现降级为 theIO或STmonads。树可以通过将旧叶子留在内存中并返回指向更新树的新根节点来持久有效地实现。这让我们有纯Maps。

典型的参考资料是 Chris Okasaki 的Purely Functional Data Structures。

于 2013-09-20T04:30:15.483 回答
7

为什么是这样？使用二叉树将查找时间减少到 O(log(n)) 而不是 O(1)

查找只是其中一种操作；在许多情况下，插入/修改可能更重要；还有内存方面的考虑。选择树表示的主要原因可能是它更适合纯函数式语言。正如“Real World Haskell”所说：

Maps 为我们提供了与其他语言中的哈希表相同的功能。在内部，映射被实现为平衡二叉树。与哈希表相比，在具有不可变数据的语言中，这是一种更有效的表示形式。这是纯粹函数式编程对我们编写代码的影响程度最明显的例子：我们选择可以清晰表达并高效执行的数据结构和算法，但我们对特定任务的选择通常与命令式语言中的对应物不同。

这个：

并要求元素在 Ord 中。

似乎不是一个很大的缺点。毕竟，使用哈希映射，您需要 key to be Hashable，这似乎更具限制性。

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

不幸的是，我无法提供广泛的比较分析，但是有一个哈希映射包，您可以在这篇博文中查看它的实现细节和性能数据并自行决定。

于 2013-09-20T04:30:54.810 回答
0

我对使用二叉树的优势的回答是：范围查询。从语义上讲，它们需要一个总的预排序，并在算法上从一个平衡的搜索树组织中获利。对于简单的查找，恐怕只有好的 Haskell 特定答案，但本身不是好的答案：查找（实际上是散列）只需要一个 setoid（其键类型的相等/等价），它支持有效的散列指针（出于充分的理由，没有在 Haskell 中排序）。像各种形式的尝试（例如，用于元素更新的三元尝试，其他用于批量更新的尝试）散列到数组（打开或关闭）中通常比在空间和时间上的二叉树中的元素搜索更有效。Hashing 和 Tries 可以通用定义，但必须手动完成——GHC 没有 t 导出它（还没有？）。诸如 Data.Map 之类的数据结构对于原型设计和热点之外的代码往往很好，但在它们很热的地方，它们很容易成为性能瓶颈。幸运的是，Haskell 程序员不需要关心性能，只需要关心他们的经理。（由于某种原因，我目前无法在 80 多个 Data.Map 功能中找到访问搜索树的关键兑换功能的方法：范围查询界面。我找错地方了吗？）在 80 多个 Data.Map 函数中找不到访问搜索树的关键兑换功能的方法：范围查询接口。我是不是找错地方了？）在 80 多个 Data.Map 函数中找不到访问搜索树的关键兑换功能的方法：范围查询接口。我是不是找错地方了？）

于 2013-09-27T11:13:36.610 回答