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

[Edgar Friendly <thelema314@gmail.com>]

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

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: 8018 bytes --]