Re: Issues with unique object IDs in persistence

On Fri, 15 May 2009, Jarrick Chagma wrote:


Your definition still isn't coherent, i'm afraid. The problem is that two
objects with different state can be equal - for instance:

public class Thing {
  private int x;
  private String s;
  public Thing(int x, String s) {
  this.x = x; this.s = s;
  }
  public boolean equals(Object obj) {
  if ((obj == null) || (!obj instanceof Thing)) return false;
  Thing that = (Thing)obj;
  return this.x == that.x;
  }
}

new Thing(1, "red").equals(new Thing(1, "blue")); // == true

If you're willing to drop condition 3, then the definition makes sense.

If were interested in object identity rather than object state, then the
solution is fairly easy: set up a counter, and allocate numbers from it to
every object you see, using an identityHashMap to keep track of them.

Distinction by state is much harder, though. And still not well-defined -
presumably, you'd consider these objects:

List a = Arrays.asList(Arrays.asList("foo"));
List a = Arrays.asList(a.get(0));

The same. But do you consider these objects:

List a = Arrays.asList(Arrays.asList("foo"));
List b = Arrays.asList(Arrays.asList("foo"));

The same or not? They're equal, they look very similar, but if you do
this:

a.set(0, "bar");

Or this:

((List)a.get(0)).set(0, "bar");

Then they will no longer be equal, which means that they shouldn't
necessarily be considered 'the same'.

If you don't consider the latter pair of lists the same, you can build an
ID out of the class of the object in question, the values of any primitive
fields in the object and the identity numbers (worked out as above!) of
any reference fields. It won't fit in a long, though. You could hash it
down to a long, but then you lose the guarantee of different objects
having different identities. Or you could use the counter mechanism again,
but this time with these complete-state IDs as a key, used to look up the
counter-issued ID. Note that since you need both the identity and state
mechanisms running in parallel, it probably makes sense to include the
counter-issued state ID in the record keyed by identity, since every
object has exactly one state ID, and the lookups in the identity map are
likely to be much faster than those in the state map, since you don't have
to construct a state ID to do them.

If you do consider the latter pair of lists the same, you have a rather
harder problem. You can apply the same strategy of constructing a mega-ID
containing the complete state of the object, but this time it has to
include the state of any pointed-to objects as well. You can do this by
descending into those objects, constructing their state ID, and then
combining those to make the state ID for the root object, applying this
recursively as necessary. Note that you'll have to detect and deal with
cycles in the reference graph, or else you'll end up in an infinite loop.
You might be able to get clever here, and use child objects' state IDs
instead of ther actual values in constructing the root's state ID, but
then you end up with a different version of the infinite loop problem.

tom

--
Once, at a fair on the Heath, [Geoffrey Fletcher] overheard a man saying
that Hampstead wasn't thrilling enough. Fletcher reached over in the
darkness and stuck an ice lolly down the back of his shirt.