Happy Happy Joy Joy (was: On to Hydro)

[Tyler Close]

Markm wrote:
> At 01:09 AM 8/24/00 , Tyler Close wrote:
> >It might be better if you think of cryptographic hashs as "message
> >digests", or MACs (Message Authentication Codes), instead of hashs.
> >This makes it clear that there are additional requirements
> for these
> >hashs than for hashtable hashs (requirements that a
> hashtable does not
> >need to meet).
>
> Terminology alert: MACs need to be based on a cryptohash,
> but are more than
> just the cryptohash.

I wasn't attempting to define all the different sorts of hashs, just
indicate that there are some more appropriate names to be used
depending on what you're doing, and that using these names can clarify
some design issues. I didn't feel the need to explain basic
cryptography terminology to Jonathan Shapiro.

> Also, cryptohashes *can* be used for hash-table lookup,
...
> Note that the cryptohash, being at least 128 bits, is too
> long to use
> directly as in index into a lookup table data structure, so
> a smaller number
> needs to be derived from it.  But the same statement
> applies to the 32 bit
> hashes gotten from Java's Object.hashCode().

That's one way of looking at it, but I believe it is a poor way of
looking at it. The hashtable is ignorant of the cryptohash's security
properties. From the point of view of the hashtable, the cryptohash is
just another key object to be hashed and store in the table. In this
case, your magic "a smaller number needs to be derived from it" step
is the hashtable hash function. This step should be encapsulated away
from the hashtable implementation in the same way that the hashing of
other key objects is.

> Therefore,
> cryptohash are not
> a disjoint category but are a kind of hash.

I believe it leads to cleaner lines of reasoning to think of them as
disjoint operations. As I've explained above, there is no benefit to
thinking of them as related operations.

I don't see any goal to be achieved in debating this design philosophy
issue at this time, so I'm going to drop this part of the discussion
now.

> For E, everyone needs to remember that "==" based lookup
> uses a hash that's
> never exposed to the E programmer, but used privately
> within the hashtable
> implementation.  To do otherwise would be to expose the inherent
> non-determinism of object-identity-based hash values. This

What are your thoughts on Dan Bornstein's request that hashed
containers use equivalence, not equality, to search for elements and
that the definition of equivalence be user configurable at
construction time. I believe it is a good feature and I have already
added it to my Hashtable implementation.

Tyler


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