Reputation: 9085
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:
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.
Upvotes: 5
Views: 2164
Reputation: 5980
Is this a homework? It looks like a problem from a book.
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.)HashSet<Key>
.Upvotes: 2
Reputation: 11101
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;
}
}
}
}
Upvotes: 2
Reputation: 3935
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.
Upvotes: 2
Reputation: 564413
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.
Upvotes: 6