Subject: Re: (make-hash-table :test #'mytest)
From: (Rob Warnock)
Date: Tue, 05 Nov 2002 20:56:41 -0600
Newsgroups: comp.lang.lisp
Message-ID: <>
Tim Bradshaw  <> wrote:
| * Frode Vatvedt Fjeld wrote:
| > And rehash at GC-time? Is this really being done in practice?
| It more-or-less has to be I think.  Unless object contain some magic
| bit of data which uniquely identifies them but is not their address,
| then if their address changes, you need to rehash.

Some kinds of objects might conveniently have a hash computed on them
when they're created or read in (or lazily, the first time they're used
in any hash-related operation) that is permanently stored with the object
(and recomputed if the object is mutated). Strings & symbols (with the
hash being based on their name-strings) come to mind as the main candidates
for this, though in some cases bignums might also benefit.

In that case, hash tables containing only keys with such "persistent"
hash values [or values whose hashes don't depend on location] need not
be re-hashed when GC'd, nor even when expanded (if the stored hash value
contains "extra" bits which were unused in doing lookups with the smaller
hash table size). Indeed, a hash table might contain a hint bit that says
whether the table is currently "GC-clean", which is cleared whenever a
non-cooperating key is stored into it (and perhaps set again during some
future GC if the table becomes "clean" again).


Rob Warnock, PP-ASEL-IA		<>
627 26th Avenue			<URL:>
San Mateo, CA 94403		(650)572-2607