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

SXHASH and EQ hash tables



I agree that limiting the number of substructures visited by SXHASH is
a good thing to do.  The next manual should promise that SXHASH will
operate on any object, and mention depth- and length-limiting as an
implementation note.  Probably what you want is just a limit on the
number of substructures visited.  There's probably no good way of
outlawing a constant function, but I think the desirability of having a
large range for SXHASH goes without saying.

Scott pointed out to me that efficiency rules out having (SETF (GETHASH
KEY ...)) do an automatic (COPY-TREE KEY) for the insertion.  He
suggested removing the item from the hashtable, then modifying it, then
reinserting; that's a solution in some cases, but what if a lot of keys
share the modified structure?  Well, for EQUAL hash tables, I think the
manual should mention that you might want to (SETF (GETHASH (COPY-TREE
Key)...)).  And for EQUALP hashtables, there should be a
COPY-SUBSTRUCTURE (or COPY-TREE :TEST #'EQUALP ?) function to do the
analogous thing.

As for using SXHASH on EQ hash tables, I think this is a really bad
idea.  There's just no way to get around rehashing, and I think it's
conceptually wrong to have to worry about it.  I can see rehashing
``whenever some object in the table is updated'' but for EQ keys you
aren't modifying the object in the table.  Here I think the manual
should promise that EQ hashing is insensitive to changes in
substructures.

Dan