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

Question

在OCaml中,任何事情Hashtbl都可以hash转为int

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

我的意思是,在Java我们拥有hashCode()了它返回一个整数和Java的哈希表可以散列该整数每个对象.

但OCaml是如何实现这一点的呢？

Answer 1

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

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

更新

在我看来你可能一直在问OCaml是如何Hashtbl.hash实现的.答案是它无法在OCaml中实现(没有作弊),因为它违反了参数.唯一可能的纯函数类型'a -> int是返回常量值的函数.直觉是这样的函数不能使用有关其参数的任何信息,因为它是为所有可能的类型定义的.

Hashtbl.hash是一些违反参数的OCaml函数之一.它们存在于OCaml中,因为它们非常方便.另一个臭名昭着的是多态比较compare(以及相关的=运算符).