Concurrent bidirectional dictionary
It is better to use CouncurrentDictionary to reduce lock contention:

class Map&lt;X, Y&gt;
{
    public X this[Y y]
    {
        get { return YX[XY[YX[y]]]; } // Ensure Set completion
        set { Set(value, y); }
    }

    public Y this[X x]
    {
        get { return XY[x]; }
        set { Set(x, value); }
    }

    void Set(X x, Y y)
    {
        if (!YX.GetOrAdd(y, x).Equals(x))
            throw new InvalidOperationException();

        if (!XY.GetOrAdd(x, y).Equals(y))
            throw new InvalidOperationException();
    }

    ConcurrentDictionary&lt;X, Y&gt; XY { get; } = new ConcurrentDictionary&lt;X, Y&gt;();
    ConcurrentDictionary&lt;Y, X&gt; YX { get; } = new ConcurrentDictionary&lt;Y, X&gt;();
}