Re: [Caml-list] Hashing failure

[Xavier Leroy <Xavier.Leroy@inria.fr>]

On 12/20/2012 09:18 PM, Thomas Braibant wrote:

> [Reducing a hash value to a [0, N) interval ]
> My question is : is there a safe way to bullet-proof my code against
> these pathological cases, without too much hinderance (this is some
> code whose efficiency is critical...)

Some possibilities to reduce an integer k to the interval [0, N):

  abs (k mod N)
     (if N > 0, k mod N is guaranteed to be in (-N,N) )

  (k land max_int) mod N
     ("land max_int" masks the sign bit off and preserves all other
      bits, reducing k to [0, max_int])

The latter is a bit more efficient, as it avoids the conditional in "abs".

If N is a power of 2, you can just do

  k land (N - 1)

For hash tables, it is easy to ensure that the size of the array is a
power of 2.  However, the formula above assumes that the low bits of k
have good distribution, which is not always the case if k is computed
with a simple hash function.  You can also "mix up" some of the high
bits before taking the low bits, e.g.

(k lxor (k lsr 16)) land (N - 1)

Hope this helps,

- Xavier