Re: [Caml-list] ocaml defaut hash ?

[Christophe Raffalli <Christophe.Raffalli@univ-savoie.fr>]

[-- Attachment #1: Type: text/plain, Size: 1908 bytes --]

On 16-04-23 13:21:40, Gerd Stolpmann wrote:
> Am Samstag, den 23.04.2016, 11:16 +0200 schrieb Christophe Raffalli:
> > By the way what I really need is a hash function for arrays that I can
> > update when I update one entry in the array.  Does anyone known of
> > such a hash function ?
>
> It would have to be commutative then (you need to remove the old version
> and add the new one, for any element for the array). You could use XOR
> or + of the hashes of the individual elements.

Hello,

xor or + was not enough and it does not have to be commutative.

I tried

let hash_array a =
  let r = ref 0 in
    Array.iteri (fun i x -> r := !r lxor Hashtbl.hash (i,x)) a;
      !r

Which works not to bad ... but some small hash value (below 10, after
moduli) seems to come too often ...

> If this doesn't work good enough, I'd try to define larger hash blocks.
> E.g. consider 4 consecutive elements as a block, and compute the hash of
> the block, and take the XOR of all blocks you have.

This is already done. My array is in fact a packed array of values that
can be represented on few bits, implemented cleanly via a functor.

The property I would like if you think that the array is a 2 dimensional bitmaps are
- the hash changes when any bit changes
- the hash changes for all (most) translation at angle multiple of pi/4
with zéro padding (making xor no sufficient)
- covering all range of caml integer as usual


> Quality depends a
> little bit on what is in the elements.
>
> Gerd
> --
> ------------------------------------------------------------
> Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
> My OCaml site:          http://www.camlcity.org
> Contact details:        http://www.camlcity.org/contact.html
> Company homepage:       http://www.gerd-stolpmann.de
> ------------------------------------------------------------
>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 181 bytes --]