Re: [Caml-list] Hash clash in polymorphic variants

[Eric Cooper <ecc@cmu.edu>]

On Thu, Jan 10, 2008 at 05:09:13PM +0000, Jon Harrop wrote:
> 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?

I don't think it's worth worrying about.

I wrote a program a while ago to look into this.  I never saw any
"human-sensible" collisions (between two identifiers that a person
might have chosen). And if you're producing gensyms in a program, you
can just check ahead of time.

To find a collision with a given identifier, consider each bignum N
that differs by a multiple of 2^31 from the identifier's hash value.
Compute the radix-223 representation of N.  If that forms a legal
OCaml identifier, then you've found a collision.

For example, Eric_Cooper collides with azdwbie, c7diagq, hlChrkt,
NSaServ, and SaupDOF, to pick just a few.

-- 
Eric (call me SaupDOF) Cooper             e c c @ c m u . e d u