List or dictionary of two key tuple

c#, dictionary

Solution

Create a storage class exposing Add(a, b) and similar functions. The internal storage can be a `HashSet<T>` where T is a suitable string-tuple key. The only thing important about this Key and comparer is to use hash and equality functions that are symmetric, i.e. that (a,b) equals (b,a), and consequently that hash(a,b) == hash(b,a).

As pointed out earlier, a lot of hash functions has this property, for example sums and xor of the hash values. I chose to not use xor because it means that all pairs of equal strings would have hash zero, which probably could lead to inefficient lookup if pairs of equal strings are likely.

The below implementation assumes all strings are non null, but has no error checking.

public class Storage
{
   private HashSet<Key> set;

   public Storage()
   {
      set = new HashSet<Key>(new Key.Comparer());
   }

   public void Add(string a, string b)
   {
      set.Add(new Key{A=a, B=b});
   }

   public bool Contains(string a, string b)
   {
      return set.Contains(new Key{A=a, B=b});
   }

   internal class Key
   {
       internal String A { get; set; }
       internal String B { get; set; }
       internal class Comparer : IEqualityComparer<Key>
       {
          public bool Equals(Key x, Key y)
          {
             return (x.A == y.A && x.B == y.B) || (x.A == y.B && x.B == y.A);
          }
          public int GetHashCode(Key k)
          {
             int aHash = k.A.GetHashCode();
             int bHash = k.B.GetHashCode();
             // Hash for (x,y) same as hash for (y,x)
             if (aHash > bHash)
                return bHash * 37 + aHash;
             return aHash * 37 + bHash;
          }
       }
   }

}

Problem

I have a set of two-key pairs of strings { (a1, b1), (a2, b2), (a3, b3), ... }. In my scenario (a1, b1) == (b1, a1), so a (a1, b1) or (b1, a1) combination should be part of my set only once. In a C# application I need to be able to: - Add a new pairs of these (a,b) tuples - Efficiently (i.e. fast) check if a pair of (a1, b1) or (b1, a1) is already in my table. How would you implement something like this, with a Dictionary[Tuple[K1, K2]], or something else? If using a Dictionary, is there any way to tell it to consider (K1,K2) the same as (K2, K1) so I wouldn't have to add both combinations? Or maybe adding both (K1, K2) and (K2, K1) is the way to go? Thanks.

Original source