Geek Answers Handbook

List or dictionary of two key tuples

I have a set of two-digit pairs of strings {(a1, b1), (a2, b2), (a3, b3), ...}. In my scenario (a1, b1) == (b1, a1), so the combination of (a1, b1) or (b1, a1) should be part of my set only once.

In a C # application, I need to be able to:

  • Add new pairs of these (a, b) tuples
  • Effectively (i.e. quickly) check if the pair (a1, b1) or (b1, a1) is in my table.

How would you implement something like this using the dictionary [Tuple [K1, K2]] or something else? If you use the dictionary, is there any way to tell him to consider (K1, K2) the same as (K2, K1), so I would not need to add both combinations? Or perhaps add both (K1, K2) and (K2, K1)?

Thanks.

+4
source share
4 answers

Create a storage class that displays the Add (a, b) functions and similar functions. The internal memory may be a HashSet<T> , where T is a suitable row key. The only thing that is important with respect to this key and the comparator is to use hash functions and equality functions that are symmetric, i.e. That (a, b) is equal to (b, a) and therefore hash (a, b) == hash (b, a).

As stated earlier, many hash functions have this property, such as sums and xor hash values. I decided not to use xor, because this means that all pairs of the same lines will have a zero hash, which can probably lead to an inefficient search if pairs of equal lines are likely.

The implementation below assumes that all lines are not null but do not have 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 (xA == yA && xB == yB) || (xA == yB && xB == yA); } public int GetHashCode(Key k) { int aHash = kAGetHashCode(); int bHash = kBGetHashCode(); // Hash for (x,y) same as hash for (y,x) if (aHash > bHash) return bHash * 37 + aHash; return aHash * 37 + bHash; } } } }
+2
source

Create your own class that implements IEquatable (and make sure it overrides GetHashCode correctly). You can then use this in a HashSet<T> , and two pairs can be made "equal" automatically.

+6
source

Is this homework? This seems like a problem from a book.

  • Define a Key class, define equalities and hash operators and methods. (This means that you must define the Equals method, operator == , the GetHashCode method, and possibly other methods if the compiler wants them.)
  • Use a HashSet<Key> .
+2
source

I would use a dictionary in which the key is generated by a function that takes 2 lines and generates a hash as follows: compare both lines, create a shortened line that consists of the line “smaller” line + separator + “large” line, so the order has no values. a similar "equal" operator can also be implemented.

+2
source

More articles:


All Articles