From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by sympa.inria.fr (Postfix) with ESMTPS id 2C5497EEB3 for ; Thu, 17 Jan 2013 16:46:58 +0100 (CET) Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of nicholas.r.lucaroni@gmail.com) identity=pra; client-ip=209.85.216.181; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="nicholas.r.lucaroni@gmail.com"; x-sender="nicholas.r.lucaroni@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail1-smtp-roc.national.inria.fr: domain of nicholas.r.lucaroni@gmail.com designates 209.85.216.181 as permitted sender) identity=mailfrom; client-ip=209.85.216.181; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="nicholas.r.lucaroni@gmail.com"; x-sender="nicholas.r.lucaroni@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail1-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-qc0-f181.google.com) identity=helo; client-ip=209.85.216.181; receiver=mail1-smtp-roc.national.inria.fr; envelope-from="nicholas.r.lucaroni@gmail.com"; x-sender="postmaster@mail-qc0-f181.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgQCALAc+FDRVdi1k2dsb2JhbABEDoI6qHmJPwGJHAgWDgEBAQEJCQsJFAQjgh4BAQQBQAEbEgsBAwELBgULGiEiAREBBQEKEgYTEod0AQMJBgydIYw0gnuEcQoZJwMKWYcoAQUMkSwDiGGNK4EcjUwWKYJRgQhc X-IronPort-AV: E=Sophos;i="4.84,486,1355094000"; d="scan'208";a="190416453" Received: from mail-qc0-f181.google.com ([209.85.216.181]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 17 Jan 2013 16:46:46 +0100 Received: by mail-qc0-f181.google.com with SMTP id x40so1706950qcp.26 for ; Thu, 17 Jan 2013 07:46:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:cc:content-type; bh=Y8nPiLze39cpBpWavGrwJJOo3JPi4GoWxGDEsHghTSA=; b=v4gVI0qUi2uGzulLHzmmWv0N1DXqdCZymYyRPv14bJPSwXEEL8papuKpzoiJ0hc7oB 4WYKt5PBg/z2CoH4U0F3sT4csx+URFC1IB4r/sC32DvDB2fTQ7RmqwLlsz3wgOl+Et0P ju6LphlkF8wJBHqmYgMgTTjQlpa2nnonliuh8REChJbxD9QE/pypwO1DzVkBQcoyt6K6 8HTbwrKsZqCHGd/ZpDW7LvMiTVNiv2SrUUzJriqZ/ard7R4VzqNndRV004aSa131wdzn utzU1IjVNH48fBaBIwJllUqslESmiogA/aBGuzEoMLywfij/ks8G33qFdJKl4/fLK/k6 6KWQ== MIME-Version: 1.0 X-Received: by 10.229.111.220 with SMTP id t28mr1382428qcp.146.1358437605976; Thu, 17 Jan 2013 07:46:45 -0800 (PST) Received: by 10.49.51.136 with HTTP; Thu, 17 Jan 2013 07:46:45 -0800 (PST) In-Reply-To: <50F81A48.4080901@cs.cornell.edu> References: <50F81A48.4080901@cs.cornell.edu> Date: Thu, 17 Jan 2013 10:46:45 -0500 Message-ID: From: Nicholas Lucaroni To: Jean-Baptiste Jeannin Cc: "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=002354471964f42bfc04d37de6f7 Subject: Re: [Caml-list] Hash function: complexity and circular structures --002354471964f42bfc04d37de6f7 Content-Type: text/plain; charset=ISO-8859-1 https://sympa.inria.fr/sympa/arc/caml-list/2011-07/msg00117.html That thread talks about the previous and a better alternative (which is in 4.x). Xavier had said, *The SVN trunk for OCaml contains a complete reimplementation of the* *generic hash function that addresses both issues: lists and other complex keys are traversed breadth-first in a more cautious manner than before, and the mixing functions are based on MurmurHash 3, which exhibits very good statistical properties. All this should go in the next major release 3.13. So, everyone with an interest in efficient hash tables is welcome to try the trunk sources and let me know of any problems encountered.* On Thu, Jan 17, 2013 at 10:35 AM, Jean-Baptiste Jeannin < jeannin@cs.cornell.edu> wrote: > Hello, > > The default OCaml function (Hashtbl.hash) says that it "always terminates, > even on cyclic structures.". I would be curious to know what its complexity > is, both on a finite list and on a cyclic list (created by let rec l = 1 :: > l for example). Is the algorithm that is being used published anywhere? > > Also, this hashing function seems to be returning 0 on any cyclic list (at > least the ones I tried). Is this normal? Does anyone know any better > hashing function on cyclic lists? > > # Hashtbl.hash [ 1 ; 2 ];; > - : int = 131199 > # let rec ones = 1 :: ones;; > val ones : int list = > [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > 1; > 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; > ...] > # Hashtbl.hash ones;; > - : int = 0 > # Hashtbl.hash (5 :: 4 :: ones);; > - : int = 0 > > Thank you, > Jean-Baptiste Jeannin > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa.inria.fr/sympa/**arc/caml-list > Beginner's list: http://groups.yahoo.com/group/**ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-**bugs > --002354471964f42bfc04d37de6f7 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable https://sympa.inria.fr/sympa/arc/caml-list/2011-07/msg00117.html
=
That thread talks about the previous and a better alternativ= e (which is in 4.x).=A0

Xavier had said,
The=A0= SVN=A0trunk=A0for=A0OCaml=A0contains=A0a=A0complete=A0reimplementation=A0of= =A0the
generic=A0hash=A0function=A0that=A0addresses=A0both= =A0issues:=A0lists=A0and=A0other
complex=A0keys=A0are=A0traversed=A0breadth-first=A0in=A0= a=A0more=A0cautious=A0manner
than=A0before,=A0and=A0the=A0mixing=A0functions=A0are=A0= based=A0on=A0MurmurHash=A03,=A0which
exhibits=A0very=A0good=A0statistical=A0properties.=A0=A0= All=A0this=A0should=A0go=A0in=A0the
next=A0major=A0release=A03.13.=A0=A0So,=A0everyone=A0wit= h=A0an=A0interest=A0in=A0efficient
hash=A0tables=A0is=A0welcome=A0to=A0try=A0the=A0trunk=A0= sources=A0and=A0let=A0me=A0know=A0of=A0any
problems=A0encountered.

On Thu, Jan 17, 2013 at 10:35 AM, Jean-Bapti= ste Jeannin <jeannin@cs.cornell.edu> wrote:
Hello,

The default OCaml function (Hashtbl.hash) says that it "always termina= tes, even on cyclic structures.". I would be curious to know what its = complexity is, both on a finite list and on a cyclic list (created by let r= ec l =3D 1 :: l for example). Is the algorithm that is being used published= anywhere?

Also, this hashing function seems to be returning 0 on any cyclic list (at = least the ones I tried). Is this normal? Does anyone know any better hashin= g function on cyclic lists?

# Hashtbl.hash [ 1 ; 2 ];;
- : int =3D 131199
# let rec ones =3D 1 :: ones;;
val ones : int list =3D
=A0 [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1= ; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1; 1;
=A0 =A01; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;= 1;
=A0 =A0...]
# Hashtbl.hash ones;;
- : int =3D 0
# Hashtbl.hash (5 :: 4 :: ones);;
- : int =3D 0

Thank you,
Jean-Baptiste Jeannin

--
Caml-list mailing list. =A0Subscription management and archives:
ht= tps://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners<= /a>
Bug reports: http://caml.inria.fr/bin/caml-bugs

--002354471964f42bfc04d37de6f7--