JavaでThread-safeなequalsを実装する

JavaでequalsをThread-safeに実装する話です。

まずはThread-safeでないequalsの実装を示します。

Thread-safeでない実装

class Foo {

    private int[] data;

    ...

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Foo)) return false;

        Foo that = (Foo) o;

        for(int i = 0; i < data.length; i++) {
            if(data[i] != that.data[i]) {
                return false;
            }
        }

        return true;
    }

    ...
}

次はThread-safeなequalsの誤った実装を示します。

誤った実装

public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Foo)) return false;

    Foo that = (Foo) o;

    synchronized(this) {
        synchronized(that) {
            for(int i = 0; i < data.length; i++) {
                if(data[i] != that.data[i]) {
                    return false;
                }
            }
        }
    }

    return true;
}

この実装は一見うまく動くように見えますが、
次のような過程でデッドロックが発生します。

1. スレッド1がfoo1#equals(foo2)を呼んでfoo1のロックを獲得する。
2. スレッド2がfoo2#equals(foo1)を呼んでfoo2のロックを獲得する。
3. スレッド1がsynchronized(that)でfoo2のロック獲得を待つ。
4. スレッド2がsynchronized(that)でfoo1のロック獲得を待つ。

デッドロックが発生する理由は単純です。
2つ以上のオブジェクトのロックを獲得する際に、
ロックの獲得順序を一定にするという基本原則に反しているからです。

しかし、foo1とfoo2は対等です。これらに一定の順序付けをすることは可能でしょうか。

それは、System#identityHashCode(Object)を使うと可能です。
identityHashCodeは引数のオブジェクトを一意に表すint型の値を返します。
例えばこの値が大きい方から先にロックを獲得するというルールを定めると、
2つのオブジェクト間で一定の順序でロックを獲得することができます。

最後に、identityHashCodeを利用したThread-safeなequalsの実装を示します。

正しい実装

public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Foo)) return false;

    Foo that = (Foo) o;

    // Decide lock order
    Foo firstLock, secondLock;
    if(System.identityHashCode(this) > System.identityHashCode(that)) {
        firstLock = this;
        secondLock = that;
    } else {
        firstLock = that;
        secondLock = this;
    }

    // Lock and Compare
    synchronized(firstLock) {
        synchronized(secondLock) {
            for(int i = 0; i < data.length; i++) {
                if(data[i] != that.data[i]) {
                    return false;
                }
            }
        }
    }

    return true;
}

それぞれの実装を3000回試行したところ、
誤った実装ではデッドロックが14回発生しましたが、正しい実装では0回でした。