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

["David Allsopp" <dra-news@metastack.com>]

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...

An alternative implementation might have been to lookup the tags (in a
perfect hash table) using a system similar to caml_named_value but I imagine
that the present method was preferred because it's simpler (and quite
possibly faster) and collisions are rare (as Eric pointed out) - although in
Jon's case the lack of a guarantee is unfortunate.

Incidentally, and off-the-subject here, using a hash table with a bucket
size of 1 is very important if you need performance guarantees on your hash
table and have some other way of coping with collisions.


David