Re: [Caml-list] hashing big ints

[Goswin von Brederlow <goswin-v-b@web.de>]

Damien Pous <Damien.Pous@inria.fr> writes:

> Dear caml-list,
>
> Let me re-raise an apparently old and possibly dumb question : how to
> hash big ints ?
>
> Hashtbl.hash doesn't work (ocaml 3.12.1):
>
> # Hashtbl.hash (Big_int.big_int_of_int 42);;
> - : int = 1
> # Hashtbl.hash (Big_int.big_int_of_int 33);;
> - : int = 1
>
> (Certainly because big ints hide their content in custom blocks.)
>
> I found several discussions about this kind of problem (comparison of
> nums, etc...), which were more focused on how to let
> Pervasive.compare/equal and Hashtbl.hash behave correctly in a uniform
> way.
>
> My question is simpler : I just need to write my own hashing function,
> so that I can call Hashtbl.Make. I currently use something like:
>
> let rec hash x =
>   try int_of_big_int x
>   with _ -> hash (shift_right_big_int x Sys.word_size)
>
> Some of you certainly know how to get a better behaved function. (I
> don't know anything about hashing theory, except that my function is
> certainly not a good one: it doesn't contain any prime number...)
>
> Thanks for your help,
> Damien

A usualy good hash function for integers is to take the integer modulo a
prime number. This usualy results in an uniform distribution. So:

let big_prime = (big_int_of_int prime)
let hash x = mod_big_int x big_prime

We also want the output range of the hash function to be as large as
possible to minimize the number of collision. That means we want the
prime to be as big as possible. And there we hit a little snag. For best
results you want a different prime number for 32bit and 64bit systems.
Lookup the closest prime number smaller than 2^32 and 2^64 and use
those.

Note: It is too bad there isn't a mod_big_int_with_int or even better a
Big_int.hash function directly. Maybe you could write one that takes
advantage of knowing the internal structure of Big_int?

MfG
        Goswin