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

[Kuba Ober <ober.14@osu.edu>]

On Friday 11 January 2008, David Allsopp wrote:
> Kuba Ober wrote:
> > On Friday 11 January 2008, Jon Harrop wrote:
> > > On Friday 11 January 2008 13:30:29 Kuba Ober wrote:
> > > > Are those collisions of any real importance? I mean, do they break
> > > > anything? If all they do is imply linearly searching a list of a few
> > > > elements, for the colliding entry, then it's a non-issue?
> > >
> > > It would prevent code from compiling so it would be a complete
> > > show-stopper.
> >
> > So what you're saying is that the implementation uses the hash with
> > bucket
> >
> > size of 1? That's kinda poor decision, methinks.
>
> I think you're missing the context - there's no hash table. See 18.3.6 in
> the manual - the hashed values (and resulting collisions) are to do with
> the internal representation of polymorphic variants.
>
> The compiler cannot process code that uses two polymorphic variants whose
> tag names will have the same internal representation (and therefore be
> incorrectly viewed as having the same value). The test is probably
> performed somewhere in the type checker...

Yeah, I sort of put the wagon ahead of the horse. Of course the hashing 
function doesn't imply a hash table.

What I meant was simply that instead of using some fixed hash function, one 
could use a perfect hashing function which is optimal for its known set of 
inputs, and won't ever generate a collision.

The tables that such a function uses to hash its input have to be generated at 
link-time, which means run-time too.

Cheers, Kuba