Barry Margolin
6/16/2015 1:56:00 AM
In article <20150615150609.132@kylheku.com>,
Kaz Kylheku <kaz@kylheku.com> wrote:
> I just noticed in the CLHS that the computation of equal is not required to
> terminate.
> But the computation of sxhash, which is tied to equal, and whose intended
> purpose
> is hashing, *is* required to terminate. Oops!
>
> What is the point of that? If you do hashing using sxhash, what good is it to
> be
> assured that computation of the hash codes will terminate, if the actual
> comparison
> to verify equality might not terminate?
>
> Basically, either you want both sxhash and equal to terminate on circular
> objects, or else let neither of them terminate.
Hash functions don't have to examine every bit of the data they're
hashing, and they often limit the amount for performance reasons -- it's
generally better to have a few more hash collisions than for the hash
function to be slow. So a hash function doesn't have to detect
circularity in order to terminate on a circular function, all it has to
do is limit the recursive depth.
But EQUAL can't do that -- it can't report that two lists are equal just
because it gave up before it reached the difference. We could have
required it to detect circularity, but deciding whether two circular
list structures are equal is complicated, so we just punted there.
Using a circular list as a key in a hash table seems like a bad idea.
--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***