[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: EQUALP hash tables (and more ...)

    Date: 09 May 85  2356 PDT
    From: Jon White <JLW@SU-AI.ARPA>

    ... a more generalized form of hashing ... two more "properties" of
    hashtables -- the "equivalenceing" function, and the "numericalizing"

    For "equivalence" function, the user may supply #'eq, #'string=, or
    even something random like #'=-mod-5;

Bravo!  If CL should have hash tables, it should have these.  The
existing lack of functionality is embarrassing in an otherwise
orthogonal, extensible language.

    ... the "numericalizing" function is simply how to reduce a general
    s-expression into a reasonable sized fixnum....

I would leave off ``reasonable sized''; certainly gethash is capable of
hashing a fixnum value to its favorite range.

    I [believe] hashing on EQ means using the pointer address...
    but nothing in the CLM would prevent an implementation from using sxhash

Two problems with this.  First, as you note, the key could get
modified.  I'm not sure you noticed, but this means that in order for
GETHASH to fail, it would have to examine the whole table for modified
structures.  Second, I think SXHASH might not terminate on circular
structures, though this caveat is not in the manual (and it, or its
denial, should be).