Hash function improvements

ocaml / Zarith

The Zarith library implements arithmetic and logical operations over arbitrary-precision integers and rational numbers. The implementation, based on GMP, is very efficient.

Other

231 stars 70 forks source link

Hash function improvements #145

Closed vouillon closed 10 months ago

vouillon commented 1 year ago

make sure that the hash of zero is not 0
finalize the hash and fold the result to a positive 31-bit integer

xavierleroy commented 1 year ago

I could use more context:

What's wrong with zero hashing to 0 ?
Is it intended that Z.hash x should be equal to Hashtbl.hash x? I'm not sure this is the case even with the proposed patch, as an extra mixing with 0 seems to be missing.

Clarifications welcome!

vouillon commented 1 year ago

My initial motivation was to harmonize hash results over 32-bits architectures (between zarith_stubs_js and zarith C stubs).

Beside that:

I don't really care about zero hashing to 0. I can special-case zero in zarith_stubs_js instead.
It probably makes sense that Z.hash returns a positive integer, since this is less error-prone, and that it returns the same result on all architectures. For this, anding with 0x3FFFFFFF should be sufficient.
It might be nice that Hashtbl.hash and Z.hash coincide. But I got this wrong...

xavierleroy commented 1 year ago

My initial motivation was to harmonize hash results over 32-bits architectures

Agreed. Let's do that.

I don't really care about zero hashing to 0. I can special-case zero in zarith_stubs_js instead.

I still don't understand why a special case is needed for zero...

It might be nice that Hashtbl.hash and Z.hash coincide. But I got this wrong...

If we really want this identity, we can just define Z.hash as Hashtbl.hash + a type constraint, like we do in the OCaml stdlib for String.hash, Int32.hash, etc. While we're at it, we could also define Z.seeded_hash. I'm tempted!

xavierleroy commented 10 months ago

After thinking some more about it, I believe Z.hash should be an alias for the standard hash function Hashtbl.hash, like we do for other standard library modules that work with integers (Int, Int32, Int64, Nativeint). See #150 for more details.