数据结构——一个Haskell哈希实现，它不存在于IO单子中

Question

我正在寻找一种数据结构，它的工作方式有点像Data.HashTable，但不受IO单子的阻碍。目前，我正在使用[(key,val)]。我想要一个0 (log n)的结构其中n是键值对的个数。

与必须读取的频率相比，构建

结构的频率较低，并且在构建时，我同时拥有所有键值对。如果有区别的话，键是String s。

如果能知道[(key,val)]在多大的尺寸下是值得删除的，那就更好了。

Answer 1

您可以考虑:

• 数据。

或者

• 数据。HashMap

前者是Haskell中按键存储和查找元素的标准容器。后者是一个专门为散列键优化的新库。

Johan Tibell最近的演讲通过散列实现更快的持久数据结构给出了一个概述，而Milan Straka最近的Haskell Symposium论文特别概述了Data.Map结构和hashmap包。

Answer 2

如果您预先有所有的键值对，您可能需要考虑一个完美的哈希函数。

基准测试将告诉您何时从一个简单的列表切换。