第 15 章：映射与哈希表（Maps and Hash Tables）

原文：Anil Madhavapeddy and Yaron Minsky, Real World OCaml: Functional Programming for the Masses, Second Edition, Chapter 15。维护者已确认本书为开源书籍，可翻译并发布用于学习研究。

许多编程问题都需要处理按键/值对组织的数据。在 OCaml 中，表示这类数据最简单的方式也许是关联列表（association list），它就是键和值组成的二元组列表。例如，可以像下面这样表示 10 个数字与其英文名称之间的映射：

# open Base;;
# let digit_alist =
    [ 0, "zero"; 1, "one"; 2, "two"  ; 3, "three"; 4, "four"
    ; 5, "five"; 6, "six"; 7, "seven"; 8, "eight"; 9, "nine" ];;
val digit_alist : (int * string) list =
  [(0, "zero"); (1, "one"); (2, "two"); (3, "three"); (4, "four");
   (5, "five"); (6, "six"); (7, "seven"); (8, "eight"); (9, "nine")]

可以使用 List.Assoc 模块中的函数操作这些数据：

# List.Assoc.find ~equal:Int.equal digit_alist 6;;
- : string option = Some "six"
# List.Assoc.find ~equal:Int.equal digit_alist 22;;
- : string option = None
# List.Assoc.add ~equal:Int.equal digit_alist 0 "zilch";;
- : (int, string) Base.List.Assoc.t =
[(0, "zilch"); (1, "one"); (2, "two"); (3, "three"); (4, "four");
 (5, "five"); (6, "six"); (7, "seven"); (8, "eight"); (9, "nine")]

关联列表简单且易用，但性能并不理想，因为关联列表上几乎所有非平凡操作都需要对列表做线性时间扫描。

本章会讨论关联列表的两个更高效替代方案：映射（maps）和哈希表（hash tables）。映射是一种不可变、基于树的数据结构，大多数操作耗时与映射大小成对数关系；哈希表是一种可变数据结构，大多数操作具有常数时间复杂度。我们会详细说明这两种数据结构，并给出一些如何在两者之间选择的建议。

15.1 映射（Maps）

先看一个实践中可能如何使用映射的例子。在第 5 章“文件、模块与程序（Files, Modules, and Programs）”中，我们展示过一个模块 Counter，用于维护一组字符串的频率计数。下面是它的接口：

open Base

(** A collection of string frequency counts *)
type t

(** The empty set of frequency counts *)
val empty : t

(** Bump the frequency count for the given string. *)
val touch : t -> string -> t

(** Converts the set of frequency counts to an association list. Every
    string in the list will show up at most once, and the integers
    will be at least 1. *)
val to_list : t -> (string * int) list

这里的预期行为很直接。Counter.empty 表示空的频率计数集合；touch 会把指定字符串的频率计数加 1；to_list 则返回非零频率的列表。

下面是实现：

open Base

type t = (string, int, String.comparator_witness) Map.t

let empty = Map.empty (module String)
let to_list t = Map.to_alist t

let touch t s =
  let count =
    match Map.find t s with
    | None -> 0
    | Some x -> x
  in
  Map.set t ~key:s ~data:(count + 1)

看看上面类型 t 的定义。你会看到 Map.t 有三个类型参数。前两个符合预期：一个用于键的类型，一个用于数据的类型。第三个类型参数，也就是比较器见证（comparator witness），需要解释一下。

比较器见证用于指明构造该映射时使用的是哪个比较函数，而不是说明映射中存储的数据类型。特别是，类型 String.comparator_witness 表示这个映射是用 String 模块提供的默认比较函数构建的。本章稍后会讨论为什么比较器见证很重要。

对 Map.empty 的调用也值得解释，因为它不太寻常地把一个一等模块作为参数。这个一等模块的作用是提供构建映射所需的比较函数，以及一个用于生成有用错误消息的 S 表达式转换器。我们会在第 21 章“使用 S 表达式进行数据序列化（Data Serialization with S-Expressions）”中进一步讨论 S 表达式。对于 Map.find 或 Map.add 这样的函数，不需要再次提供该模块，因为映射本身包含了对其所用比较函数的引用。

并不是每个模块都能用于创建映射，但 Base 中的标准模块可以。本章后面会展示如何设置你自己的模块，使其也能以这种方式使用。

15.1.1 集合（Sets）

除了映射，Base 还提供了一种集合数据类型，它的设计思路与映射类似。从某种意义上说，集合不过是忽略数据部分的映射。虽然可以用映射来编码集合，但使用 Base 专门提供的集合类型更自然，也更高效。下面是一个简单例子：

# Set.of_list (module Int) [1;2;3] |> Set.to_list;;
- : int list = [1; 2; 3]
# Set.union
    (Set.of_list (module Int) [1;2;3;2])
    (Set.of_list (module Int) [3;5;1])
  |> Set.to_list;;
- : int list = [1; 2; 3; 5]

除了你会期待映射拥有的那些操作之外，集合还支持传统集合操作，包括并集、交集和差集。

15.1.2 模块与比较器（Modules and Comparators）

基于 Base 中某个模块表示的类型创建映射或集合很容易。这里，我们基于本章前面定义的 digit_alist，创建一个从数字到其英文名称的映射。

# let digit_map = Map.of_alist_exn (module Int) digit_alist;;
val digit_map : (int, string, Int.comparator_witness) Map.t = <abstr>
# Map.find digit_map 3;;
- : string option = Some "three"

函数 Map.of_alist_exn 会从给定关联列表构造映射。如果某个键被使用多次，它会抛出异常。看一下 Map.of_alist_exn 的类型签名：

# #show Map.of_alist_exn;;
val of_alist_exn :
  ('a, 'cmp) Set.comparator -> ('a * 'b) list -> ('a, 'b, 'cmp) Map.t

Map.comparator 类型实际上是一等模块类型的别名，表示任何匹配下面所示签名 Comparator.S 的模块。

# #show Base.Comparator.S;;
module type S = Base.Comparator.S

这样的模块必须包含键本身的类型、comparator_witness 类型、以及具体比较器本身。comparator_witness 充当相关比较函数在类型层面的标识符，而具体比较器值则包含必要的比较函数。

Base 中的 Int 和 String 等模块已经满足这个接口。但如果你想让一个新模块满足这个接口呢？例如，考虑下面这个表示书籍的类型，我们为它写了一个比较函数和一个 S 表达式序列化器。

# module Book = struct

    type t = { title: string; isbn: string }

    let compare t1 t2 =
      let cmp_title = String.compare t1.title t2.title in
      if cmp_title <> 0 then cmp_title
      else String.compare t1.isbn t2.isbn

    let sexp_of_t t : Sexp.t =
      List [ Atom t.title; Atom t.isbn ]
  end;;
module Book :
  sig
    type t = { title : string; isbn : string; }
    val compare : t -> t -> int
    val sexp_of_t : t -> Sexp.t
  end

这个模块拥有我们需要的基础功能，但还不满足 Comparator.S 接口，所以还不能用它创建映射，如下所示：

# Map.empty (module Book);;
Line 1, characters 19-23:
Error: Signature mismatch:
       ...
       The type `comparator_witness' is required but not provided
       File "duniverse/base/src/comparator.mli", line 18, characters 2-25:
         Expected declaration
       The value `comparator' is required but not provided
       File "duniverse/base/src/comparator.mli", line 20, characters 2-53:
         Expected declaration

为了满足这个接口，需要使用 Comparator.Make 函子扩展该模块。这里使用一种常见惯用法：创建一个名为 T 的子模块，包含相关类型的基础功能，然后同时包含该模块，以及把函子应用到该模块后得到的结果。

module Book = struct
  module T = struct

    type t = { title: string; isbn: string }

    let compare t1 t2 =
      let cmp_title = String.compare t1.title t2.title in
      if cmp_title <> 0 then cmp_title
      else String.compare t1.isbn t2.isbn

    let sexp_of_t t : Sexp.t =
      List [ Atom t.title; Atom t.isbn ]

  end
  include T
  include Comparator.Make(T)
end;;

有了这个模块，现在可以构建一个 Book.t 集合：

# let some_programming_books =
    Set.of_list (module Book)
      [ { title = "Real World OCaml"
        ; isbn = "978-1449323912" }
      ; { title = "Structure and Interpretation of Computer Programs"
        ; isbn = "978-0262510875" }
      ; { title = "The C Programming Language"
        ; isbn = "978-0131101630" } ];;
val some_programming_books : (Book.t, Book.comparator_witness) Set.t =
  <abstr>

上面使用了 Comparator.Make，但通常更推荐使用 Comparable.Make，因为除了比较器本身之外，它还提供额外辅助函数，例如中缀比较运算符以及最小值、最大值函数。

15.1.3 为什么需要比较器见证（Why Do We Need Comparator Witnesses）

比较器见证与我们已经见过的其他类型很不一样。它不是用来跟踪正在使用的数据种类，而是用于挑出某个特定值，也就是某个比较函数。为什么我们需要这种东西？

比较器见证很重要，因为映射和集合上的某些操作，尤其是那些组合多个映射或集合的操作，其正确性依赖于一个事实：被组合的两个对象都按照同一个全序排列，而这个全序又由比较函数决定。

例如，考虑 Map.symmetric_diff，它计算两个映射之间的差异。

# let left = Map.of_alist_exn (module String) ["foo",1; "bar",3; "snoo",0];;
val left : (string, int, String.comparator_witness) Map.t = <abstr>
# let right = Map.of_alist_exn (module String) ["foo",0; "snoo",0];;
val right : (string, int, String.comparator_witness) Map.t = <abstr>
# Map.symmetric_diff ~data_equal:Int.equal left right |> Sequence.to_list;;
- : (string, int) Map.Symmetric_diff_element.t list =
[("bar", `Left 3); ("foo", `Unequal (1, 0))]

如下所示，Map.symmetric_diff 的类型要求它比较的两个映射不仅拥有相同的键和值类型，还必须拥有相同的比较器见证。

# #show Map.symmetric_diff;;
val symmetric_diff :
  ('k, 'v, 'cmp) Map.t ->
  ('k, 'v, 'cmp) Map.t ->
  data_equal:('v -> 'v -> bool) ->
  ('k, 'v) Map.Symmetric_diff_element.t Sequence.t

如果没有这个约束，就可以对按不同顺序排序的映射运行 Map.symmetric_diff，这可能导致混乱结果。

为了看到这个约束实际发挥作用，需要创建两个键和值类型相同、但比较函数不同的映射。下面通过创建一个新模块 Reverse 来做到这一点。该模块表示按常规字典序相反顺序排序的字符串。

module Reverse = struct
  module T = struct
    type t = string
    let sexp_of_t = String.sexp_of_t
    let t_of_sexp = String.t_of_sexp
    let compare x y = String.compare y x
  end
  include T
  include Comparator.Make(T)
end;;

如下所示，Reverse 和 String 都可以用来创建键类型为 string 的映射：

# let alist = ["foo", 0; "snoo", 3];;
val alist : (string * int) list = [("foo", 0); ("snoo", 3)]
# let ord_map = Map.of_alist_exn (module String) alist;;
val ord_map : (string, int, String.comparator_witness) Map.t = <abstr>
# let rev_map = Map.of_alist_exn (module Reverse) alist;;
val rev_map : (string, int, Reverse.comparator_witness) Map.t = <abstr>

Map.min_elt 会返回映射中最小键对应的键和值，这确认了两个映射确实使用不同的比较函数。

# Map.min_elt ord_map;;
- : (string * int) option = Some ("foo", 0)
# Map.min_elt rev_map;;
- : (string * int) option = Some ("snoo", 3)

因此，Map.symmetric_diff 中的算法应用到这些值时根本无法正确工作。好在如果尝试这么做，类型系统会在编译期给出错误，而不是在运行时抛出错误，更不会默默返回错误结果。

# Map.symmetric_diff ord_map rev_map;;
Line 1, characters 28-35:
Error: This expression has type
         (string, int, Reverse.comparator_witness) Map.t
       but an expression was expected of type
         (string, int, String.comparator_witness) Map.t
       Type Reverse.comparator_witness is not compatible with type
         String.comparator_witness

15.1.4 多态比较器（The Polymorphic Comparator）

并不需要为每个想要构建映射的类型都生成专用比较器。也可以基于 OCaml 内置的多态比较函数构建映射。多态比较函数已经在第 4 章“列表与模式（Lists and Patterns）”中讨论过。

# Map.Poly.of_alist_exn digit_alist;;
- : (int, string) Map.Poly.t = <abstr>

注意，基于多态比较器的映射，与基于类型专用比较函数的映射，拥有不同的比较器见证。因此，编译器会拒绝下面的代码：

# Map.symmetric_diff
    (Map.Poly.singleton 3 "three")
    (Map.singleton (module Int) 3 "four" );;
Line 3, characters 5-43:
Error: This expression has type (int, string, Int.comparator_witness) Map.t
       but an expression was expected of type
         (int, string, Map.Poly.comparator_witness) Map.t
       Type Int.comparator_witness is not compatible with type
         Map.Poly.comparator_witness

这段代码被拒绝是有充分理由的：并不能保证某个类型关联的比较器会以与多态比较相同的方式排序。

多态比较的陷阱（The Perils of Polymorphic Compare）

多态比较非常方便，但它有严重缺点，在生产代码中大多应该避免。要理解原因，需要先理解多态比较如何工作。

多态比较直接操作 OCaml 值的运行时表示，遍历这些值的结构，而不考虑它们的类型。

尽管忽略类型，它大体上仍会按你希望的方式运行。对 int 和 float 的比较会遵守普通数值顺序，字符串、列表和数组这样的容器会按字典序比较。它也能作用于几乎所有 OCaml 类型，只是有一些重要例外，例如函数。

但多态比较忽略类型的本质意味着它会窥探普通抽象边界之下的实现，这可能导致一些非常令人困惑的结果。映射本身就是一个很好的例子。考虑下面两个映射：

# let m1 = Map.of_alist_exn (module Int) [1, "one";2, "two"];;
val m1 : (int, string, Int.comparator_witness) Map.t = <abstr>
# let m2 = Map.of_alist_exn (module Int) [2, "two";1, "one"];;
val m2 : (int, string, Int.comparator_witness) Map.t = <abstr>

从逻辑上说，这两个映射应该相等，而调用 Map.equal 时也会得到这个结果：

# Map.equal String.equal m1 m2;;
- : bool = true

但由于元素是以不同顺序加入的，映射底层树的布局会不同。因此，多态比较会断定它们不同。

可以在下面看到这一点。注意，Base 默认隐藏多态比较，但可以通过 Poly 模块使用它。

# Poly.(m1 = m2);;
Exception: Invalid_argument "compare: functional value".

这个比较失败了，因为多态比较不能作用于函数，而映射会存储创建它时所用的比较函数。好在有一个函数 Map.Using_comparator.to_tree 可以暴露底层二叉树，而不带附加的比较函数。可以用它来比较底层树：

# Poly.((Map.Using_comparator.to_tree m1) =
  (Map.Using_comparator.to_tree m2));;
- : bool = false

可以看到，多态比较现在能产生结果了，但它不是我们想要的结果。

多态比较破坏抽象的本质可能导致真实而微妙的 bug。例如，如果构造一个以集合为键的映射，而集合也存在与映射相同的多态比较问题，那么用多态比较器构建的映射就会行为错误，把本应聚合在一起的键分开。更糟的是，它的行为还会不一致，因为多态比较的行为会依赖这些集合被构造出来的顺序。

15.1.5 用 [@@deriving] 满足 Comparator.S（Satisfying Comparator.S with [@@deriving]）

在新类型上使用映射和集合，需要满足 Comparator.S 接口，而这又需要为相关类型提供 S 表达式转换器和比较函数。手写这些函数既烦人又容易出错，但有更好的方式。Base 带有一组语法扩展，可以自动完成这些任务。

回到本章前面的例子，我们创建了类型 Book.t，并把它设置成可用于创建映射和集合。

module Book = struct
  module T = struct

    type t = { title: string; isbn: string }

    let compare t1 t2 =
      let cmp_title = String.compare t1.title t2.title in
      if cmp_title <> 0 then cmp_title
      else String.compare t1.isbn t2.isbn

    let sexp_of_t t : Sexp.t =
      List [ Atom t.title; Atom t.isbn ]

  end
  include T
  include Comparator.Make(T)
end

这里很大一部分代码都用于为 Book.t 类型创建比较函数和 S 表达式转换器。但如果启用了 ppx_sexp_conv 和 ppx_compare 语法扩展，就可以请求它们为我们创建这些函数的默认实现。可以通过总包 ppx_jane 同时启用这两个扩展。

# #require "ppx_jane";;

然后可以在 Book 定义中这样使用这些扩展：

module Book = struct
  module T = struct
    type t = { title: string; isbn: string }
    [@@deriving compare, sexp_of]
  end
  include T
  include Comparator.Make(T)
end;;

如果需要某种特定排序方式，始终可以手写比较函数；但如果你只需要一个适合创建映射和集合的全序，那么 [@@deriving compare] 是一个好选择。

=、== 与 phys_equal

OCaml 有多种相等性概念，选对并不总是容易。如果没有打开 Base，你会发现 == 运算符测试的是物理相等，而 = 运算符是多态相等函数。

如果两个值在内存中是同一个指针，就认为它们物理相等。两个内容相同但分别构造的数据结构，不会被 == 认为相等。另一方面，多态相等是结构性的，这实际上意味着，如果值拥有相同内容，它就会认为它们相等。

大多数时候，这两种相等形式你都不想要。多态相等有前面解释过的问题；物理相等虽然有用，但只在特定情况下需要，最常见的是处理可变对象时，因为这时对象的物理身份很重要。

Base 隐藏了多态相等，而把 = 保留给与特定类型关联的相等函数。在顶层，= 被专门化为整数相等。

# 1 = 2;;
- : bool = false
# "one" = "two";;
Line 1, characters 1-6:
Error: This expression has type string but an expression was expected of type
         int

其他类型专用相等函数位于对应模块中：

# String.("one" = "two");;
- : bool = false

= 和 == 很容易混淆，所以 Base 废弃了 ==，并提供了 phys_equal，这是一个名称清晰且有描述性的函数。

# ref 1 == ref 1;;
Line 1, characters 7-9:
Alert deprecated: Base.==
[2016-09] this element comes from the stdlib distributed with OCaml.
Use [phys_equal] instead.
- : bool = false
# phys_equal (ref 1) (ref 1);;
- : bool = false

这只是 Base 试图避免容易出错的 API 的一个小例子。

15.1.6 把 [@@deriving] 应用于映射和集合（Applying [@@deriving] to Maps and Sets）

上一节展示了如何使用 [@@deriving] 标注设置一个类型，使其可用于创建映射或集合类型。但如果想在映射或集合类型本身上放置 [@@deriving] 标注呢？

# type string_int_map =
    (string,int,String.comparator_witness) Map.t [@@deriving sexp];;
Line 2, characters 44-49:
Error: Unbound value Map.t_of_sexp
Hint: Did you mean m__t_of_sexp?

这会失败，因为并不存在现成的 Map.t_of_sexp。这不是简单的遗漏。没有合理方式定义一个有用的 Map.t_of_sexp，因为比较器见证并不是可以从 S 表达式中解析出来的东西。

好在还有另一种方式可以书写映射类型，并且能与各种 [@@deriving] 扩展一起工作，如下所示：

# type string_int_map = int Map.M(String).t [@@deriving sexp];;
type string_int_map = int Base.Map.M(Base.String).t
val string_int_map_of_sexp : Sexp.t -> string_int_map = <fun>
val sexp_of_string_int_map : string_int_map -> Sexp.t = <fun>

这里使用函子 Map.M 定义所需类型。虽然这种写法看起来不同于普通类型签名，但类型含义是相同的，如下所示：

# let m = Map.singleton (module String) "one" 1;;
val m : (string, int, String.comparator_witness) Map.t = <abstr>
# (m : int Map.M(String).t);;
- : int Base.Map.M(Base.String).t = <abstr>

同一种类型也能与其他 deriver 配合使用，例如用于比较和哈希函数的 deriver。由于这种类型写法也更短，所以大多数时候都应该使用它。

15.1.7 树（Trees）

如前所述，映射内部携带了创建它时使用的比较器。有时出于空间效率考虑，你可能想要一个不包含比较器的映射数据结构版本。可以通过 Map.Using_comparator.to_tree 得到这样的表示，它只返回映射底层的树，不带比较器。

# let ord_tree = Map.Using_comparator.to_tree ord_map;;
val ord_tree :
  (string, int, String.comparator_witness) Map.Using_comparator.Tree.t =
  <abstr>

虽然树在物理上不包含比较器，但它的类型包含比较器。这就是所谓的幻影类型（phantom type）：它反映了相关值逻辑上的某种属性，尽管这个属性并不直接对应底层物理结构中表示的任何值。

由于比较器没有包含在树中，所以在查找键时，需要显式提供比较器，如下所示：

# Map.Using_comparator.Tree.find ~comparator:String.comparator ord_tree "snoo";;
- : int option = Some 3

Map.Tree.find 的算法依赖这样一个事实：查找值时使用的比较器，与存储值时使用的比较器相同。这正是幻影类型要强制维护的不变量。下面的例子展示了使用错误比较器会导致类型错误：

# Map.Using_comparator.Tree.find ~comparator:Reverse.comparator ord_tree "snoo";;
Line 1, characters 63-71:
Error: This expression has type
         (string, int, String.comparator_witness) Map.Using_comparator.Tree.t
       but an expression was expected of type
         (string, int, Reverse.comparator_witness)
         Map.Using_comparator.Tree.t
       Type String.comparator_witness is not compatible with type
         Reverse.comparator_witness

15.2 哈希表（Hash Tables）

哈希表是映射的命令式表亲。第 9 章“命令式编程（Imperative Programming）”中已经走读过一个基础哈希表实现，所以本节主要讨论 Core 的 Hashtbl 模块在实践中的用法。与映射相比，这里会更简略，因为许多概念是共享的。

哈希表与映射有几个关键区别。首先，哈希表是可变的，这意味着向哈希表添加键/值对会修改表本身，而不是创建一个带有新绑定的新表。其次，哈希表通常比映射有更好的时间复杂度：查找和修改通常是常数时间，而映射是对数时间。最后，正如映射依赖比较函数来创建底层有序二叉树，哈希表依赖哈希函数，也就是把键转换成整数的函数。

15.2.1 哈希表的时间复杂度（Time Complexity of Hash Tables）

说哈希表提供常数时间访问，会隐藏一些复杂性。首先，包括 OCaml 在内，大多数哈希表实现都需要在表太满时调整大小。调整大小需要为哈希表分配新的底层数组，并复制所有条目，因此这是一个相当昂贵的操作。这意味着向表中添加新元素只是摊还常数时间，也就是说，在一长串操作中平均看是常数时间，但某些单独操作可能花费更多。

哈希表的另一个隐藏成本与所用哈希函数有关。如果最终得到一个病态糟糕的哈希函数，把所有数据都哈希到同一个数字，那么所有插入都会落到同一个底层桶中，这意味着你根本得不到常数时间访问。Base 的哈希表实现为哈希桶使用二叉树，所以这种情况下只会退化到对数时间，而不是传统实现中的线性时间。

在存在哈希碰撞时，Base 哈希表的对数行为也有助于防御某些拒绝服务攻击。一种著名攻击方式是向服务发送带有精心选择键的查询，导致大量碰撞。结合多数哈希表的线性行为，这可能让服务因 CPU 负载过高而无响应。Base 的哈希表不太容易受这类攻击影响，因为退化程度要小得多。

我们创建哈希表的方式类似于创建映射，也就是提供一个一等模块，从中取得构建哈希表所需的操作。

# let table = Hashtbl.create (module String);;
val table : (string, '_weak1) Base.Hashtbl.t = <abstr>
# Hashtbl.set table ~key:"three" ~data:3;;
- : unit = ()
# Hashtbl.find table "three";;
- : int option = Some 3

和映射一样，Base 中的大多数模块都已经可以为此目的使用。但如果想根据自己的类型创建哈希表，就需要做一些准备工作。为了让模块适合传给 Hashtbl.create，它必须匹配下面这个接口。

# #show Base.Hashtbl.Key.S;;
module type S = Base__Hashtbl_intf.Key.S

注意，这里没有映射和集合中出现的比较器见证等价物。这是因为让多个对象共享同一个比较函数或哈希函数的需求，对哈希表来说基本不会出现。这使得构建适合用于哈希表的模块更简单。

# module Book = struct
    type t = { title: string; isbn: string }
    [@@deriving compare, sexp_of, hash]
  end;;
module Book :
  sig
    type t = { title : string; isbn : string; }
    val compare : t -> t -> int
    val sexp_of_t : t -> Sexp.t
    val hash_fold_t :
      Base_internalhash_types.state -> t -> Base_internalhash_types.state
    val hash : t -> int
  end
# let table = Hashtbl.create (module Book);;
val table : (Book.t, '_weak2) Base.Hashtbl.t = <abstr>

也可以基于 OCaml 的多态哈希和比较函数创建哈希表。

# let table = Hashtbl.Poly.create ();;
val table : ('_weak3, '_weak4) Base.Hashtbl.t = <abstr>
# Hashtbl.set table ~key:("foo",3,[1;2;3]) ~data:"random data!";;
- : unit = ()
# Hashtbl.find table ("foo",3,[1;2;3]);;
- : string option = Some "random data!"

这非常方便，但多态比较可能表现出令人意外的行为，所以对于正确性重要的代码，通常最好避免这种做法。

15.2.2 多态哈希函数的碰撞（Collisions with the Polymorphic Hash Function）

多态哈希函数和多态比较一样，也有一些问题。这些问题源于它完全不关注类型，只是盲目沿着数据类型结构向下遍历，并根据看到的内容计算哈希。这意味着，对于映射和集合这样的数据结构，如果等价实例可能有不同结构，它就会做错事。

但多态哈希还有另一个问题：它容易产生哈希碰撞。OCaml 的多态哈希函数会以广度优先遍历方式遍历给定数据结构，并且会限制愿意遍历的节点数量。默认情况下，这个界限被设为 10 个“有意义”的节点。

遍历界限意味着哈希函数可能忽略数据结构的一部分，这可能导致病态情形：你存储的每个值都有相同哈希值。下面用 List.range 函数分配不同长度的整数列表来演示这一点：

# Hashtbl.Poly.hashable.hash (List.range 0 9);;
- : int = 209331808
# Hashtbl.Poly.hashable.hash (List.range 0 10);;
- : int = 182325193
# Hashtbl.Poly.hashable.hash (List.range 0 11);;
- : int = 182325193
# Hashtbl.Poly.hashable.hash (List.range 0 100);;
- : int = 182325193

可以看到，哈希函数在前 10 个元素后就停止了。任何大型数据结构都可能发生同样情况，包括记录和数组。为大型自定义数据结构构建哈希函数时，通常最好手写自己的哈希函数，或者使用 [@@deriving] 提供的函数。后者没有这个问题，如下所示：

# [%hash: int list] (List.range 0 9);;
- : int = 999007935
# [%hash: int list] (List.range 0 10);;
- : int = 195154657
# [%hash: int list] (List.range 0 11);;
- : int = 527899773
# [%hash: int list] (List.range 0 100);;
- : int = 594983280

注意，这里没有声明类型并使用 [@@deriving hash] 调用 ppx_hash，而是使用 [%hash]，这是一种在表达式中内联创建哈希函数的简写。

15.3 在映射与哈希表之间选择（Choosing Between Maps and Hash Tables）

映射和哈希表在功能上有足够多重叠，因此并不总是清楚什么时候该选择哪一个。由于映射不可变，它通常是 OCaml 中的默认选择。不过，OCaml 也很好地支持命令式编程，所以在使用命令式惯用法编程时，哈希表往往是更自然的选择。

撇开编程惯用法不谈，映射和哈希表之间也存在显著性能差异。对于以更新和查找为主的代码，哈希表有明显性能优势，而且数据量越大，优势越明显。

回答性能问题的最佳方式是运行基准测试，所以我们就这么做。下面的基准测试使用 core_bench 库，在非常简单的负载下比较映射和哈希表。这里跟踪 1,000 个不同整数键，并循环遍历这些键、更新它们包含的值。注意，我们使用 Map.change 和 Hashtbl.change 函数来更新相应数据结构：

open Base
open Core_bench

let map_iter ~num_keys ~iterations =
  let rec loop i map =
    if i <= 0
    then ()
    else
      loop
        (i - 1)
        (Map.change map (i % num_keys) ~f:(fun current ->
             Some (1 + Option.value ~default:0 current)))
  in
  loop iterations (Map.empty (module Int))

let table_iter ~num_keys ~iterations =
  let table = Hashtbl.create (module Int) ~size:num_keys in
  let rec loop i =
    if i <= 0
    then ()
    else (
      Hashtbl.change table (i % num_keys) ~f:(fun current ->
          Some (1 + Option.value ~default:0 current));
      loop (i - 1))
  in
  loop iterations

let tests ~num_keys ~iterations =
  let t name f = Bench.Test.create f ~name in
  [ t "table" (fun () -> table_iter ~num_keys ~iterations)
  ; t "map" (fun () -> map_iter ~num_keys ~iterations)
  ]

let () =
  tests ~num_keys:1000 ~iterations:100_000
  |> Bench.make_command
  |> Command_unix.run

结果显示，哈希表版本大约比映射版本快三到四倍：

(executable
  (name      map_vs_hash)
  (libraries base core_bench core_unix.command_unix))

$ dune build map_vs_hash.exe
$ ./_build/default/map_vs_hash.exe -ascii -quota 1 -clear-columns time speedup
Estimated testing time 2s (2 benchmarks x 1s). Change using -quota SECS.

  Name    Time/Run   Speedup
 ------- ---------- ---------
  table    13.34ms      1.00
  map      44.54ms      3.34

可以根据测试细节让加速比变小或变大。例如，它会随不同键的数量变化。但总体而言，对于大量查询和更新一组键/值对的代码，哈希表会明显胜过映射。

不过，哈希表并不总是更快的选择。特别是，当你需要在内存中同时保留数据结构的多个相关版本时，映射表现突出。原因在于映射不可变，因此像 Map.add 这样修改映射的操作，会创建一个新映射，同时保持原映射不受干扰。而且，新旧映射共享大部分物理结构，所以保留多个版本在空间上可以很高效。

下面的基准测试展示了这一点。在这个测试中，我们通过迭代应用小更新来构建映射或哈希表列表，并保留这些副本。在映射情况下，这通过 Map.change 更新映射完成。在哈希表实现中，更新使用 Hashtbl.change 完成，但还需要调用 Hashtbl.copy 来拍摄表的快照：

open Base
open Core_bench

let create_maps ~num_keys ~iterations =
  let rec loop i map =
    if i <= 0
    then []
    else (
      let new_map =
        Map.change map (i % num_keys) ~f:(fun current ->
            Some (1 + Option.value ~default:0 current))
      in
      new_map :: loop (i - 1) new_map)
  in
  loop iterations (Map.empty (module Int))

let create_tables ~num_keys ~iterations =
  let table = Hashtbl.create (module Int) ~size:num_keys in
  let rec loop i =
    if i <= 0
    then []
    else (
      Hashtbl.change table (i % num_keys) ~f:(fun current ->
          Some (1 + Option.value ~default:0 current));
      let new_table = Hashtbl.copy table in
      new_table :: loop (i - 1))
  in
  loop iterations

let tests ~num_keys ~iterations =
  let t name f = Bench.Test.create f ~name in
  [ t "table" (fun () -> ignore (create_tables ~num_keys ~iterations))
  ; t "map" (fun () -> ignore (create_maps ~num_keys ~iterations))
  ]

let () =
  tests ~num_keys:50 ~iterations:1000
  |> Bench.make_command
  |> Command_unix.run

不出所料，在这个基准测试中，映射远胜哈希表，这里超过 10 倍：

(executable
  (name      map_vs_hash2)
  (libraries core_bench core_unix.command_unix))

$ dune build map_vs_hash2.exe
$ ./_build/default/map_vs_hash2.exe -ascii -clear-columns time speedup
Estimated testing time 20s (2 benchmarks x 10s). Change using -quota SECS.

  Name      Time/Run   Speedup
 ------- ------------ ---------
  table   4_453.95us     25.80
  map       172.61us      1.00

这些数字可以通过增加表大小或列表长度变得更极端。

可以看到，树和映射的相对性能很大程度上取决于它们如何被使用的细节，因此选择哪一种数据结构，也要取决于应用本身的细节。