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: Eric Cooper <ecc@c...>
Subject: Re: [Caml-list] Hash clash in polymorphic variants
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