Re: hash tables and GC

[Barry Margolin <barmar@Think.COM>]

    Date: Fri, 22 Jul 88 18:23:53 BST
    From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>

    Even if you do a MAPHASH, there is no way for you to tell K should be
    in the table (or even that it exists) unless you have independent
    access to it.  So, the possibility of MAPHASH would still allow K
    and V to be removed.  Of course, you could gather various statistics
    with MAPHASH that would change if K were removed (e.g., the number of
    keys would decrease), but I think that's OK.

That's not quite correct.  You could remember some property of the
key, or a value that you expect to find, without retaining independent
access to the key itself.  For example, 

(defun reverse-gethash (value table)
  (let ((keys nil))
    (maphash #'(lambda (key val)
		 (when (eq val value)
		   (push key keys)))
	     table)
    keys))

In the above example I'm presuming that the GCing we are talking about
would delete entries if there were no other references to the key, and
ignores other references to the value.  Here's something that doesn't
depend on this:

(defun gethash-by-pname (string table &optional default)
  (maphash #'(lambda (key val)
	       (when (and (symbolp key) (string-equal (symbol-name key) string))
		 (return-from gethash-by-pname (values val t)))
	   table)
  (values default nil))

The general point is that MAPHASH allows you to find entries that have
properties other than the one defined by the table's equality predicate.

                                                barmar