"the given key was not present in the dictionary" error when using a self-defined class as key

Question

I've got code like this:

if (CounterForEachRelatedTagDict.Select(x => x.Key).Contains(tag.Key))
   CounterForEachRelatedTagDict[tag.Key] += tag.Value;

Is it possible that the IF statement returns true, at the same time CounterForEachRelatedTagDict[tag.Key] returns "the given key was not present in the dictionary" error? tag is a KeyValuePair<MyClass,int>.

CounterForEachRelatedTagDict is initiated like this:

Dictionary<MyClass, int> CounterForEachRelatedTagDict = new Dictionary<MyType, int>();

MyClass is like this

public class MyClass
{
    public string name {get;set;}
    public Guid Id { get; set; }
    ...
}

It seems almost unreasonable to me...

Answer 1

The problem is that your Equal and GetHashCode methods are out of sync for MyType.

When you use CounterForEachRelatedTagDict.Select(x => x.Key).Contains(tag.Key) you're performing a linear search through all of the keys using Equals to compare what you're searching for to each key.

When you use ContainsKey in Dictionary, the indexer, or one of a number of other methods for finding a key you first hash the key using GetHashCode and then it only uses Equals to find which of the (hopefully very few objects) are identical within that bucket.

What's happening is that you have two object for which first.Equals(second) returns true, but for which GetHashCode returns two different values. It's very important that, when using objects as keys in a Dictionary, any two objects for which Equals returns true must also return the same integer for GetHashCode. Ideally different objects should return different hash codes whenever possible, but it's not always possible (different objects with the same hash code are called "collisions").

Note that this method of finding keys, while it does force you to ensure all objects used as keys have sensible implementations of GetHashCode (the default implementation that comes from object is rarely appropriate) this algorithm is * extraordinary* efficient (with efficient hashing algorithms) which is what makes it worthwhile. Using ContainsKey, or the indexer of the dictionary, is much, much faster than going through each key and comparing it, which is what your Select code needs to do to avoid using GetHashCode.

So, to answer your question, yes, it's quite possible for CounterForEachRelatedTagDict.Select(x => x.Key).Contains(tag.Key) to find an item while the indexer can't.

Answer 2

First:You can use the ContainsKey method instead of that Linq Query.

Second: You must override the GetHashCode and Equals for MyType. that's the way that Dictionary look up and compare the keys.

Check out these similar questions: Dictionary.ContainsKey return False, but a want True, Using an object as a generic Dictionary key

Answer 3

To use your type as a dictionary key you should override two methods: GetHashCode and Equals.

By default (if you'll not override GetHashCode) every object of your type (even with the same field values) will return unique value. This means that you'll be able to find only exactly the same "reference" that you'll put into your dictionary. Consider following two types: MyType1 that not overrides GetHashCode and Equals, and MyType2 that do:

class MyType1
{
  public MyType1(int id, string name) {Id = id; Name = name;}
  public int Id {get; private set;}
  public string Name {get; private set;}
}


internal class MyType2
{
    public MyType2(int id, string name)
    {
        Id = id;
        Name = name;
    }

    public int Id { get; private set; }
    public string Name { get; private set; }

    bool Equals(MyType2 other)
    {
        return Id == other.Id && string.Equals(Name, other.Name);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((MyType2) obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (Id*397) ^ Name.GetHashCode();
        }
    }
}

var d1 = new Dictionary<MyType1, int>();
d1[new MyType1(1, "1")] = 1;
d1[new MyType1(1, "1")]++; // will throw withKeyNotFoundException

var d2 = new Dictionary<MyType2, int>();
d1[new MyType2(1, "1")] = 1;
d1[new MyType2(1, "1")]++; // Ok, we'll find appropriate record in dictionary