Hashing It Out

[billroper]

Thinking some more about yesterday's Java problem:

In almost every case, for an "ID"-type class, two different instances of the ID that contain the same identifiers should return true when passed to the equals() method and should return identical hash code values when the hashCode() method is called. The problem is that the standard equals() and hashCode() methods that are inherited from the Object class will treat these as different objects. If an ID is supposed to uniquely identify some Object (for example, a PersonID that uniquely identifies a Person), only one instance of the ID will work to identify the unique Object if the ID is used as a key in a HashMap or the like, because a different instance of the ID, although conceptually equal, will generate a different hash code and will return false in an equals() comparison.

The solution, then, is to override the equals() and hashCode() methods for the ID classes so that IDs that are conceptually equal will return identical hash code values and will return true in an equals() comparison. This is, in fact, the case by default if the ID is simply a String.

So let's override the hashCode() and equals() methods for the ID classes. Life is good.

Except now there's no way to identify different instances of your ID object. And when you're writing a serialized stream that may contain duplicate references to the same object, you want to know if you've written an object to the stream before, so you can write the object once and restore the duplicate references to the object when reading the serialized stream back into memory. Normally, you could use a HashMap with the object as a key to keep track of this, but now two different instances of the ID will return the same hash code and will return true for equals(), so different instances are interpreted as being the same instance.

It looks like the right answer to this is to define an interface that all of the serializable objects can implement that will, by default, call back to the default object implementations of hashCode() and equals() (let's call them objectHashCode() and objectEquals()); then implement an ObjectHashMap that will call objectHashCode() and objectEquals() instead of hashCode() and equals().

*sigh*

This is an annoying amount of work to do...

Comments

[madfilkentist]

Having, in effect, two different versions of equals for the same class sounds error-prone to me. I'd be more inclined, if it's possible, to define a wrapper object with definitions of equals and hashCode that distinguish every instance, and compare and hash (new DistinsuishingWrapper(object)) whenever you need that behavior.

The obvious downside is that it's a little more overhead to create and garbage-collect the wrappers. This may or may not be a deal-breaker in your application.

[billroper]

Steve S. put his finger on the solution. There's a class in Apache Commons (IdentityMap) for Java 6 and in Java 7 proper (IdentityHashMap) which uses the default implementations of equals and hashCode for keys that it stores, which is exactly what I need to solve the problem.

You learn something new every day, I guess. :)

[catsittingstill.livejournal.com]

It sounds very tedious and detail-oriented to me. You have my sympathy. But I suppose if anyone could do it / was willing to do it, it wouldn't pay very well.

[billroper]

It turns out that there's an existing map class that will do what I need, so this is going to be pretty simple -- other than reverting all of the changes I made last night. :)

[mdlbear]

https://commons.apache.org/proper/commons-collections/javadocs/api-3.2.1/org/apache/commons/collections/map/IdentityMap.html is the solution to your problem

[billroper]

Ha! I hadn't realized that there was a System method that would get the default hashCode(). That makes all things possible. :)

And IdentityMap exactly solves the problem that I'm trying to solve. Now I can override the equals() and hashCode() methods for the ID classes and still handle the one place where I need to do the identity testing.

Thanks!

[billroper]

And apparently, you can get this in Java 7 using IdentityHashMap. They've promised that I can go to Java 7; I guess it's time to raise the issue again.

[madfilkentist]

The last place where I worked banned Apache Commons as oudated and unreliable (and favored new Java EE technologies supported by a single person as fundamental building blocks). What are your thoughts on the reliability of Commons?

Of course, Java 7's IdentityHashMap makes the point moot in this case.

[billroper]

The pieces of Commons that I've used seem pretty reliable to me. Of course, I only use it for things that I can't get from standard Java trivially. So I've found StringUtils quite handy, for example.

And the point is only moot once I manage to get this project up onto Java 7. This is proving challenging -- not because of Java itself, but because all of the other projects that we're working with are still on Java 6.

[mdlbear]

On the gripping hand, is there any good reason why two equal IDs should be different objects? In languages with a built-in identifier type (Lisp, Smalltalk, ...) IDs are singletons, meaning you can use == to test for equality instead of equals. Big win for speed.

To make this work, put a hash table in your class and use a factory method instead of new.

[billroper]

The problem is that my Java code is communicating with C++ code where two equal IDs can be different objects and retrofitting all of that existing C++ code is going to be way too much work. Also, the IDs aren't always immutable (for some good reasons).

[mdlbear]

Right; I'd forgotten that. In that case, IdentityMap is definitely your friend. There's a lot of good stuff in the Apache Commons library.

You'll also want to check out Lombok and findbugs -- the latter is kind of a super-lint for Java.

[billroper]

Oh, I know. I have pulled several of the Apache Commons packages into the project.

It's just frustrating, because I had been googling madly looking for just this feature and my google-fu failed completely. :)