[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Hash Tables and GC
- To: common-lisp@SAIL.STANFORD.EDU
- Subject: Hash Tables and GC
- From: ELIOT@cs.umass.edu
- Date: Tue, 2 Aug 88 09:18 EDT
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.