[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
EQUALP hash tables (and more ...)
- To: Common-Lisp@SU-AI.ARPA
- Subject: EQUALP hash tables (and more ...)
- From: Skef Wholey <Wholey@CMU-CS-C.ARPA>
- Date: Sat, 11 May 1985 19:29:00 -0000
- In-reply-to: Msg of 11 May 1985 10:59-EDT from Scott E. Fahlman <Fahlman>
- Sender: WHOLEY@CMU-CS-C.ARPA
I think a user-extensible hash table mechanism would be a win, and would be
easily implementable even in our non-flavorized system (surprise, surprise).
I have a few comments, though:
1. I don't think it's possible to let users write some form of hashing function
that generates = numbers for EQ objects. There might be an arbitrarily long
time between computing the hash number and using it as an index into a vector,
in which countless objects may be transported or garbage collected. This, of
course, entirely ignores the ugly mechanism that necessitates rehashing the
hash tables at the right time. I would suggest that any hashing facility
involving EQ or EQL for some subset of Lisp objects be left to the system. I
really don't think much functionality is lost this way, although I know it's
very easy to dream up examples which "need" such a feature.
2. The user-supplied hashing function (why not call it :hash instead of
:equivalencing?) will probably want to avoid running into bignum arithmetic and
so forth. The manual should at least mention this danger when describing this
3. Some implementations may have tense routines for computing a hash code for
certain objects. String hashing is microcoded on the Perq, and assembly-coded
on other Spice Lisp-derived systems, for example. A user can get to this
particular routine via SXHASH, but that might not be the case for other hash
functions. Should all specialized, system-supplied, hashing functions be
implementation specific, and documented in the appropriate places? I guess
that would work.
4. Regarding SXHASH on circular structures: Might there be optional arguments
to SXHASH to restrict the "length" and "depth" it will descend into an object?
These would default to some "reasonable" implementation-dependent values. One
Spice Lisp application (a spelling checker that lives inside the editor) dives
straight into the microcode to compute the hash value of a substring. This
extension to SXHASH would eliminate non-portabilities like that.