[Re: Hash Tables and GC]

[goldman@vaxa.isi.edu]

          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)

There is no particular concern about whether other pointers to the VALUE
exist; only pointers to members of the KEY's equivalence class.  Look at
the problem not as one of GC, but as one of "when is it safe to remove
an entry from a hash table?"  [once it has been removed that may make
the value garbage (reduce its reference count to 0)].  It is certainly
SAFE to remove a set of entries Ei= [Ki Vi] if, once the Ei are removed,
there is no way to construct a reference to an object equivalent to any Ki.
If there are references to KEYS from inside VALUES, some schemes may fail
to remove entries that are safe to remove, but this is just like reference
count GCers that fail to reclaim certain circular structures even though
they are garbage.  You lose space, but don't get incorrect results.


    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.

Considering the paragraph of CLTL beginning on pg 77 and continuing to the top
of pg 78, entries in EQ hash tables having integers or characters as the
KEY can serve NO PORTABLE purpose except for usage through
MAPHASH and/or HASH-TABLE-COUNT.

Neil