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

Question

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

algorithmhaskelldata-structureshashtablebinary-search-tree

20

在我有限的Haskell知识中，似乎Maps（来自Data.Map）应该像其他语言中的字典或哈希表一样使用，但实际上它们是实现为自平衡二叉搜索树。

为什么会这样呢？使用二叉搜索树可以将查找时间降为O(log(n))，而不是O(1)，并且要求元素在Ord中。肯定存在充分的理由，那么使用二叉搜索树的优势是什么呢？

此外：

在哪些应用中，二叉树比哈希表更差？反之呢？是否存在许多情况其中一个非常优于另一个？Haskell中是否有传统的哈希表？

- reem

1

顺便提一下，虽然传统哈希表存在答案中描述的问题，但是有一些持久化数据结构在精神上类似并且提供类似的时间复杂度：哈希数组映射树，在Clojure等语言中使用。 - user395760

与O(1)相反，仅在平均情况下。哈希表查找在最坏情况下是O(n)。 - newacct

只有在没有开放地址法实现的哈希表中才会出现这种情况。在开放地址法中，导致O(n)查找时间的最坏情况是如此罕见，以至于几乎不值得考虑。 - reem

@newacct 对于布谷鸟哈希，查找的最坏情况时间复杂度为O(1)。 - user395760

@delnan：当然，对于这个问题，插入排序的最坏时间复杂度很糟糕。 - newacct

@newacct 是的，但对于许多应用程序来说，这就是所需的全部。同样，当插入性能更重要时，链接法给出了最坏情况下的O(1)时间复杂度。我的观点是，您正在忽略涵盖几乎任何一组边界的不同哈希表变体的动物园。我已经向您指出了动态完美哈希。我不知道它在实践中的表现如何，但渐近复杂度很好：最坏情况下的O(1)查找、插入和删除（对于后两者进行摊销，但在BST中也有许多优秀的边界，包括前驱和后继操作）。 - user395760

4个回答

11

传统的哈希表实现依赖于内存突变。可变内存和引用透明度是相互对立的，因此将哈希表实现限制在 IO 或 ST monads 中。通过在内存中保留旧叶子并返回指向更新树的新根节点，可以持久且高效地实现树形结构。这样我们就可以拥有纯净的 Map。

经典的参考书是 Chris Okasaki 的 Purely Functional Data Structures。

- J. Abrahamson

7

为什么会这样？使用二叉树将查找时间从O(1)降低到O(log(n))。

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

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

这个：

并要求元素在Ord中。

似乎不是一个很大的缺点。毕竟，使用哈希图，您需要将键设置为Hashable，这似乎更加限制。

在哪些应用程序中，二叉树比哈希表更糟糕？反过来呢？有很多情况下，一个比另一个更好吗？Haskell 中是否有传统的哈希表？

不幸的是，我无法提供详尽的比较分析，但有一个哈希映射包hash map package，您可以查看其实现细节和性能数据this blog post，并自行决定。

- fjarri

这些理由似乎相当薄弱。无论是在内存使用还是插入性能方面，树都不比哈希表优越，无论是一般情况还是在这种特定情况下都是如此。而且我怀疑可哈希性比可排序性更具限制性 - 在大多数情况下，您只需组合成员的哈希值而不是链接成员的比较。 - user395760

“在内存使用或插入性能方面，树并不比哈希表更优越”——RWH的观点是，在纯函数式语言中实现时，它们确实如此。“而且我怀疑可哈希性比可排序性更具限制性”——“Ord”由编译器自动派生，这再简单不过了。 - fjarri

正则表达式性能：在纯函数式实现中是的，但只是因为那种实现很愚蠢。如果你第一段的意思是插入必须复制底层数组，那就说清楚。正则表达式易用性：它不必比Ord更容易，它只需要和Ord一样容易即可。虽然deriving Hash今天还不起作用，但可以很容易地添加，方法与派生Ord和Eq相同：逐个成员。你甚至不必考虑如何组合成员的哈希值，可以直接重用另一个实现(例如Python元组的实现)。 - user395760

RE性能：我说的是John L所描述的：一个纯函数哈希表必须复制整个表，因此修改是线性时间。您提到的数据结构不是纯函数，它使用可变状态。RE内存占用：您是说哈希表比树占用更多空间吗？BST每个条目至少需要两个额外的字（子指针），哈希表可以达到0个字（开放寻址，100％负载因子），但通常需要一到两个字（取决于负载因子和哈希值是否被缓存）。 - user395760

关于Ord：我并不是说现在哈希化更容易了。我是说，从原则上讲，它同样普遍，换句话说，任何Ord的优势（如标准化、广泛使用、可派生等）只是因为Ord有其他常见用途（例如排序）和历史偏向（偏向基于顺序的映射）。 - user395760

显示剩余4条评论

0

使用二叉树的优势是什么？我的回答是：范围查询。从语义上讲，它们需要一个完全的前序，并且从平衡搜索树组织算法中获益。对于简单的查找，恐怕可能只有好的Haskell特定答案，但并非好的答案本身：查找（以及哈希）仅需要一个集合（其键类型上的相等/等价性），它支持指针的高效哈希（出于良好的原因，在Haskell中不排序）。像各种形式的tries（例如用于元素更新的三进制tries，用于批量更新的其他tries）一样，哈希到数组（开放或封闭）通常比在二叉树中逐个搜索更加高效，无论是空间还是时间上。哈希和Tries可以被定义为通用的，虽然这必须手动完成-- GHC没有推导它（但？）。像Data.Map这样的数据结构 tend to be fine for prototyping and for code outside of hotspots，但是当它们处于热点时，它们很容易成为性能瓶颈。幸运的是，Haskell程序员不必担心性能，只需关注他们的经理。（由于某种原因，我目前找不到搜索树的80多个Data.Map函数中的关键救赎特性的访问方式：范围查询接口。我是在看错地方吗？）

- Fritz Henglein

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John L · Accepted Answer

哈希表是基于数组查找的，因此没有可变状态就无法高效地实现。关键字被散列并确定其在桶数组中的索引。没有可变状态，将元素插入哈希表的时间复杂度变为O(n)，因为必须复制整个数组（像DiffArray这样的替代非复制实现会引入显着的性能损失）。二叉树实现可以共享大部分结构，因此在插入时只需要复制几个指针。

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

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