性能Haskell散列结构。
我正在写程序，做了很多表查找。 就这样，当我偶然发现Data.Map （当然），还有Data.HashMap和Data.Hashtable时，我正在Data.Map Haskell文档。 我不是散列algorithm方面的专家，在检查包之后，他们看起来都非常相似。 因此我想知道：
1：如果有什么重大区别？
2：在大约4000个键值对的地图/表上，查找量最大的是哪一个？
1：如果有什么主要区别？
-
Data.Map.Map在内部是一个平衡的二叉树，所以查找的时间复杂度是O（log n）。 我相信这是一个“ 持久的 ”数据结构，这意味着它的实现使得变化操作产生一个新的副本，只更新结构的相关部分。 -
Data.HashMap.Map在内部是一个Data.IntMap.IntMap，它又被实现为Patricia树; 其查找的时间复杂度为O（min（n，W）），其中W是整数中的位数。 它也是“持久的”。 -
Data.HashTable.HashTable是一个实际的哈希表，其查询的时间复杂度为O（1）。 然而，这是一个可变的数据结构 – 操作是在原地完成的 – 所以如果你想使用它，你就被困在IOmonad中。
2：在大约4000个键值对的地图/表上，查找量最大的是哪一个？
不幸的是，我可以给你的最好的答案是“这取决于”。 如果从字面上Data.Map渐近复杂性， Data.Map ，O（min（ Data.HashMap ））= 64， Data.HashMap O（log 4000）= 12， Data.Map O（1）= 1。 但是这并不是真的那样…你必须在你的代码中尝试它们。
Data.Map和Data.HashMap区别在于前者需要Ord键，后者是Hashable键。 大多数常用密钥都是，所以这不是一个决定性的标准。 我没有任何与Data.HashTable经验，所以我不能对此发表评论。
Data.HashMap和Data.Map的API非常相似，但Data.Map导出更多的函数，其中一些像Data.HashMap中没有Data.HashMap ，另外一些提供了严格和非严格的变体，而Data.HashMap （I假设你的意思是来自无序容器的散列表）在单独的模块中提供了惰性和严格的API。 如果你只使用API的公共部分，切换是非常痛苦的。
关于性能， 无序容器的 Data.HashMap查找速度相当快，最后我测量，它明显快于Data.IntMap或Data.Map ，特别适用于（尚未发布的） 无序容器的 HAMT分支。 我认为插入，它是或多或less与Data.IntMap相Data.IntMap并且比Data.Map快一点，但是我有点模糊。
对于大多数任务来说，这两者都是充分的performance，对于那些不是那些任务的人来说，无论如何你可能都需要一个量身定制的解决scheme。 考虑到你特别要求查询，我会给Data.HashMap的边缘。
Data.HashTable的文档现在说“使用哈希表包”。 有一个很好的博客文章解释了为什么哈希表是一个很好的包。 它使用ST monad。
