Data.Hashtable的算法复杂性

我正在尝试编写一个利用哈希值的函数(用于实现A*).

经过一些研究,我发现事实上的标准是Data.Map.

但是,在阅读API文档时,我发现: O(log n). Find the value at a key.

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

实际上,文档通常表明大O时间明显低于标准Hash的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)我的数据结构需求是否有更好的库？

Data.HashTable已被弃用,您将无法在当前找到它base.

它被弃用了,因为它表现不佳hashtables.

但是,hashtables并且Data.HashTable都是可变实现,Data.Map而且Data.HashMap是不可变的.

Haskell中的可变哈希映射类似于其他语言中的桶阵列或开放寻址解决方案.不可变地图基于树木或尝试.通常,不可变的关联容器不能用O(1)修改来实现.

那么为什么要使用不变的地图？

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

其次,可以在线程之间安全地共享不可变映射,这通常是一个至关重要的特性.

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

第四,由于我不完全理解的原因(更优化的库？更好地优化GHC？),不可变地图可以更快速地显示出来; 我已经尝试了几次Data.HashMap用可变映射替换hashtables,但之后性能总是有点差.