'val hash'如何：'a - > int`在OCaml中实现？ [英] How was `val hash : 'a -> int` was implemented in OCaml?

问题描述

在OCaml中， Hashtbl 可以散列任何东西到一个int

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

我的意思是，在 Java hashCode（），Java的Hashtable可以散列那个整数。

但是OCaml是如何实现这个功能的呢？

解决方案

这并不麻烦。 Hashtbl.hash 只是以类似于垃圾回收器的方式遍历数据。它以固定的距离进入链接结构，避免在有循环时失效。它不知道任何有关它遇到的高级类型，它只是散列它到达的原始值。

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

更新

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

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

In OCaml, Hashtbl can hash any thing to an int

Hashtbl.hash x associates a nonnegative integer to any value of any type. It is guaranteed that if x = y or Pervasives.compare x y = 0, then hash x = hash y. Moreover, hash always terminates, even on cyclic structures.

I mean, in Java, we have hashCode() for every object which returns an integer and Java's Hashtable can hash that integer.

But how did OCaml achieve that to hash anything?

解决方案

It's not tricky. Hashtbl.hash just traverses data in a manner similar to the way the garbage collector does it. It travels a fixed distance into the linked structure, which avoids failing when there are cycles. It doesn't know anything about the high-level types of what it encounters, it just hashes the primitive values it reaches.

You can see the code in byterun/hash.c in the OCaml source distribution.

Update

It occurs to me you might have been asking how Hashtbl.hash was implemented in OCaml. The answer is that it can't be implemented in OCaml (without cheating) because it violates parametricity. The only possible pure functions of type 'a -> int are ones that return a constant value. The intuition is that such a function can't use any information about its argument because it is defined for all possible types.

Hashtbl.hash is one of a few OCaml functions that violate parametricity. They exist in OCaml because they're extremely handy. Another notorious one is the polymorphic comparison compare (and the associated = operator).

这篇关于'val hash'如何：'a - > int`在OCaml中实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！