数据结构中的哈希表算法复杂度

Question

我正在尝试编写一个利用哈希表的函数（用于A *实现）。

经过一些研究，我发现事实上标准是使用 Data.Map。

然而，在阅读API文档时，我发现： O(log n). 查找键对应的值。

https://downloads.haskell.org/~ghc/6.12.2/docs/html/libraries/containers-0.3.0.0/Data-Map.html

实际上，文档通常建议使用大O时间明显低于标准哈希表的O(1)。

然后我发现 Data.HashTable。 https://hackage.haskell.org/package/base-4.2.0.2/docs/Data-HashTable.html 这份文档没有直接提到大O，让我相信它可能符合我的期望。

我有几个问题： 1）那正确吗？ O(lookupInDataHashTable) = O(1)？ 2）鉴于其效率低下，为什么要使用 Data.Map？ 3）是否有更好的库满足我的数据结构需求？

- Abraham P

---

实际应用中，你应该对比O(1)和O(log n)算法（前者可能有更大的常数），可以选择使用Data.Map或Data.IntMap。如果需要使用Data.HashTable，请参考https://hackage.haskell.org/package/hashtables。总的来说，我认为最重要的是最终的内存使用情况。 - josejuan

Answer 1

Data.HashTable已经被弃用，你将无法在当前的base中找到它。

它被弃用是因为与hashtables相比表现不佳。

然而，hashtables和Data.HashTable都是可变实现，而Data.Map和Data.HashMap是不可变的。

Haskell中的可变哈希映射类似于其他语言中的桶数组或开放地址解决方案。不可变映射基于树或trie。一般来说，不可变关联容器无法使用O(1)修改实现。

那么为什么要使用不可变映射？

首先，在Haskell中API更加方便。我们不能在纯函数中使用可变映射，只能在IO或ST操作中使用。

第二，不可变映射可以在线程之间安全地共享，这通常是一个关键特性。

第三，在实践中，可变和不可变映射之间的性能差异可能是微不足道的，即它不会明显影响整个程序的性能。O(log n)也受到可用内存的限制，因此与O(1)相比，我们不会得到显著的渐近差异。特别是，Data.HashMap使用16分支trie，因此trie深度实际上不能超过6或7。

第四，由于一些我不完全理解的原因（更优化的库？GHC的更好优化？），不可变映射可能只是纯粹更快。我曾几次尝试将Data.HashMap替换为来自hashtables的可变映射，但之后性能总是稍微差一些。

- András Kovács

---

你是否发现，无论是大型的可变映射还是小型的可变映射，在性能方面都表现不佳？ - sshine

大型可变映射性能较差。特别是，在具有300k-500k元素的映射中，这里注释掉的trieToNode链接表现明显较差。 - András Kovács

Answer 2

为什么会使用Data.Map，尽管其效率不高？

它虽不高效，但支持任何具有Ord实例的键类型，甚至那些不能散列为整数的类型。

O(lookupInDataHashTable) = O(1)吗？

通常来说是的。"lookupInDataHashTable"的工作流程及其对应的大O符号表示的性能如下：

1. 对键进行哈希运算。对于整数：O(1)，对于字符串：O（字符串长度） 2. 访问IOArray并获取列表，其中包含所有具有相同哈希值的键值对。O(1) 3. 在列表中查找键。O（列表长度）

因此，除非您的键非常长，否则查找函数保证具有O（1）的性能。

是否有更好的库满足我的数据结构需求？

这要取决于你的键类型。对于不同的整数，Data.IntMap 是最佳的，对于其他可散列类型，Data.HashMap 表现良好，否则只能使用 Data.Map。

- zakyggaps

---

我的键是字符串类型。 - Abraham P

@AbrahamP 在这种情况下，您可能需要考虑使用（路径压缩）Trie树。 - Daniel Wagner

@AbrahamP，你的键有多长？这真的很重要。此外，在放弃纯度和其优势以使用哈希表之前，您应该查看哈希映射、trie变体等是否足够快。 - dfeuer