[gclist] object identity & copying collection

[Fergus Henderson]

Hi,

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 <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.