Portable hash

Portable hash

[Dawid Toton]

I'm looking for a way to calculate hashes of values of variuos types. It 
has to be:
1. proper function (i.e. x=y => (hash x)=(hash y) )
2. and should not change with a platform or compiler version.
3. It'd also help to have practically no collisions.

For some time I needed not to move data across machines and what I have 
been (wrongly) using for this so far is:
let hash x =  Digest.string (Marshal.to_string x [])

Recently I realized that it's incorrect as Marshal.to_string is not pure 
function and doesn't satisfy my first requirement. Indeed in some very 
rare cases I got different results from the same value. Only the 3rd 
point is satisfied very well.

I have to change my function before I run into problems and I'm considering:
1) Small hashes:

 let hash x =  |Hashtbl.hash_param large_int large_int x

Does anybody know what are properies of | |Hashtbl.hash_param? I mean: 
is the implementation stable? Can I have good distribution when all the 
data is examined (large parameters)?

Unfortunately it returns int of platform-dependent length (and even 
platform-depentent less significant bits of result?). How hard would it 
be to tailor it to, say, work always with 31 bits?
||
2) To serialize values with Sexp:

let hash to_sexp x = Digest.string (string_of_sexp (to_sexp x))
|
|This way I have the stablility because I can just keep implementation 
of Sexp untouched. But the performance is going to be even worse than 
with my original solution.|

Has anybody solved already this (or similar) problem?

Dawid Toton

Re: [Caml-list] Portable hash

[Florent Monnier]

> How hard would it
> be to tailor it to, say, work always with 31 bits?

Hashtbl.hash will return a 31 bit integers on both 32 or 64 architectures:

file: ocaml-3.10.2/byterun/hash.c

CAMLprim value caml_hash_univ_param(value count, value limit, value obj)
{
 [...]

  return Val_long(hash_accu & 0x3FFFFFFF);
  /* The & has two purposes: ensure that the return value is positive
     and give the same result on 32 bit and 64 bit architectures. */
}

# max_int (* the 31 bit one *) = 0x3FFFFFFF ;;
- : bool = true

> 2. and should not change with a platform or compiler version.
If you wish to get a code that won't change for a futur ocaml version, just 
extract the current hash function of ocaml to include it in your own code.
You can do this because the code of the stdlib is LGPL.
____________

currently I have some problems with Hashtbl.hash because it doesn't hash 
values of kind integers, so if (x = y + 1) I get ((hash x) = (hash y) + 1) 
which results in a poor repartition.

Does someone know how to hash an integer ?
Here there are hashing functions for integers:
- http://www.concentric.net/~Ttwang/tech/inthash.htm
- http://burtleburtle.net/bob/hash/integer.html
but they are for 32 bit unsigned integers.
How can I adapt it for 31 bit integers ?

Or would it be a good solution to convert the bits of the integer to a 
bool list and then give it to Hashtbl.hash ?
At least with this solution I haven't ((hash x) = (hash y) + 1) anymore.