Deterministic hashing

Learning
1

I have been using Hashtbl.hash to generate unique ids from a certain datatype in my program. The problem with this is that between runs of the program the same input yields a different hash. This causes cram tests to fail even when the program hasn’t changed.

Is it possible to use Hashtbl.seeded_hash for this purpose? The docs say that the function “is further parametrized by an integer seed” (emphasis mine), so assume I will see the same nondeterministic behavior.

I have already come up with an alternative solution that is particular to my application but from an architectural perspective using a hash-like function is much cleaner.

Eager to hear any suggestions. Thanks!

2

This is surprising because, according to the code Hashtbl.hash calls Hashtbl.seeded_hash with a fixed seed of 0.
But looking at caml_hash everything (for a fixed seed) should be deterministic, unless the data structure you hash contains closures. In this case the code pointer is part of the hash and may yield different results for different runs. Or if you are using objects, then their internal id is used for the hash, but their internal id may change depending on creation order.

Edit : the following shows that the issue might indeed be code pointer used in hash + ASLR :

let f x y = x + y

let () = Format.printf "%d\n%!" (Hashtbl.hash f)


$ ocamlopt foo.ml
$ ./a.out; ./a.out; ./a.out
545623849
393380115
243345998
$ setarch -R  ./a.out ; setarch -R ./a.out ; setarch -R ./a.out 
1014361679
1014361679
1014361679
3

Converting to a string and using the digest module might suffice? The data structure is not the issue.

4

A faulty assumption on my end may be that the data structures I am passing in are really the same between runs of the program. It is hard to verify if there is nondeterminism here, but this seems increasingly likely to me.

5

Since you raise this question in the context of automated testing, I assume that you’ll want the hashes to be consistent across revisions to the standard library? In general, a hash function interface that doesn’t promise to be stable for all eternity won’t be.

A good fingerprint function is one that has a fixed specification, and the hashes found in the Digest module seem like they qualify. Duff also appears to implement Rabin’s algorithm.