haskell中的Data.Map的效率

haskell中的Data.Map是用平衡二叉树实现的，相对用hash实现来说，效率应该差了不少
可是Data.hashtable功能好像很弱

有没有比较好的实现方法

hashtable 不一定比 map 快 …… 要看具体情况，而且 ghc 的 hashtable 有时会很慢。

这是比较平均的情况

bench_hashtable.hs

import Control.Monad
import qualified Data.HashTable as H
main = do
    m <- H.new (==) H.hashInt
    forM_ [1..10000000] $ \n -> H.insert m n n
    v <- H.lookup m 100
    print v

bench_hashmap.hs

import Data.IntMap
import Data.List
main = print $ m ! 100
    where m = fromDistinctAscList [(i,i) | i <- [1..10000000]]

在我的机器上（ghc 6.10.2，编译参数 -O2）
bench_hashtable.hs  18.656250s
bench_map.hs  6.328125s

不过这个慢估计是 GC 的原因，bench_hashmap +RTS -H500M 就变成 7.296875s 了。但是仍旧显示 ghc 的 hashtable 实现有问题 ……

比较一下对应的 Ruby 代码 （1.9.1 p129）
bench_hash.rb

h = {}
(1..10000000).each do |i|
  h[i] = i
end
puts h[100]

bench_hash.rb 7.125000 s ，号称最慢的 ruby 竟然还快一点点，是不是很囧 ？ 同样的事情如果用 F# 或者 C++，简直是闪电速度 ……

hash 遇到某个 key 有个超长链的情况，性能会更坏。
不过很多情况换个思路也能达到很高的效率，不是非 hashtable 不可 …… 再不满意就用 C++ 的 unordered_map 补救 ……

hash表常常有更好的效率
但平衡二叉树的效率要比hash稳定 我们说hash的查找效率是1那只是在不考虑冲突的情况下。  况且求hash值也是要时间的 时间复杂度更优不带表效率更好这还和数据规模有关。

hashtable比Map少了很多方法 那是正常的因为hashtable不适合做那些事
作为标准库 把那些方法加进去才不正常呢

没有万能的数据结构 根据自己的需求选一种就是了

谢谢，楼上两位的回复
因为想实现类似python中dict的，可以insert, update等等
用Data.Map实际运行起来比用python还要慢

Data.HashTable 不是引用透明的（这个东西竟然有内部状态 ……），可能他们因此而不太喜欢它 ……

不过我想 CRUD 4 个函数应该够用了，如果要更多的功能，用 combinator 的方式能组合出不少。toList 以后也可以用 list 相关的很多方法。不用太担心 toList 的效率问题，lazy 求值会舍弃很多不必要的计算。

能具体举个例子么？

還有，因為哈希需要提供哈希函數，對于某些沒有或難以提供哈希函數的key，map是唯一的選擇（不能實現Eq的很少）……