c# - Use custom object as Dictionary Key

Question

I want to use a custom object as a Dictionary key, mainly, I have something like this: (I can't use .net 4.0 so I don't have tuples)

class Tuple<A, B> : IEquatable<Tuple<A,B>>
{
  public A AValue { get; set; }
  public B BValue { get; set; }

  public Tuple(A a, B b){ AValue = a; BValue = b; }

  public bool Equals(Tuple<A, B> tuple)
  {
    return tuple.AValue.Equals(AValue) && tuple.BValue.Equals(BValue);
  }

  public bool Equals(object o)
  {
  return this.Equals(o as Tuple<A,B>);
  }
}

I then do something like this.

  var boolmap = new Dictionary<Tuple<bool, bool>, string>();
  boolmap.Add(new Tuple<bool,bool>(true, true), "A");
  boolmap.Add(new Tuple<bool,bool>(true, false), "B");
  boolmap.Add(new Tuple<bool,bool>(false, true), "C");
  boolmap.Add(new Tuple<bool,bool>(false, false), "D");
  var str = boolmap[new Tuple<bool,bool>(true, false)];

I get a KeyNotFound exception at the last line. Why is this ? Isn't it enough I implement IEquatable ?

Thanks

Answer 1

You also need to override GetHashCode() (and preferably also Equals()). Your otherwise-equal object is returning a different hash code, which means that the key is not found when looked up.

The GetHashCode() contract specifies that the return value from two objects MUST be equal when the two objects are considered equal. This is the root of your problem; your class does not meet this requirement. The contract does not specify that the value must be different if they are not equal, but this will improve performance. (If all of the objects return the same hash code, you may as well use a flat list from a performance perspective.)

A simple implementation in your case might be:

public override int GetHashCode()
{
    return AValue.GetHashCode() ^ BValue.GetHashCode();
}

Note that it might be a good idea to test if AValue or BValue are null. (This will be somewhat complicated since you don't constrain the generic types A and B, so you cannot just compare the values to null -- the types could be value types, for example.)¹

It's also a good idea to make classes you intend to use as dictionary keys immutable. If you change the value of an object that is being used as a key, the dictionary will exhibit weird behavior since the object is now in a bucket where it doesn't belong.

---

¹ Note that you could make use of EqualityComparer<A>.Default.GetHashCode(AValue) (and similar for BValue) here, as that will eliminate the need for a null check.