functional-programming - 如何用函数式语言实现哈希表？

Question

有什么方法可以用纯函数式语言有效地实现哈希表吗？似乎对哈希表的任何更改都需要创建原始哈希表的副本。我肯定错过了什么。哈希表是非常重要的数据结构，没有它们，编程语言就会受到限制。

Answer 1

Is there any way to implement hash tables efficiently in a purely functional language?

哈希表是抽象“字典”或“关联数组”数据结构的具体实现。所以我想你真的很想问问纯函数字典与命令式哈希表相比的效率。

It seems like any change to the hash table would require creating a copy of the original hash table.

是的，哈希表本质上是必不可少的，并且没有直接的纯功能等价物。也许最相似的纯函数字典类型是哈希 trie但是由于分配和间接，它们比哈希表慢得多。

I must be missing something. Hash tables are pretty darn important data structures, and a programming language would be limited without them.

字典是一种非常重要的数据结构(尽管值得注意的是，在 1990 年代 Perl 使它们流行之前，它们在主流中很少见，因此人们在没有字典的情况下编码了几十年)。我同意哈希表也很重要，因为它们通常是迄今为止最有效的字典。

有很多纯函数字典:

平衡树(红黑、AVL、权重平衡、指状树等)，例如Map在 OCaml 和 F# 和 Data.Map在 haskell 。

哈希tries ，例如PersistentHashMap在 Clojure 中。

但是这些纯函数字典都比一个像样的哈希表(例如 .NET Dictionary)慢得多。

当心 Haskell 基准将哈希表与纯函数字典进行比较，声称纯函数字典具有竞争力。正确的结论是 Haskell 的哈希表效率很低，以至于它们几乎和纯函数字典一样慢。例如，如果与 .NET 进行比较，您会发现 a .NET Dictionary can be 26× faster than Haskell's hash table !

I think to really conclude what you're trying to conclude about Haskell's performance you would need to test more operations, use a non-ridiculous key-type (doubles as keys, what?), not use -N8 for no reason, and compare to a 3rd language that also boxes its parametric types, like Java (as Java has acceptable performance in most cases), to see if its a common problem of boxing or some more serious fault of the GHC runtime. These benchmarks are along these lines (and ~2x as fast as the current hashtable implementation).

这正是我所指的那种错误信息。在此上下文中不要关注 Haskell 的哈希表，只需查看最快的哈希表(即不是 Haskell)和最快的纯函数字典的性能。