Version française
Home     About     Download     Resources     Contact us    
Browse thread
Hash clash in polymorphic variants
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jacques Garrigue <garrigue@m...>
Subject: Re: [Caml-list] Hash clash in polymorphic variants
From: Jon Harrop <jon@ffconsultancy.com>

> ISTR advice that constructors sharing the first few characters should be 
> avoided in order to reduce the likelihood of clashing hash values for 
> polymorphic variants. Is that right?

Not at all. If the first characters are identical it just means that an
identical value will be added to the hashes of the suffixes, which
actually means that you lower the probability of getting conflicts :-)
The hash functions guarantees that all keys of strictly less than 5
characters will map to different.

The probability of getting clashes being really low, you should not be
concerned by this. Just check aferwards. A simple way to do it is to
produce a big type containing all the tags, and feed it to ocamlc.

> I'm interested in automatically translating the GL_* enum from
> OpenGL into polymorphic variants. So although it is generated code I
> have little control over it, e.g. I cannot change the translation as
> OpenGL gets extended because code will already be using the existing
> names.

In the event you get a conflict when openGL is extended, you can still
add a special case for the newly added tags. I hope this does not
happen, but the birthday theorem tells you that when you get enough
participants, clashes are hard to avoid.

Cheers,

Jacques Garrigue