EQUALP hash tables

[Jon White <JLW@SU-AI.ARPA>]

In-reply-to: your message of 11-May-85  10:59 EDT

As for names for the "equivalence" and "numericalizing" functions for
hash tables, well, the :test argument is already the "equivalence" argument;
how about :sxhash for the numericalizing argument?  This has the mnemonic
value that the default for it could simply be #'SXHASH.

I see no reason to restrict the possible values that :sxhash may have --
even when the :test argment is #'EQ; as my note last week was intending
to point out, EQ-type hash tables needn't be constrained to use pointer
bits for the :sxhash -- it's only a vague general feeling that we don't
want to have to re-hash whenever some object in th table is updated that
prevents use of #'SXHASH here.  But for many (maybe even most?) applications
there is really no need to worry about the updating problem;  after all,
who really worrys about it with EQUAL type tables?  and it's just as
serious a problm there too, as Hoey pointed out.

How  would you feel about this?  The default :sxhash value will be an internal
version of MAKNUM *** when the :test arg is #'EQ o #'EQL *** rather than
SXHASH (appropriate conversions from 'EQ and 'EQL).  iven this, is there any
need to have the user supply the information that the table will have to be
re-hash'd after a relocating GC?  This condition should only occur when the
:sxhash function is somehow a function of the entry's pointer address -- and
by fiat you are ruling out any user-level function that returns that address.
Can anyone think of a case where this isn't true?

Finally, I'd say your suggestion for a REHASH function is quite timely.
Interlisp  has such a function:
  (REHASH hash-array new-array)
where both argments are hash-arrays, and the first one is merely re-hashed
into the second; a NIL for the second arg means something like (I think)
"cons up a fresh hash array just big enough to hold all the elements of
the first argument, and it's :rehash-threshold size"; and a T for the
second arg means something like (I think) "cons up a fresh hash array big
enough to be the growth by the :rehash-size of the first argument".
[well, if it doesn't operate exactly like that, it should].  

A useful scenario is to make a huge hash table, make many entries over a
period of time, and then finally decide that not may more entries will
be made; thus one will want to "shrink" the table to the minimum feasible
size for holding the current entries.  REHASH, as defined above, with a
second arg of NIL is just the right thing.

-- JonL --