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

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

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

You should update to OCaml 4.xx I don't think the hash function works at
all on lists in 3.12.1 (in the sense that it, as you've found, it always
returns 0).

in ocaml 4.00+rc1
# Hashtbl.hash (6 :: 7 :: 8 :: 9 :: 10 :: 11 :: 12 :: 13:: 14 :: 15 :: []);;
- : int = 418135511

in ocaml 3.12.1
# Hashtbl.hash (6 :: 7 :: 8 :: 9 :: 10 :: 11 :: 12 :: 13:: 14 :: 15 :: []);;
- : int = 0



On Thu, Jan 17, 2013 at 11:41 AM, Edgar Friendly <thelema314@gmail.com>wrote:

> The source is quite easy to read, and is available here:
>
> https://github.com/ocaml/ocaml/blob/trunk/byterun/hash.c
>
> It turns out that even seeded MurmurHash3 does not prevent algorithmic
> attacks as expected, as demonstrated and explained at 29c3:
> http://events.ccc.de/congress/2012/Fahrplan/events/5152.en.html and
> www.youtube.com/watch?v=Vdrab3sB7MU.
>
> E.
>
>
> On Thu, Jan 17, 2013 at 10:46 AM, Nicholas Lucaroni <
> nicholas.r.lucaroni@gmail.com> wrote:
>
>> 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: 8961 bytes --]