[gclist] object identity & copying collection
Wed, 10 Dec 1997 21:50:53 +1100
In Appel's "Modern compiler implementation in ML", exercise 13.4 says
"... Explain the problem in implementing hashCode() ... in a Java system
with copying garbage collection, and propose a solution."
Explaining the problem is easy enough (you can't just use the
object address, because it will change), and proposing a solution
is also easy, but proposing a *good* solution is a bit harder.
What is the "textbook" solution for this problem?
Some less-than-ideal solutions:
- hash values can be computed lazily in hashCode()
using a random number generator; they can then
be stored by either
- having a hash value field in each object (ugh!)
- keeping a global table (binary tree) mapping
from objects to hash values. This requires
that the collector preserve relative ordering
(otherwise you'd have to use a linked list, double-ugh!).
You also want the table keys to be weak pointers.
Fergus Henderson <firstname.lastname@example.org> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger email@example.com | -- the last words of T. S. Garp.