Re: [Caml-list] Hashing failure

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

On 2012/12/21, at 5:18, Thomas Braibant <thomas.braibant@gmail.com> wrote:

> Hi list,
> 
> I have a piece of code that looks like this.
> 
> let hkey = H.hash d in (* a custom hash function *)
> let index = hkey mod (Array.length t.table) in
> let bucket = t.table.(index) in (* 1 *)
> 
> the line marked with 1 was generating an index out of bounds
> exception. It appeared that it was because index was negative, a
> problem  I knew of when using mod ... So I added an abs around index
> 
> let hkey = H.hash d in
> let index =  abs (hkey mod (Array.length t.table)) in
> let bucket = t.table.(index) in (* 1 *)
> 
> But it yields the same exception...
> 
> This seemed completely unbelievable, till I realized that
> - x mod y may return a negative value if x is less than 0
> - abs x may return a negative value if x is min_int

What about just ensuring that your hash function returns a positive
value to start with.
An easy way to do that is

   let hkey = hkey land max_int

This avoids using abs altogether.
(I now understand why the standard hash function is 30-bit…)

	Jacques Garrigue