哈希表

模块 Hashtbl

Hashtbl 模块实现了高效的可变查找表。要创建一个哈希表，我们可以编写

# let my_hash = Hashtbl.create 123456;;
val my_hash : ('_weak1, '_weak2) Hashtbl.t = <abstr>

123456 是哈希表的初始大小。这个初始数字只是您对将放入哈希表的数据量的最佳猜测。如果低估了大小，哈希表可以增长，所以不用太担心。my_hash 的类型是

# my_hash;;
- : ('_weak1, '_weak2) Hashtbl.t = <abstr>

'_weak1 和 '_weak2 分别对应于键和值的类型。这些槽位中没有填充具体的类型（例如，int 或 float * string），因为键和值的类型尚未确定。下划线表示一旦选择，键和数据类型将被固定。换句话说，您不能有时对给定的哈希表使用整数作为键，然后稍后在同一个哈希表中使用字符串作为键。

让我们向 my_hash 添加一些数据。假设我正在开发一个填字游戏求解程序，我想找到所有以特定字母开头的单词。首先，我需要将数据输入 my_hash。

请注意，哈希表通过就地更新进行修改，因此，与映射不同，每次更改表时 *不会* 创建另一个哈希表。因此，代码 let my_hash = Hashtbl.add my_hash ... 没有任何意义。相反，我们会编写类似这样的代码

# Hashtbl.add my_hash "h" "hello";
  Hashtbl.add my_hash "h" "hi";
  Hashtbl.add my_hash "h" "hug";
  Hashtbl.add my_hash "h" "hard";
  Hashtbl.add my_hash "w" "wimp";
  Hashtbl.add my_hash "w" "world";
  Hashtbl.add my_hash "w" "wine";;
- : unit = ()

如果我们想在 my_hash 中找到一个包含 "h" 的元素，那么我们会编写

# Hashtbl.find my_hash "h";;
- : string = "hard"

注意它只返回一个元素？该元素是最后一个以 "h" 的值为输入的元素。

我们可能想要的是所有以 "h" 开头的元素。为此，我们要 *找到所有* 元素。为此，还有什么比 find_all 更好的名字呢？

# Hashtbl.find_all my_hash "h";;
- : string list = ["hard"; "hug"; "hi"; "hello"]

返回 ["hard"; "hug"; "hi"; "hello"]。

如果删除一个键，其先前值将再次成为与该键关联的默认值。

# Hashtbl.remove my_hash "h";;
- : unit = ()
# Hashtbl.find my_hash "h";;
- : string = "hug"

这种行为对于上面的示例或当键表示可以被同名局部变量暂时屏蔽的变量时很有趣。

在其他情况下，人们可能希望新值 *替换* 先前的值。在这种情况下，使用 Hashtbl.replace

# Hashtbl.replace my_hash "t" "try";
  Hashtbl.replace my_hash "t" "test";
  Hashtbl.find_all my_hash "t";;
- : string list = ["test"]

# Hashtbl.remove my_hash "t";
  Hashtbl.find my_hash "t";;
Exception: Not_found.

要查明 my_hash 中是否有一个字母的条目，我们会执行

# Hashtbl.mem my_hash "h";;
- : bool = true