From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 7CC917EE79 for ; Sat, 23 Apr 2016 19:22:27 +0200 (CEST) IronPort-PHdr: 9a23:sZpINBcbJw4Eh3HP3UtqYipIlGMj4u6mDksu8pMizoh2WeGdxc+6Zx7h7PlgxGXEQZ/co6odzbGG4+a/AydZuM3JmUtBWaIPfidNsd8RkQ0kDZzNImzAB9muURYHGt9fXkRu5XCxPBsdMs//Y1rPvi/6tmZKSV3BPAZ4bt74BpTVx5zukbviq9uMOU4R3WH1SIgxBSv1hD2ZjtMRj4pmJ/R54TryiVwMRd5rw3h1L0mYhRf265T41pdi9yNNp6BprJYYAu3SNp41Rr1ADTkgL3t9pIiy7UGCHkOz4S43Un8XiQZPGwjIpCvzUJn4ti/7/r5W2DObJtHxVbA5Hw6r4aliTBvpoDoBNiB862jJjc19yqxB9kGPvRt6lqHZeo3dD+Z5ervYdNUcDT5AWMhWfyNMGI/5dJcIC/IENOBe6YXw8Qhd5SCiDBWhUbu8ggRDgWX7iOhji7ws Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=info@gerd-stolpmann.de; spf=None smtp.mailfrom=info@gerd-stolpmann.de; spf=None smtp.helo=postmaster@mout.kundenserver.de Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of info@gerd-stolpmann.de) identity=pra; client-ip=212.227.17.24; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="info@gerd-stolpmann.de"; x-sender="info@gerd-stolpmann.de"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of info@gerd-stolpmann.de) identity=mailfrom; client-ip=212.227.17.24; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="info@gerd-stolpmann.de"; x-sender="info@gerd-stolpmann.de"; x-conformance=sidf_compatible Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mout.kundenserver.de) identity=helo; client-ip=212.227.17.24; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="info@gerd-stolpmann.de"; x-sender="postmaster@mout.kundenserver.de"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0DAAAAYrhtXkBgR49RehAt9u3UehXACgR88EAEBAQEBAQEBEQEBAQEHDQkJIS+CLYIUAQEBAwEnLiQFCwsYLlcGEwmIGQwBCb84AQEBAQEFAQEBARQIhSmFQ4RKhUsFh3SQG4E0AoxegWaHTwSFV4YjiQw3gi8SCoFNagGIegEBAQ X-IPAS-Result: A0DAAAAYrhtXkBgR49RehAt9u3UehXACgR88EAEBAQEBAQEBEQEBAQEHDQkJIS+CLYIUAQEBAwEnLiQFCwsYLlcGEwmIGQwBCb84AQEBAQEFAQEBARQIhSmFQ4RKhUsFh3SQG4E0AoxegWaHTwSFV4YjiQw3gi8SCoFNagGIegEBAQ X-IronPort-AV: E=Sophos;i="5.24,523,1454972400"; d="asc'?scan'208";a="175542104" Received: from mout.kundenserver.de ([212.227.17.24]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 23 Apr 2016 19:22:26 +0200 Received: from office1.lan.sumadev.de ([188.107.80.127]) by mrelayeu.kundenserver.de (mreue103) with ESMTPSA (Nemesis) id 0LjcUK-1bQs6i462K-00bYr7; Sat, 23 Apr 2016 19:22:25 +0200 Received: from [192.168.65.10] (unknown [192.168.65.10]) by office1.lan.sumadev.de (Postfix) with ESMTPSA id 322AADC05D; Sat, 23 Apr 2016 19:22:24 +0200 (CEST) Message-ID: <1461432138.26469.178.camel@e130.lan.sumadev.de> From: Gerd Stolpmann To: Christophe Raffalli Cc: caml-list@inria.fr Date: Sat, 23 Apr 2016 19:22:18 +0200 In-Reply-To: <20160423154132.GB1455@delli7.univ-savoie.fr> References: <20160423091630.GA25686@delli7.univ-savoie.fr> <1461410500.26469.167.camel@e130.lan.sumadev.de> <20160423154132.GB1455@delli7.univ-savoie.fr> Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="=-jIosbhnXn6Svg6UIm7os" X-Mailer: Evolution 3.10.4-0ubuntu2 Mime-Version: 1.0 X-Provags-ID: V03:K0:3jhcrd86bCylSGUK6N4rvoV1d7HXREZZOY1EFUoj5hq5UVwCzcy r9z794WKFL8NaNC7Pk2HzCyrZvBQuodTkNj9QN+RLDaqBKn5CXnUbU1Ddvn2pxcE2ew0t+R 1QuZJQVsjBsh4EE5bzdH6NN62BJ2+IydO4yEnbgIJA4PSDo5XnF4bw9154Wukv/qkzDzEzq NKvyi2ae+O4WvhW7meyTg== X-UI-Out-Filterresults: notjunk:1;V01:K0:UIT+tziDrLU=:Tfil7/bzMd7g7IXhBe4uwk wnN/x5BJFKDPQVceezbJQ+whM0tKK+n9nmm2rv7skSGmv6PC8YXhpDdSLMEaB08jyRvxgvIYd tu8GASMJR7arwy76c0+bzqyXSyQOTkC+Hs6dXMkAKLsZxf58Jfc1K3Ifh2ziHZvRzAKfOjosM r1xKs+3pfpfWgs04nDlNu8qyIGbytsX4QrwtQpihLT5eek+in/9iSh4JYihwQIrkg/tElTIHW RxJBA0p9IeOqkwh/+KO8rpuC+scDyObfT9zRfTRIjtsAoFj+upEmbNypfKm2f1wMSjAygc9gT LLanYpSEMBGFivf2GJjkvL9gLop4MKWeevDC/q6r/GCqAhOTguu5siAunie1PKvi5quUBBMYY VC//JQMZTP9DIJ7dxw17cjbJLU+6w7XMuJoNTo873Mu88ukXjQDY/H6WbsDr0K33SLrURtLo/ 0uAQ34aaAyEqvICk/tDZdxo7VHIZLuyIlE6nJh1n4llwIuecAyL0SXivgLkhfIkWXGObIXkm4 ZKzofM6vok43s3pxg22Vf16uw8UNIc60ilveFRxDF/W1eKwzGwOoddU32d08dV53mEV5oXIan LF8BBVyf4BS0Zm7SMarOjQonkmdJRD6YHjShWMpdv8DhwBlhL9/BdKFyQaGC1QLqw64SOC1F8 Yj34+2rf8AoLkDUciNBbOdDIDhQHRsWHiteii386j6gLgfZysp0fkozjOGFc7A+7Efhs= Subject: Re: [Caml-list] ocaml defaut hash ? --=-jIosbhnXn6Svg6UIm7os Content-Type: text/plain; charset="ISO-8859-15" Content-Transfer-Encoding: quoted-printable Am Samstag, den 23.04.2016, 17:41 +0200 schrieb Christophe Raffalli: > 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. >=20 > Hello, >=20 > xor or + was not enough and it does not have to be commutative. Well, you need to be able to "subtract" the hash of the old version somehow from the aggregate hash. Well, algebra was a long time ago. > I tried >=20 > let hash_array a =3D > let r =3D ref 0 in > Array.iteri (fun i x -> r :=3D !r lxor Hashtbl.hash (i,x)) a; > !r >=20 > Which works not to bad ... but some small hash value (below 10, after > moduli) seems to come too often ... Instead of (i,x) you could also use any function of these. If you can spend some RAM: Let's rnd(i) the i-th random number of a memorized sequence. The hash of the i-th element is then hash(rnd(i)*x). You could also use another operation instead of * but multiplication is fairly cheap, and "mangles" already a lot. If you want to spend more time, hash(rnd(i)*x mod p) for a large prime p (instead of the implicit modulus 2^31/2^63), because the set of values is largest with a primal modulus. > > 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. >=20 > 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. >=20 > 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=E9ro padding (making xor no sufficient) I think when you make the element hash dependent on the position i you get exactly this property, even with xor. Gerd > - covering all range of caml integer as usual >=20 >=20 > > 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 > > ------------------------------------------------------------ > > --=20 ------------------------------------------------------------ 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 ------------------------------------------------------------ --=-jIosbhnXn6Svg6UIm7os Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 iQEcBAABAgAGBQJXG69KAAoJEAaM4b9ZLB5TiUwIAIjuAbL4FmsbAT74jlVFQnVI ouKhfWxj2P4esfhaQizMX2xXVPWNFZVNKvGpxi4/ALsXwjKFLv/s5dJNJIX3L8fH 0jxrOfDH1KE+m8WB/skHcUXYbsYqCFFr2orUeAb036RMXSI1yeVPNKd7CC+c28yy +tWfPgESn04UZdASez0DlQlPBtKF3SL+GdAw0jIXEUJemQQHquSNDhJQRcRTjrpD MTSv/TPlHOLo0zb6WSI4b43jUiQmPr1JnhGw6oIPdDcwl4G7cYaI1rNvGU9Kpni7 nfnP+QUw8nKOFm6oRhmFCLFvAed9cvyrp70LzU1nGaplVNcVbmFyCxSACXG1O1E= =Ec5X -----END PGP SIGNATURE----- --=-jIosbhnXn6Svg6UIm7os--