如何用函数式语言实现哈希表？ [英] How does one implement hash tables in a functional language?

问题描述

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

解决方案

>有没有什么办法以纯粹的函数式语言高效地实现哈希表？

哈希表是抽象字典或关联数组数据结构。所以我想你真的想问一下纯函数字典与命令式哈希表相比的效率。

看起来对哈希表的任何改变都需要创建原始哈希表的副本。

是的，哈希表本质上是势在必行的并没有直接的纯功能等价物。也许最类似的纯函数字典类型是散列特里，但由于分配和间接指向，它们比散列表慢得多。

我必须失去一些东西。哈希表是非常重要的数据结构，如果没有它们，编程语言将会受到限制。

字典是非常重要的数据结构尽管值得注意的是，直到Perl在20世纪90年代使它们广受欢迎，它们才成为主流，所以人们编码的东西数十年没有字典的好处）。我同意哈希表也很重要，因为它们通常是迄今为止效率最高的字典。

有许多纯粹的功能词典：

• 平衡树木（红黑色，AVL，重量平衡，手指树等），例如在OCaml和F＃中映射和在Haskell中 Data.Map 。


哈希尝试，例如 PersistentHashMap 在Clojure中。

但是这些纯粹功能的字典是所有 比体面散列表（例如.NET Dictionary ）慢。

当心Haskell基准比较散列表和纯功能字典，声称纯功能字典具有竞争性。正确的结论是，Haskell的哈希表效率低下，几乎和纯功能字典一样慢。例如，如果您与.NET进行比较，您会发现 .NET Dictionary 可以比Haskell的哈希表快26倍！

编辑斯科特韦斯特（又名Saynte）低估了我的回答，并添加了一条评论，提到了我所指的那种错误信息。在这种情况下不要关注Haskell的哈希表，只要看看最快哈希表（即不是Haskell）和最快速的纯功能字典的性能。

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. I must be missing something. Hash tables are pretty darn important data structures, and a programming language would be limited without them.

解决方案

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

Hash tables are a concrete implementation of the abstract "dictionary" or "associative array" data structure. So I think you really want to ask about the efficiency of purely functional dictionaries compared to imperative hash tables.

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

Yes, hash tables are inherently imperative and there is no direct purely functional equivalent. Perhaps the most similar purely functional dictionary type is the hash trie but they are significantly slower than hash tables due to allocations and indirections.

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

Dictionaries are a very important data structure (although its worth noting that they were rare in the mainstream until Perl made them popular in the 1990s, so people coded stuff for decades without benefit of dictionaries). I agree that hash tables are also important because they are often by far the most efficient dictionaries.

There are many purely functional dictionaries:

• Balanced trees (red-black, AVL, weight-balanced, finger trees etc.), e.g. Map in OCaml and F# and Data.Map in Haskell.

• Hash tries, e.g. PersistentHashMap in Clojure.

But these purely functional dictionaries are all much slower than a decent hash table (e.g. the .NET Dictionary).

Beware Haskell benchmarks comparing hash tables to purely functional dictionaries claiming that purely functional dictionaries are competitively performant. The correct conclusion is that Haskell's hash tables are so inefficient that they are almost as slow as purely functional dictionaries. If you compare with .NET, for example, you find that a .NET Dictionary can be 26× faster than Haskell's hash table!

EDIT Scott West (aka Saynte) has downvoted my answer and added a comment with exactly the kind of misinformation I was referring to. Pay no attention to Haskell's hash tables in this context, just look at the performance of the fastest hash tables (i.e. not Haskell) and the fastest purely functional dictionaries.

这篇关于如何用函数式语言实现哈希表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！