Threadsafe bidirectional association in Java

Question

What is a good way to implement thread-safe bidirectional associations? Is there maybe a good library or code generator?

Here is a non thread-safe example:

class Foo {

    private Foo other;

    public Foo getOther() {
        return other;
    }

    public void setOther(Foo other) {
        this.setOtherSecretly(other);
        other.setotherSecretly(this);
    }

    void setOtherSecretly(Foo other) {
        if (this.other != null) this.other.other = null;
        this.other = other;
    }
}

My requirements for thread-safety are:

• No deadlocks
• Eventual consistency (When all threads stop modifying the objects, a consistent state is eventually reached. I.e., it is acceptable that assert foo.getOther().getOther() == foo fails when another thread is performing setOther concurrently.
• Sequential behaviour. If a thread performs setOther and no other other thread overrides the value, getOther immediately returns the new value for that thread.
• No traveling back in time. Once a thread observed a new value with getOther, it will never again receive the old value (unless it is set again).

Also nice to have:

• Low contention, especially no global lock. The solution should scale well.
• As little synchronization overhead as possible. It should have reasonable performance for a single thread.
• Low memory overhead. When an object has 5 associations, I don't want 3 additional fields per association. Local variables in setters are ok.

My application will have 16 threads working on about 5.000 objects of several classes.

I couldn't come up with a solution yet (no, this is not homework), so any input (ideas, articles, code) is welcome.

Answer 1

Google Guava does this for you: BiMap.

For example:

BiMap<Integer, String> bimap = Synchronized.biMap(HashBiMap.create(), someMutexObject);
bimap.put(1, "one");
bimap.put(2, "two");

bimap.get(1); // returns "one"
bimap.inverse().get("one") // returns 1

someMutexObject can be any object you would want to synchronize on.