List or dictionary of two key tuple

Question

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.

Answer 1

Make a custom class that implements IEquatable (and make sure to properly override GetHashCode). You can then use this in a HashSet<T>, and the two pairs can be made "equal" automatically.

Answer 2

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;
          }
       }
   }

}

Answer 3

I would use a dictionary where the key is generated by a function which accepts 2 strings and generates the hash like this: compare both strings, build a concated string which is made of the "smaller" string + seperator+ " larger" string. this way order doesn't matter. a similar "equals" operator can also be implemented.

Answer 4

Is this a homework? It looks like a problem from a book.

1. Define class Key, define equality and hash operators and methods. (It means you should define method Equals, operator ==, method GetHashCode, and possibly other methods if compiler will want them.)
2. Use HashSet<Key>.