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

*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.

- Prev by Date:
**Removal request** - Next by Date:
**[Re: Hash Tables and GC]** - Previous by thread:
**Re: hash tables and GC** - Next by thread:
**Re: hash tables and GC** - Index(es):