Since Dictionary<TKey, TValue> is already designed to handle hash collisions, I would recommend that, before implementing your own replacement from scratch, you ask: is there any way I can use the existing Dictionary<TKey, TValue> type with two symmetric keys? And, in fact, this can be done, because a .Net dictionary can be constructed with a custom IEqualityComparer. Given that, your problem now simplifies to: how can I create an equality comparer between pairs of keys that is symmetric?

Assuming you have access to the Tuple or ValueTuple types, you can create the following IEqualityComparer and extension methods:

public class SymmetricTupleComparer<T1> : IEqualityComparer<Tuple<T1, T1>>
{
    IEqualityComparer<T1> comparer = EqualityComparer<T1>.Default;
 
    #region IEqualityComparer<Tuple<T1,T1>> Members

    public bool Equals(Tuple<T1, T1> x, Tuple<T1, T1> y)
    {
        if (object.ReferenceEquals(x, y))
            return true;
        else if (object.ReferenceEquals(x, null) || object.ReferenceEquals(y, null))
            return false;

        if (comparer.Equals(x.Item1, y.Item1) && comparer.Equals(x.Item2, y.Item2))
            return true;
        if (comparer.Equals(x.Item1, y.Item2) && comparer.Equals(x.Item2, y.Item1))
            return true;
        return false;
    }

    public int GetHashCode(Tuple<T1, T1> obj)
    {
        if (obj == null)
            return 0;
        // Here we use the fact that the XOR operator is symmetric
        return comparer.GetHashCode(obj.Item1) ^ comparer.GetHashCode(obj.Item2);
    }

    #endregion
}

public static partial class DictionaryExtensions
{
    // Extension methods for dictionaries of symmetric pairs.
    // https://unity3d.com/learn/tutorials/topics/scripting/extension-methods

    public static void Add<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary.Add(Tuple.Create(item1, item2), value);
    }

    public static void Set<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary[Tuple.Create(item1, item2)] = value;
    }

    public static bool Remove<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.Remove(Tuple.Create(item1, item2));
    }

    public static bool TryGetValue<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, out TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.TryGetValue(Tuple.Create(item1, item2), out value);
    }
}

• GetHashCode() XOR's the hash codes of the items. Since XOR is symmetric, two tuples with flipped items will have the same hash code.

• Equals() checks whether the items are identical or identical when flipped.

And now you can use the comparer and extension methods as follows:

var dictionary = new Dictionary<Tuple<int, int>, string>(new SymmetricTupleComparer<int>());
dictionary.Set(1, 0, "hello");
Console.WriteLine(dictionary.Get(0, 1));

Sample fiddle with basic tests working.

public struct SymmetricPair<TKey> : IEquatable<SymmetricPair<TKey>>
{
    readonly TKey item1;
    readonly TKey item2;

    public SymmetricPair(TKey item1, TKey item2)
    {
        this.item1 = item1;
        this.item2 = item2;
    }

    public TKey Item1 { get { return item1; } }
    public TKey Item2 { get { return item2; } }

    #region IEquatable<SymmetricPair<TKey>> Members

    public bool Equals(SymmetricPair<TKey> other)
    {
        var comparer = EqualityComparer<TKey>.Default;
        if (comparer.Equals(Item1, other.Item1) && comparer.Equals(Item2, other.Item2))
            return true;
        if (comparer.Equals(Item2, other.Item1) && comparer.Equals(Item1, other.Item2))
            return true;
        return false;
    }

    #endregion

    public override bool Equals(object obj)
    {
        if (!(obj is SymmetricPair<TKey>))
            return false;
        return Equals((SymmetricPair<TKey>)obj);
    }

    public override int GetHashCode()
    {
        var comparer = EqualityComparer<TKey>.Default;
        // Note that the XOR operator is symmetric
        return comparer.GetHashCode(Item1) ^ comparer.GetHashCode(Item2);
    }

    public override string ToString()
    {
        return string.Format("SymmetricPair: ({0} {1})", Item1, Item2);
    }
}

public static partial class DictionaryExtensions
{
    // Extension methods for dictionaries of symmetric pairs.
    // https://unity3d.com/learn/tutorials/topics/scripting/extension-methods

    public static void Add<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary.Add(new SymmetricPair<TKey>(item1, item2), value);
    }

    public static void Set<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary[new SymmetricPair<TKey>(item1, item2)] = value;
    }

    public static bool Remove<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.Remove(new SymmetricPair<TKey>(item1, item2));
    }

    public static TValue Get<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary[new SymmetricPair<TKey>(item1, item2)];
    }

    public static bool TryGetValue<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, out TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.TryGetValue(new SymmetricPair<TKey>(item1, item2), out value);
    }
}

Sample fiddle #2.

Since Dictionary<TKey, TValue> is already designed to handle hash collisions, I would recommend that, before implementing your own replacement from scratch, you ask: is there any way I can use the existing Dictionary<TKey, TValue> type with two symmetric keys? And, in fact, this can be done, because a .Net dictionary can be constructed with a custom IEqualityComparer. Given that, your problem now simplifies to: how can I create an equality comparer between pairs of keys that is symmetric?

Assuming you have access to the Tuple or ValueTuple types, you can an IEqualityComparer that returns true if two 2-tuples have items that are identical or identical when swapped. Note that the comparer must be a proper equivalence relation by being reflexive, symmetric and transitive. Thus the implementation of IEqualityComparer.GetHashCode(x, y) must therefore return the same value for flipped tuples, i.e. comparer.GetHashCode(Tuple.Create(a, b)) == comparer.GetHashCode(Tuple.Create(b, a)) for all a and b.

The following comparers and dictionary extension methods can be used for this purpose:

public abstract class SymmetricTupleComparerBase<T> : IEqualityComparer<Tuple<T, T>>
{
    protected readonly IEqualityComparer<T> comparer = EqualityComparer<T>.Default;

    public bool Equals(Tuple<T, T> x, Tuple<T, T> y)
    {
        if (object.ReferenceEquals(x, y))
            return true;
        else if (object.ReferenceEquals(x, null) || object.ReferenceEquals(y, null))
            return false;

        if (comparer.Equals(x.Item1, y.Item1) && comparer.Equals(x.Item2, y.Item2))
            return true;
        if (comparer.Equals(x.Item1, y.Item2) && comparer.Equals(x.Item2, y.Item1))
            return true;
        return false;
    }

    public abstract int GetHashCode(Tuple<T, T> obj);
}

public class SymmetricTupleComparer<T> : SymmetricTupleComparerBase<T>
{
    public override int GetHashCode(Tuple<T, T> obj)
    {
        if (obj == null)
            return 0;
        return HashHelper.SymmetricCombineHash(comparer.GetHashCode(obj.Item1), comparer.GetHashCode(obj.Item2));
    }
}

public class SymmetricTupleComparerComplex<T> : SymmetricTupleComparerBase<T>
{
    public override int GetHashCode(Tuple<T, T> obj)
    {
        if (obj == null)
            return 0;
        return HashHelper.SymmetricCombineHashComplex(comparer.GetHashCode(obj.Item1), comparer.GetHashCode(obj.Item2));
    }
}

public static partial class HashHelper
{
    public static int SymmetricCombineHash(int code1, int code2)
    {
        // in case Item1 and Item2 are identical, code1 == code2 so code1 ^ code2 will always be zero.
        if (code1 == code2)
        {
            // As implemented in practice, hash codes seem to be biased towards small numbers, 
            // so reverse the bytes of the single-item hash to bias it towards a larger number.
            return ReverseBytes(code1);
        }
        // Note that the XOR operator is symmetric
        return code1 ^ code2;
    }

    public static int SymmetricCombineHashComplex(int code1, int code2)
    {
        // This can be useful when input hash codes are biased towards small integers by
        // expanding the input values to larger numbers.

        if (code1 == code2)
        {
            // in case Item1 and Item2 are identical, code1 == code2 so code1 ^ code2 will always be zero.
            return ReverseBytes(code1);
        }
        // Note that the multiplation operator is symmetric
        return unchecked(((ulong)~(uint)code1) * ((ulong)~(uint)code2)).GetHashCode();
    }

    public static Int32 ReverseBytes(Int32 value)
    {
        return unchecked((Int32)ReverseBytes((UInt32)value));
    }

    public static UInt32 ReverseBytes(UInt32 value)
    {
        // https://stackoverflow.com/questions/18145667/how-can-i-reverse-the-byte-order-of-an-int
        return (value & 0x000000FFU) << 24 | (value & 0x0000FF00U) << 8 |
            (value & 0x00FF0000U) >> 8 | (value & 0xFF000000U) >> 24;
    }
}

public static partial class DictionaryExtensions
{
    // Extension methods for dictionaries of symmetric pairs.
    // https://unity3d.com/learn/tutorials/topics/scripting/extension-methods

    public static void Add<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary.Add(Tuple.Create(item1, item2), value);
    }

    public static void Set<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary[Tuple.Create(item1, item2)] = value;
    }

    public static bool Remove<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.Remove(Tuple.Create(item1, item2));
    }

    public static TValue Get<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary[Tuple.Create(item1, item2)];
    }

    public static bool TryGetValue<TKey, TValue>(this IDictionary<Tuple<TKey, TKey>, TValue> dictionary, TKey item1, TKey item2, out TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.TryGetValue(Tuple.Create(item1, item2), out value);
    }
}

• SymmetricTupleComparerBase<T>.GetHashCode() checks whether the items are identical or identical when flipped.

• SymmetricTupleComparer<T>.GetHashCode() XOR's the hash codes of the items when not equal, or uses a hash of one of them when equal. Since XOR is symmetric, two tuples with flipped items will have the same hash code.

  This works well when the input hash codes are fairly randomly distributed among possible int values, such as with string hash codes.

• SymmetricTupleComparerComplex<T>.GetHashCode() uses a hash of the product of the two values as longs when not equal, or uses a hash of one of the values when equal. Since multiplication is symmetric, two tuples with flipped items will have the same hash code.

  This works better when the input hash codes are biased towards small numbers. E.g. Int32.GetHashCode() returns the integer value itself.

Now you can use the comparer and extension methods as follows:

var dictionary = new Dictionary<Tuple<int, int>, string>(new SymmetricTupleComparerComplex<int>());
dictionary.Set(1, 0, "hello");
Console.WriteLine(dictionary.Get(0, 1));

Sample fiddle with basic tests working.

public struct SymmetricPair<TKey> : IEquatable<SymmetricPair<TKey>>
{
    readonly TKey item1;
    readonly TKey item2;

    public SymmetricPair(TKey item1, TKey item2)
    {
        this.item1 = item1;
        this.item2 = item2;
    }

    public TKey Item1 { get { return item1; } }
    public TKey Item2 { get { return item2; } }

    #region IEquatable<SymmetricPair<TKey>> Members

    public bool Equals(SymmetricPair<TKey> other)
    {
        var comparer = EqualityComparer<TKey>.Default;
        if (comparer.Equals(Item1, other.Item1) && comparer.Equals(Item2, other.Item2))
            return true;
        if (comparer.Equals(Item2, other.Item1) && comparer.Equals(Item1, other.Item2))
            return true;
        return false;
    }

    #endregion

    public override bool Equals(object obj)
    {
        if (!(obj is SymmetricPair<TKey>))
            return false;
        return Equals((SymmetricPair<TKey>)obj);
    }

    public override int GetHashCode()
    {
        var comparer = EqualityComparer<TKey>.Default;
        var code1 = comparer.GetHashCode(Item1);
        var code2 = comparer.GetHashCode(Item2);
        
        // Here we use the fact that the XOR operator is symmetric
        return HashHelper.SymmetricCombineHash(code1, code2);
    }

    public override string ToString()
    {
        return string.Format("SymmetricPair: ({0} {1})", Item1, Item2);
    }
}

public static partial class HashHelper
{
    public static int SymmetricCombineHash(int code1, int code2)
    {
        // in case Item1 and Item2 are identical, code1 == code2 so code1 ^ code2 will always be zero.
        if (code1 == code2)
        {
            // As implemented hash codes seem to be biased towards small numbers, 
            // so reverse the bytes of the single-item hash to bias it towards a larger number.
            return ReverseBytes(code1);
        }
        // Note that the XOR operator is symmetric
        return code1 ^ code2;
    }

    public static int SymmetricCombineHashComplex(int code1, int code2)
    {
        // in case Item1 and Item2 are identical, code1 == code2 so code1 ^ code2 will always be zero.
        if (code1 == code2)
            return ReverseBytes(code1);
        // Note that the multiplation operator is symmetric
        return unchecked(((ulong)~(uint)code1) * ((ulong)~(uint)code2)).GetHashCode();
    }


    public static Int32 ReverseBytes(Int32 value)
    {
        return unchecked((Int32)ReverseBytes((UInt32)value));
    }

    public static UInt32 ReverseBytes(UInt32 value)
    {
        // https://stackoverflow.com/questions/18145667/how-can-i-reverse-the-byte-order-of-an-int
        return (value & 0x000000FFU) << 24 | (value & 0x0000FF00U) << 8 |
            (value & 0x00FF0000U) >> 8 | (value & 0xFF000000U) >> 24;
    }
}

public static partial class DictionaryExtensions
{
    // Extension methods for dictionaries of symmetric pairs.
    // https://unity3d.com/learn/tutorials/topics/scripting/extension-methods

    public static void Add<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary.Add(new SymmetricPair<TKey>(item1, item2), value);
    }

    public static void Set<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        dictionary[new SymmetricPair<TKey>(item1, item2)] = value;
    }

    public static bool Remove<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.Remove(new SymmetricPair<TKey>(item1, item2));
    }

    public static TValue Get<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary[new SymmetricPair<TKey>(item1, item2)];
    }

    public static bool TryGetValue<TKey, TValue>(this IDictionary<SymmetricPair<TKey>, TValue> dictionary, TKey item1, TKey item2, out TValue value)
    {
        if (dictionary == null)
            throw new ArgumentNullException();
        return dictionary.TryGetValue(new SymmetricPair<TKey>(item1, item2), out value);
    }
}

Sample fiddle #2.