我正在尝试编写一个利用哈希表的函数(用于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)是否有更好的库满足我的数据结构需求?