Correctly synchronizing equals() in Java

Question

I have the following class which contains only one field i. Access to this field is guarded by the lock of the object ("this"). When implementing equals() I need to lock this instance (a) and the other (b). If thread 1 calls a.equals(b) and at the same time thread 2 calls b.equals(a), the locking order is reverse in the two implementations and may result in deadlock.

How should I implement equals() for a class which has synchronized fields?

public class Sync {
    // @GuardedBy("this")
    private int i = 0;
    public synchronized int getI() {return i;}
    public synchronized void setI(int i) {this.i = i;}

    public int hashCode() {
        final int prime = 31;
        int result = 1;
        synchronized (this) {
            result = prime * result + i;
        }
        return result;
    }

    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Sync other = (Sync) obj;
        synchronized (this) {
            synchronized (other) {
                // May deadlock if "other" calls 
                // equals() on "this" at the same 
                // time 
                if (i != other.i)
                    return false;
            }
        }
        return true;
    }
}

Answer 1

The correct implementation of equals() and hashCode() is required by various things like hashing data structures, and so you have no real option there. From another perspective, equals() and hashCode() are just methods, with the same requirements on synchronization as other methods. You still have the deadlock problem, but it's not specific to the fact that it equals() that's causing it.

Answer 2

Why synchronise? What is the use case where it matters one if them changes during the comparison and it does not matter if if changes immediately after before code depending on equality runs. (ie if you have code depending on equlity what happens if the values become unequal before or during this code)

I think you have to take a look at the larger process to see where you need to lock.

Answer 3

Always lock them in the same order, one way you could decide the order is on the results of System.identityHashCode(Object)

Edit to include comment:

The best solution to deal with the rare case of the identityHashCodes being equal requires more details about what other locking of those objects is going on.

All multiple object lock requirements should use the same resolution process.

You could create a shared utility to track objects with the same identityHashCode for the short period of the lock requirements, and provide a repeatable ordering for them for the period that they're being tracked.

Answer 4

Trying to synchronize equals and hashCode inside the object will not work properly. Consider the case of a HashMap that uses hashCode to discover which "bucket" an object will be in, and then uses equals to sequentially search all objects in the bucket.

If objects are allowed to mutate in a way that changes the outcomes of hashCode or equals you could end up with a scenario where HashMap calls hashCode. It acquires the lock, gets the hash and releases the lock again. HashMap then proceeds to compute which "bucket" to use. But before HashMap can acquire the lock on equals someone else grabs the lock and mutates the object so that equals become inconsistent with the previous value of hashCode. This will lead to catastrophic results.

The hashCode and equals methods are used in a lot of places and is core to the Java collections API. I might be valuable to rethink your application structure that do not require synchronized access to these methods. Or at the very least not synchronize on the object itself.

Answer 5

Where is the point in synchronizing equals() if the result isn't guaranteed to be true after synchronization was left:

if (o1.equals(o2)) {
  // is o1 still equal to o2?
}

Hence you could simply synchronize calls to getI() inside equals one after another without changing the output - it's simple not valid anymore.

You'll always have to synchronize the whole block:

synchronized(o1) {
  synchronized(o2) {
    if (o1.equals(o2)) {
      // is o1 still equal to o2?
    }
  }
}

Admittedly, you'll still face the same problem, but at least your synchronizing at the right point ;)

Answer 6

The only way to know for sure if synchronization is strictly necessary is to analyze the entire program for situations. There are two things you need to look for; situations where one thread is changing an object while another is calling equals, and situations where the thread calling equals might see a stale value of i.

If you lock both this and the other object at the same time you do indeed risk a deadlock. But I'd question that you need to do this. Instead, I think you should implement equals(Object) like this:

public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Sync other = (Sync) obj;
    return this.getI() == other.getI();
}

This does not guarantee that the two objects have the same value of i at the same time, but that is unlikely to make any practical difference. After all, even if you did have that guarantee, you'd still have to cope with the issue that the two objects might no longer be equal by the time that the equals call returned. (This is @s's point!)

Furthermore, this does not entirely eliminate the risk of deadlock. Consider the case where a thread may call equals while holding a lock on one of the two objects; e.g.

// In same class as above ...
public synchronized void frobbitt(Object other) {
    if (this.equals(other)) {
        ...
    }
}

Now if two threads call a.frobbitt(b) and b.frobbitt(a) respectively, there is a risk of deadlock.

(However, you do need to call getI() or declare i to be volatile, otherwise the equals() could see a stale value of i if it was recently updated by a different thread.)

This having been said, there is something rather worrying about a value-based equals method on an object whose component values may be mutated. For example, this will break many of the collection types. Combine this with multi-threading and you are going to have a lot of difficulty figuring out whether your code is really correct. I cannot help thinking that you would be better off changing the equals and hashcode methods so that they don't depend on state that may mutate after the methods have been called the first time.

Answer 7

(I assume that you're interested in the general case here, and not just in wrapped integers.)

You can't prevent two threads from calling set... methods in arbitrary order. So even when one thread gets a (valid) true from calling .equals(...), that result could be invalidated immediately by another thread that calls set... on one of the objects. IOW the result only means that the values were equal at the instant of comparison.

Therefore, synchronizing would protect against the case of the wrapped value being in an inconsistent state while you are attempting to do the compare (e.g. two int-sized halves of a wrapped long being updated consecutively). You could avoid a race condition by copying each value (i.e. independently synchronized, without overlap) and then comparing the copies.

Answer 8

Reads and writes to int variables are already atomic, so there is no need to synchronize the getter and setter (see http://java.sun.com/docs/books/tutorial/essential/concurrency/atomic.html).

Likewise, you don't need to synchronize equals here. While you could prevent another thread from changing one of the i values during comparison, that thread would simply block until the equals method completes and change it immediately afterwards.

Answer 9

As Jason Day points out, integer compares are already atomic, so synchronizing here is superfluous. But if you were just constructing a simplified example and in real life you're thinking of a more complex object:

The direct answer to your question is, insure that you always compare the items in a consistent order. It doesn't matter what that order is, as long as it's consistent. In a case like this, System.identifyHashCode would provide an ordering, like:

public boolean equals(Object o)
{
  if (this==o)
    return true;
  if (o==null || !o instanceof Sync)
    return false;
  Sync so=(Sync) o;
  if (System.identityHashCode(this)<System.identityHashCode(o))
  {
    synchronized (this)
    {
      synchronized (o)
      {
         return equalsHelper(o);
      }
    }
  }
  else
  {
    synchronized (o)
    {
      synchronized (this)
      {
        return equalsHelper(o);
      }
    }
  }
}

Then declare equalsHelper private and let it do the real work of comparing.

(But wow, that's a lot of code for such a trivial issue.)

Note that for this to work, any function that can change the state of the object would have to be declared synchronized.

Another option would be to synchronize on Sync.class rather than on either object, and then to also synchronize any setters on Sync.class. This would lock everything on a single mutex and avoid the whole problem. Of course, depending on what you're doing this might cause undesired blocking of some threads. You'd have to think through the implications in light of what your program is about.

If this is a real issue in a project you're working on, a serious alternative to consider would be to make the object immutable. Think of String and StringBuilder. You could create a SyncBuilder object that lets you do any work you need to create one of these things, then have a Sync object whose state is set by the constructor and can never change. Create a constructor that takes a SyncBuilder and sets its state to to match or have a SyncBuilder.toSync method. Either way, you do all your building in SyncBuilder, then turn it into a Sync and now you're guaranteed immutability so you don't have to mess with synchronization at all.

Answer 10

If it has been said enough, the fields you use for hashCode(), equals() or compareTo() should be immutable, preferably final. In this case you don't need to synchronise them.

The only reason to implement hashCode() is so the object can be added to a hash collection, and you cannot validly change the hashCode() of an object which has been added to such a collection.

Answer 11

Do not use syncs. Think about unmodifiable beans.

Answer 12

You are attempting to define a content-based "equals" and "hashCode" on a mutable object. This is not only impossible: it doesn't make sense. According to

http://java.sun.com/javase/6/docs/api/java/lang/Object.html

both "equals" and "hashCode" need to be consistent: return the same value for successive invocations on the same object(s). Mutability by definition prevents that. This is not just theory: many other classes (eg collections) depend on the objects implementing the correct semantics for equals/hashCode.

The synchronization issue is a red herring here. When you solve the underlying problem (mutability), you won't need to synchronize. If you don't solve the mutability problem, no amount of synchronization will help you.