Re: [Caml-list] Hash function: complexity and circular structures

[Nicholas Lucaroni <nicholas.r.lucaroni@gmail.com>]

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

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<https://sympa.inria.fr/sympa/arc/caml-list>
> Beginner's list: http://groups.yahoo.com/group/**ocaml_beginners<http://groups.yahoo.com/group/ocaml_beginners>
> Bug reports: http://caml.inria.fr/bin/caml-**bugs<http://caml.inria.fr/bin/caml-bugs>
>

[-- Attachment #2: Type: text/html, Size: 7294 bytes --]