Happy Happy Joy Joy (was: On to Hydro)

[Tyler Close]

Jonathan Shapiro wrote:
> > My RedBlackTree does use a configurable comparison
> predicate (where
> > this whole thread started from), but my Hashtable does
> not support a
> > separate hashing function. Could you explain why you
> would want one?
>
> One explanation is that I may know something about the
> distribution of hash
> values or the number of entries I plan to insert that leads
> me to want to
> specify both a hash function and a number of buckets.

I see specifying the number of buckets to start with as a separate
issue from specifying the hash function. My Hashtable actually forces
you to always specify the initial bucket count at construction time
(either directly, or indirectly).

My Hashtable has been implemented such that it copes very well with
poorly distributed hash codes (excepting the case where all hash codes
are identical). I doubt you'd ever have need to try to do better with
a custom hash function.

> Another is that I may wish to hash based on the value of
> the object (using
> some suitable universaly deterministic function) rather than on it's
> identity -- this is currently done in DCMS, in fact.

In a persistent programming language, there is no difference between
these two cases. The hash code is always calculated based on the value
of the immutable key object. The reference to a mutable object can be
thought of as, and is implemented as, an immutable token identifying
the object. When you insert the reference into a hashtable, you are
actually inserting this immutable token.

> For content-based hashes, however, the hash function should
> certainly be
> user selectable.

I don't see a reason to support multiple hash codes, and it's
certainly possible for the runtime to generate a good hash of the
object's value.

Tyler


_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com