Hash Tables and GC

[ELIOT@cs.umass.edu]

    I just got back from vacation and read the discussion of has tables.
    One point seems not to have been discussed - "Weak" links in hash
    tables would be almost impossible to implement except for EQ hash
    tables.  Not only does the GC have to prove that the reference
    count for both key and value is one, but the GC also has to prove
    that there are no other objects, x, such that:
    	(<Equality-Predicate> x KEY)
    For EQ hash tables this condition is true, a priori, but for any
    other hash table it is not.  Consider an EQL hash table with
    BIGNUM keys.  A program could somehow effectively copy a bignum
    that is being used as a hash table key and then lose the original.
    
    For EQUAL hash tables it is even worse.  Suppose (A . B) is a
    key.  At any time a program might apply CONS to A and B to
    re-create the key.  For example, suppose I am using a hash
    table to represent a graph.  If A and B are nodes, then
    the graph-links can be implemented using a hash table like this:
    
    (defun BEFORE-P (A B)
    	(gethash (cons a b) *link-table*))
    
    Even EQ hash tables have problems, in any implementation with
    immediate representations for objects.  For example the key 57236
    (a fixnum) may not be interned and therefor there is no way to tell
    how many copies of it exist.
    
    Because of these problems I would suggest that this feature be
    restricted to EQ and EQL hash tables, and that numbers of all types
    should be considered accessible keys.