如何在函数式语言中实现哈希表？

Question

在纯函数式语言中是否有一种有效的方式来实现哈希表呢？似乎对哈希表的任何更改都需要创建原始哈希表的副本。我可能遗漏了什么。哈希表是非常重要的数据结构，如果没有它们，编程语言就会受到限制。

- Matt Fichman

---

请问您需要翻译的句子是：“Name another data structure that has O(1) random insertion and lookup.”？如果是的话，翻译为：“请列举另一种具有O(1)随机插入和查找的数据结构。” - Matt Fichman

“你也严重高估了哈希表的重要性，并且完全没有为你给它们的重要性做出合理的解释。” 哈希表通常比任何纯函数式集合或字典快10倍以上。因此，在实践中，大多数纯函数式图算法的性能通常是糟糕的，而这种情况通常是不可接受的。 - J D

“你的逻辑有缺陷，而且你对实际应用中有用的东西的假设是误导的。请进一步教育自己，而不要浪费我的时间。”好吧，我已经在几种不同的语言（包括我自己的VM上的自己的语言和GC）中使用了红黑树、AVL树、平衡树、Splay树、哈希树以及开放和闭合哈希表，并用许多不同的键和值类型进行了基准测试，并影响了OCaml、F#、.NET、Haskell和Mathematica中的字典和GC，并为许多公司提供了咨询服务（图形、技术计算、金融等）。 - J D

除非@Jon要求删除那条粗鲁的评论，否则我认为应该让它保留。在我看来，这有点有趣。 - user1228

@C.A.McCann提到“主要是学术领域”。但我所从事的都是工业界中完全不同的商业代码库。图形应用程序使用字典来表示细分曲线和曲面（例如PS、PDF、WPF），在这些情景下性能至关重要。Mathematica的核心是一个全局重写表，它被表示为哈希表，性能至关重要（他们聘请我使用纯函数字典进行了比较）。在金融领域，字典被用于表示一个内存数据库，关联着交易员、出价/报价、交易等信息，既包括客户端也包括服务器。 - J D

Answer 1

在纯函数式编程语言中，有没有一种有效的实现哈希表的方法？

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

似乎对哈希表的任何更改都需要创建原始哈希表的副本。

是的，哈希表本质上是命令式的，没有直接的纯函数式等价物。也许最相似的纯函数式字典类型是哈希树trie，但由于分配和间接引用，它们比哈希表慢得多。

我一定漏了什么。哈希表是非常重要的数据结构，如果没有它，编程语言将受到限制。

字典是非常重要的数据结构（尽管值得注意的是，在 Perl 在 1990 年代使它们流行之前，它们在主流中很少见，因此人们在数十年中编写代码时没有字典的好处）。我同意哈希表也很重要，因为它们通常是迄今为止最有效的字典。

有许多纯函数式字典：

• 平衡树（红黑树，AVL树，重量平衡树，指针树等），例如OCaml和F#中的Map以及Haskell中的Data.Map。

• 哈希tries，例如Clojure中的PersistentHashMap。

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

注意，比较哈希表和纯函数字典的Haskell基准测试声称纯函数字典具有竞争性能时要小心。正确的结论是，Haskell的哈希表非常低效，几乎与纯函数字典一样慢。如果你与.NET进行比较，例如，你会发现.NET Dictionary可以比Haskell的哈希表快26倍！

我认为要真正得出关于 Haskell 性能的结论，你需要测试更多操作，使用一个非荒谬的键类型（双倍作为键，什么鬼？），不要无缘无故地使用 -N8，并将其与第三种也盒化其参数类型的语言进行比较，例如 Java（在大多数情况下，Java 的性能是可接受的），以查看它是否是盒化的常见问题或 GHC 运行时的某些更严重的错误。这些 基准测试 就是这样的（速度约为当前哈希表实现的两倍）。

这正是我所指的错误信息。在这种情况下不要关注 Haskell 的哈希表，只需查看最快的哈希表（即非 Haskell 的）和最快的纯函数字典的性能。

- J D

---

我认为要真正得出你试图得出的有关Haskell性能的结论，你需要测试更多的操作，使用一个非荒谬的键类型（把double作为键，什么？），没有无端地使用-N8选项，并且比较一下和第三种语言的性能，这种语言也像Java一样装箱其参数化类型（因为Java在大多数情况下具有可接受的性能），以查看它是否是装箱的常见问题或GHC运行时的某些更严重的故障。这些基准测试类似于这些内容（并且比当前哈希表实现快约两倍）。 - ScottWest

@ScottWest 我上一段已经解释了为什么这些略慢的Haskell哈希表基准测试是无关紧要的。这是关于快速哈希表与快速纯函数字典的比较。 - J D

我完全同意@JonHarrop的观点，纯函数数据结构无法复制哈希表，也无法伪造它们。我认为这真的值得成为被接受的答案。 - Kristopher Micinski

错误信息？你（现在）倒数第二段基本上是一个不连贯的话，只是想对Haskell性能进行离题攻击。删掉这一段，我很乐意点赞该答案。 - ScottWest

是的，这种情况已经被人们所知。 - Will Ness

Answer 2

哈希表可以用类似于Haskell中的ST monad的方式实现，它基本上将IO操作包装在纯函数接口中。它通过强制按顺序执行IO操作来实现这一点，从而保持引用透明性：您无法访问旧的哈希表“版本”。

参见：hackage.haskell.org/package/hashtables

- Phob

Answer 3

现有的答案都有很好的观点可以分享，我想我只需要添加一个数据来比较一些不同的关联数据结构的性能：

测试包括顺序插入、查找和添加数组元素。 这个测试并不是非常严格，不应该这样认为，它只是对预期结果的一个指示。

首先在Java中使用HashMap，这是未同步的Map实现：

import java.util.Map;
import java.util.HashMap;

class HashTest {
    public static void main (String[] args)
    {
        Map <Integer, Integer> map = new HashMap<Integer, Integer> ();
        int n = Integer.parseInt (args [0]);
        for (int i = 0; i < n; i++)
            {
                map.put (i, i);
            }

        int sum = 0;
        for (int i = 0; i < n; i++)
            {
                sum += map.get (i);
            }


        System.out.println ("" + sum);
    }
}

接着，使用Gregory Collins最近完成的哈希表工作（在hashtables包中）进行Haskell实现。这可以通过ST单子变得纯净无暇，也可以通过IO实现不纯度。我这里使用的是IO版本:

{-# LANGUAGE ScopedTypeVariables, BangPatterns #-}
module Main where

import Control.Monad
import qualified Data.HashTable.IO as HashTable
import System.Environment

main :: IO ()
main = do
  n <- read `fmap` head `fmap` getArgs
  ht :: HashTable.BasicHashTable Int Int <- HashTable.new
  mapM_ (\v -> HashTable.insert ht v v) [0 .. n - 1]
  x <- foldM (\ !s i -> HashTable.lookup ht i >>=
               maybe undefined (return . (s +)))
       (0 :: Int) [0 .. n - 1]
  print x

最后，使用来自hackage的不可变HashMap实现（来自hashmap包）的人：

module Main where

import Data.List (foldl')
import qualified Data.HashMap as HashMap
import System.Environment

main :: IO ()
main = do
  n <- read `fmap` head `fmap` getArgs
  let
    hashmap = 
        foldl' (\ht v -> HashMap.insert v v ht) 
           HashMap.empty [0 :: Int .. n - 1]
  let x = foldl' (\ s i -> hashmap HashMap.! i + s) 0 [0 .. n - 1]
  print x

当n=10,000,000时，我发现总运行时间如下：

• Java HashMap -- 24.387秒
• Haskell HashTable -- 7.705秒，GC占41%时间（
• Haskell HashMap -- 9.368秒，GC占62%时间

将n降至1,000,000时，我们得到：

• Java HashMap -- 0.700秒
• Haskell HashTable -- 0.723秒
• Haskell HashMap -- 0.789秒

这有两个有趣的原因：

1. 性能通常非常接近（除了Java在1M条目以上的分歧）
2. 大量时间花费在收集上！（在n=10,0000,000的情况下，杀死Java）。

这似乎表明，在像Haskell和Java这样的语言中，已经装箱的映射键会受到这种装箱的影响。那些不需要或可以取消装箱键和值的语言可能会看到更多的性能提升。

显然，这些实现并不是最快的，但我会说，以Java为基准，它们至少对于许多用途来说是可接受/可用的（虽然也许更熟悉Java智慧的人可以说HashMap是否被认为是合理的）。

我想指出，与HashTable相比，Haskell HashMap占用了更多的空间。

Haskell程序是使用GHC 7.0.3和-O2 -threaded编译的，并只使用+RTS -s标志运行以获取运行时GC统计信息。Java是使用OpenJDK 1.7编译的。

- ScottWest

---

FYI，在我的 MacBook 上，当 n=10,000,000 时，一个等价的 C# 程序大约需要0.4秒完成。 - Yadli