Tim Bradshaw  <tfb@cley.com> 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

-----
Rob Warnock, PP-ASEL-IA		<rpw3@rpw3.org>
627 26th Avenue			<URL:http://www.rpw3.org/>
San Mateo, CA 94403		(650)572-2607