在我有限的Haskell知识中,似乎Maps(来自Data.Map)应该像其他语言中的字典或哈希表一样使用,但实际上它们是实现为自平衡二叉搜索树。
为什么会这样呢?使用二叉搜索树可以将查找时间降为O(log(n)),而不是O(1),并且要求元素在Ord中。肯定存在充分的理由,那么使用二叉搜索树的优势是什么呢?
此外:
在哪些应用中,二叉树比哈希表更差?反之呢?是否存在许多情况其中一个非常优于另一个?Haskell中是否有传统的哈希表?
在我有限的Haskell知识中,似乎Maps(来自Data.Map)应该像其他语言中的字典或哈希表一样使用,但实际上它们是实现为自平衡二叉搜索树。
为什么会这样呢?使用二叉搜索树可以将查找时间降为O(log(n)),而不是O(1),并且要求元素在Ord中。肯定存在充分的理由,那么使用二叉搜索树的优势是什么呢?
此外:
在哪些应用中,二叉树比哈希表更差?反之呢?是否存在许多情况其中一个非常优于另一个?Haskell中是否有传统的哈希表?
哈希表是基于数组查找的,因此没有可变状态就无法高效地实现。关键字被散列并确定其在桶数组中的索引。没有可变状态,将元素插入哈希表的时间复杂度变为O(n),因为必须复制整个数组(像DiffArray这样的替代非复制实现会引入显着的性能损失)。二叉树实现可以共享大部分结构,因此在插入时只需要复制几个指针。
Haskell当然可以支持传统的哈希表,只要更新在适当的单子中。hashtables包可能是最广泛使用的实现。
二叉树和其他非变异结构的一个优点是它们是持久的:可以保留旧数据的副本而不需要额外的记账。例如,在某种事务算法中可能会有用。它们也自动线程安全(尽管更新不会在其他线程中可见)。
Data.HashMap.Lazy
、Data.HashMap.Strict
和Data.HashSet
,它们都在unordered-containers
中。 - Travis BemannData.IntMap
(来自containers
)。 - John LIO
或 ST
monads 中。通过在内存中保留旧叶子并返回指向更新树的新根节点,可以持久且高效地实现树形结构。这样我们就可以拥有纯净的 Map
。查找只是其中一种操作;在许多情况下,插入/修改可能更重要;还有内存方面的考虑。选择树形表示法的主要原因可能是它更适合纯函数语言。正如《Real World Haskell》所述:
Maps给了我们与其他语言中哈希表相同的功能。在内部,map被实现为平衡的二叉树。与哈希表相比,在具有不可变数据的语言中,这是一种更高效的表示方法。这是纯函数编程深刻影响我们编写代码的最明显例子:我们选择可以清晰表达并且性能高效的数据结构和算法,但我们针对特定任务的选择通常与命令式语言中的选择不同。
这个:
并要求元素在Ord中。
似乎不是一个很大的缺点。毕竟,使用哈希图,您需要将键设置为Hashable
,这似乎更加限制。
Ord
更容易,它只需要和Ord
一样容易即可。虽然deriving Hash
今天还不起作用,但可以很容易地添加,方法与派生Ord
和Eq
相同:逐个成员。你甚至不必考虑如何组合成员的哈希值,可以直接重用另一个实现(例如Python元组的实现)。 - user395760Ord
的优势(如标准化、广泛使用、可派生等)只是因为Ord
有其他常见用途(例如排序)和历史偏向(偏向基于顺序的映射)。 - user395760