hash - 基于物理身份的替代Hashtbl.hash

Question

我试图派生一个描述结构化值的Graphviz文件。这是出于诊断目的，因此我希望我的图形尽可能接近地反射(reflect)内存中的实际结构。我正在使用下面的方法将值映射到Graphviz顶点，以便当一个值具有两个或多个入站引用时可以重用顶点:

let same = (==)

module StateIdentity : Hashtbl.HashedType = struct
  type t = R.meta_t state
  let hash = Hashtbl.hash
  let equal = same
end

module StateHashtbl = Hashtbl.Make (StateIdentity)

Hashtbl.hash的文档表明，它既适用于 StateIdentity.equal = (=)，也适用于 StateIdentity.equal = (==)，但我想确保哈希表访问尽可能地接近O(1)，因此，宁可不要让 Hashtbl.hash走一个(可能很大)。这种情况)在每次查找中都包含对象图。

我知道Ocaml会移动引用，但是Ocaml中是否有O(1)代理可用于引用身份？

Hashtable of mutable variable in Ocaml的答案表明不是。

我不愿意在状态上附加序列号，因为这是诊断代码，因此我所做的任何错误都有可能掩盖其他错误。

Answer 1

如果从OCaml的< ... >对象类型的意义上使用“对象”一词，则可以使用Oo.id为每个实例获取唯一的整数标识。否则，“是否存在值(value)标识的通用代理”的答案为“否”。在这种情况下，我的建议是从Hashtbl.hash开始，评估它是否适合您的需求，否则设计您自己的哈希函数。

您还可以使用Hashtbl.hash_param(请参阅documentation)来在散列期间打开值遍历的旋钮。请注意，Hashtbl代码使用链接列表存储相同哈希值的存储桶，因此，如果存在很多哈希冲突，则会触发线性搜索行为。最好将其他使用二进制搜索树的实现用于冲突桶。但话又说回来，您应该评估自己的情况，然后再转向更复杂的解决方案(在“好的情况下”具有较差的性能)解决方案。