高效的Haskell哈希结构。

Question

高效的Haskell哈希结构。

61

我正在编写一个需要进行许多表查找的程序。因此，当我浏览 Haskell 文档时，我偶然发现了 Data.Map（当然），还有 Data.HashMap 和 Data.Hashtable。我不是哈希算法方面的专家，在检查过这些包后发现它们看起来非常相似。因此，我想知道：

1：主要区别是什么，如果有的话？

2：在大量查询约为 4000 个键值对的映射/表时，哪种方法具有最好的性能？

- providence

4

你可能也会对这篇博客文章感兴趣。它展示了许多有趣的数字，并比较了Haskell中哈希表的不同方法。文章最终得出结论，为了使哈希表正常工作并快速，需要使用不纯性（impurity）。 - fuz

35

在SO上的人们通常能够提供你自己无法发现的见解。例如，库的作者或熟悉该库的人可能会偶然发现这个问题，并解释一些模糊的配置选项或调整方法。此外，某人可能会推荐第四个选项"SuperHashMap"。最后，将来处于我当前位置的其他人可以看到这个问题并从中学习。 - providence

4

一般情况下，不要使用模块名称来标识代码。在Haskell的世界中，模块名称会发生冲突。例如，当你说“Data.HashMap”时，我猜你是在谈论“hashmap”包，但它的性能比我建议你使用的“unordered-containers” HashMap实现要差。 - Thomas M. DuBuisson

@FUZxxl 谢谢你提供的链接。结合 @mergeconflict 的回答，我决定尝试在 hashtables 包中实现 cuckoo。同时感谢 @ThomasM.DuBuisson，我还是 Haskell 的新手，需要像这样的技巧！ - providence

@ThomasM.DuBuisson 并不是说unordered-containers在所有情况下都比hashmap更快。在我的特定应用程序中，我使用前者的HashMap和后者的HashSet以获得最佳性能。 - augustss

3个回答

14

Data.Map 和 Data.HashMap 明显的区别在于前者需要使用 Ord 排序的键，而后者需要使用 Hashable 哈希的键。大部分常用的键都满足这两个条件，所以这并不是决定性的标准。我没有任何关于 Data.HashTable 的经验，所以无法对此发表评论。 Data.HashMap 和 Data.Map 的 API 非常相似，但是 Data.Map 导出了更多的函数，例如 alter 在 Data.HashMap 中不存在，其他一些函数提供了严格和非严格的变体，而 Data.HashMap（我假设你指的是 unordered-containers 中的哈希表）则在单独的模块中提供了惰性和严格的 API。如果你只使用共同的 API 部分，切换是非常容易的。

就性能而言，unordered-containers 的 Data.HashMap 具有非常快速的查找功能，最后一次我的测量结果显示，它明显比 Data.IntMap 或 Data.Map 要快得多，特别是对于尚未发布的 unordered-containers 中的 HAMT 分支。我认为在插入方面，它和 Data.IntMap 大致相当，在某种程度上比 Data.Map 快一些，但我对此有点模糊。

两者在大多数任务中都足够高效，对于它们无法胜任的任务，你可能需要一个定制化的解决方案。考虑到你特别询问的是查找，我会选择 Data.HashMap。

- Daniel Fischer

请确保你正在谈论相同的 Data.Hashmap。在我上次检查时，Unordered-containers 比其他包的 HashMap 实现要快得多。 - Thomas M. DuBuisson

好的观点。我完全忘记了之前有一个 Data.HashMap。 - Daniel Fischer

在2015年，base中不再有Data.HashMap。但是在hashtables包中有一个。 - sinelaw

3

Data.HashTable的文档现在说：“使用hashtables包”。这里有一篇很好的博客文章，解释了为什么hashtables是一个好的包，请点击这里。它使用ST monad。

- gatoatigrado

“hashtables”包使用的是ST单子而不是State单子。 - is7s

正确的，ST只是State的变换器（即有用）版本。 - gatoatigrado

11

不是这样的。这两者有着巨大的概念差异。ST单子在类型层面上携带状态，而State单子在值层面上携带状态 :) - is7s

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

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

- mergeconflict · Accepted Answer

1: 主要区别是什么？

Data.Map.Map 内部使用平衡二叉树实现, 因此其查找的时间复杂度为 O(log n)。我认为它是一种“持久化”数据结构，意味着它的可变操作会产生一个新副本，并且只更新结构的相关部分。
Data.HashMap.Map 内部使用 Data.IntMap.IntMap 实现，它又以 Patricia 树作为实现方式；它的查找时间复杂度为 O(min(n, W))，其中 W 是整数位数。它也是“持久化”的。新版本（>=0.2）使用哈希数组映射字典。根据文档：“许多操作的平均时间复杂度为 O(log n)。实现使用了大的基数（比如16），因此在实践中这些操作是常数时间。”
Data.HashTable.HashTable 是一个真正的哈希表，查找的时间复杂度为 O(1)。但是，它是一个可变数据结构——操作是就地完成的——因此如果您想使用它，必须用 IO Monad。

2: 对于大约4000个键值对的映射/表进行高频查找，哪一个性能最好？

我能给你的最好答案是“要看情况”。如果您按照渐近复杂度去考虑，你会得到 O(log 4000) = 约12 的结果，使用 Data.Map；O(min(4000, 64)) = 64 的结果，使用 Data.HashMap；以及 O(1) = 1 的结果，使用 Data.HashTable。但实际上并不完全这样...需要在代码的上下文中尝试它们。