Ocaml 哈希表中的相等性

Question

Ocaml 中是否有哈希表在测试键相等时使用 == 而不是 = ？ 例如：

# type foo = A of int;;
# let a = A(1);;
# let b = A(1);;
# a == b;;
- : bool = false
# a = b;;
- : bool = true
# let h = Hashtbl.create 8;;
# Hashtbl.add h a 1;;
# Hashtbl.add h b 2;;
# Hashtbl.find h a;;
- : int = 2
# Hashtbl.find h b;;
- : int = 2

我想要一个可以区分 a 和 b 的哈希表。这可能吗？

Answer 1

您可以使用自定义哈希表：

module H = Hashtbl.Make(struct
  type t = foo
  let equal = (==)
  let hash = Hashtbl.hash
end)

然后在代码中使用 H 而不是 Hashtbl。

Answer 2

托马斯和卡戈的答案中的解决方案在功能上是正确的。如果您按原样使用他们的解决方案，可能会困扰您的一个问题是，如果您散列许多对于 (=) 相等而对于 (= 不同的键，您将遇到比预期更多的冲突=)。事实上，对于 (=) 来说，所有相等的键都具有相同的 Hashtbl.hash 哈希值，并且最终位于同一个存储桶中，在那里它们被识别为不同的 (因为您要求将 (==) 用作相等函数）并创建不同的绑定。在最坏的情况下，哈希表的行为与关联列表具有相同的复杂性（顺便说一下，这是您可以使用的另一种数据结构，然后您不必担心提供哈希函数）。

如果您可以接受偶尔更改的值的键（因此无法从哈希表中检索该值，因为绑定位于错误的存储桶中），则可以使用以下低级函数作为哈希：

external address_of_value: 'a -> int = "address_of_value"

已实现在 C 中为：

#include "caml/mlvalues.h"

value address_of_value(value v)
{
  return (Val_long(((unsigned long)v)/sizeof(long)));
}

然后您将使用：

module H = Hashtbl.Make(struct
  type t = foo 
  let equal = (==) 
  let hash = address_of_value
end);;