Concurrent bidirectional dictionary

Question

I've been agonizing over this for an hour or two. I require a bidirectional dictionary that was thread safe. From what I understand about dictionaries, they're thread safe when being read from, but no so much when being written to. I've tried to write this code snippet to my understanding of correct, but a review would be excellent if possible.

class ConcurrentBidirectionalDictionary<TKey,UKey>
{
    private Dictionary<TKey, UKey> BackingDictionary;

    public ConcurrentBidirectionalDictionary()
    {
        BackingDictionary = new Dictionary<TKey, UKey>();
    }

    //Adding to dictionaries is not thread-safe ergo, lock when adding
    private readonly object _SyncLock = new object();
    public void Add(TKey item1, UKey item2)
    {
        if (!BackingDictionary.ContainsKey(item1) && !BackingDictionary.ContainsValue(item2))
        {
            lock (_SyncLock)
            {
                if (!BackingDictionary.ContainsKey(item1) && !BackingDictionary.ContainsValue(item2))
                {
                    BackingDictionary.Add(item1, item2);
                }
                else
                {
                    ThrowNewDuplicateKeyException(item1, item2);
                }
            }
        }
        else
        {
            ThrowNewDuplicateKeyException(item1, item2);
        }
    }

    private void ThrowNewDuplicateKeyException(TKey item1, UKey item2)
    {
        if (BackingDictionary.ContainsKey(item1) && BackingDictionary.ContainsValue(item2))
        {
            throw new ArgumentException("Duplicate Keys not allowed", "item1, item 2", null);
        }
        else if (BackingDictionary.ContainsKey(item1))
        {
            throw new ArgumentException("Duplicate Keys not allowed", "item1", null);
        }
        else if (BackingDictionary.ContainsValue(item2))
        {
            throw new ArgumentException("Duplicate Keys not allowed", "item 2", null);
        }
    }

    //Reading is thread safe, no lock needed
    public TKey GetFromUKey(UKey UKey)
    {
        var Record = BackingDictionary.FirstOrDefault(x => EqualityComparer<UKey>.Default.Equals(x.Value, UKey));
        if (Record.Equals(default(KeyValuePair<TKey,UKey>)))
        {
            throw new IndexOutOfRangeException($"Unable to find UKey {UKey}");
        }
        return Record.Key;
    }

    public UKey GetFromTKey(TKey TKey)
    {
        return BackingDictionary[TKey];
    }
}

Answer 1

It is better to use CouncurrentDictionary to reduce lock contention:

class Map<X, Y>
{
    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<X, Y> XY { get; } = new ConcurrentDictionary<X, Y>();
    ConcurrentDictionary<Y, X> YX { get; } = new ConcurrentDictionary<Y, X>();
}

Answer 2

I think you have some misconceptions regarding thread safety. Check out MSDN page about Dictionary. Thread Safety section states:

A Dictionary can support multiple readers concurrently, as long as the collection is not modified. Even so, enumerating through a collection is intrinsically not a thread-safe procedure. In the rare case where an enumeration contends with write accesses, the collection must be locked during the entire enumeration. To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.

This is because when you write to dictionary it can,for example, increase the size of underlying collections or reorganize internal "buckets" where items are stored. Those operation will move items around which can break a concurrent read operation in unpredictable way. Enumerations on the other hand will throw straight away, if you modify the collection during enumeration process.

The bottom line is: your GetFromTKey (read) and GetFromUKey (enumeration) are not thread safe. You must synchronize them with your Add method if you want to read and write concurrently.