functional-programming - `val hash : 'a -> int` 是如何在 OCaml 中实现的？

Question

在 OCaml 中，Hashtbl可以hash对 int 进行任何操作

Hashtbl.hash x 将非负整数与任何类型的任何值相关联。保证如果 x = y 或 Pervasives.compare xy = 0，则哈希 x = 哈希 y。此外，哈希总是终止，即使在循环结构上也是如此。

我的意思是，对于每个返回整数的对象Java，我们都有，Java 的 Hashtable 可以散列该整数。hashCode()

但是 OCaml 是如何实现散列的呢？

Answer 1

这并不棘手。Hashtbl.hash只是以类似于垃圾收集器的方式遍历数据。它在链接结构中行进固定距离，从而避免在有循环时失败。它对所遇到的高级类型一无所知，它只是散列它所达到的原始值。

您可以在 OCaml 源代码分发中看到 byterun/hash.c 中的代码。

更新

我突然想到你可能一直在问OCamlHashtbl.hash是如何实现的。答案是它不能在 OCaml 中实现（没有作弊），因为它违反了参数化。唯一可能的纯函数类型是返回常量值的函数。直觉是这样的函数不能使用关于其参数的任何信息，因为它是为所有可能的类型定义的。'a -> int

Hashtbl.hash是少数违反参数性的 OCaml 函数之一。它们存在于 OCaml 中是因为它们非常方便。另一个臭名昭著的是多态比较compare（和相关的=运算符）。