C# Dictionary throws KeyNotFoundException when key exists

Question

I am storing a 2D array that represents a distance matrix between vectors as a Dictionary<DistanceCell, double>. My implementation of DistanceCell has two string fields representing the vectors being compared.

class DistanceCell
{
    public string Group1 { get; private set; }
    public string Group2 { get; private set; }

    public DistanceCell(string group1, string group2)
    {
        if (group1 == null)
        {
            throw new ArgumentNullException("group1");
        }

        if (group2 == null)
        {
            throw new ArgumentNullException("group2");
        }

        this.Group1 = group1;
        this.Group2 = group2;
    }
}

Since I'm using this class as a key, I overrode Equals() and GetHashCode():

public override bool Equals(object obj)
{
    // False if the object is null
    if (obj == null)
    {
        return false;
    }

    // Try casting to a DistanceCell. If it fails, return false;
    DistanceCell cell = obj as DistanceCell;
    if (cell == null)
    {
        return false;
    }

    return (this.Group1 == cell.Group1 && this.Group2 == cell.Group2) 
           || (this.Group1 == cell.Group2 && this.Group2 == cell.Group1);
}

public bool Equals(DistanceCell cell)
{
    if (cell == null)
    {
        return false;
    }

    return (this.Group1 == cell.Group1 && this.Group2 == cell.Group2) 
           || (this.Group1 == cell.Group2 && this.Group2 == cell.Group1);
}

public static bool operator ==(DistanceCell a, DistanceCell b)
{
    // If both are null, or both are same instance, return true.
    if (System.Object.ReferenceEquals(a, b))
    {
        return true;
    }

    // If either is null, return false.
    // Cast a and b to objects to check for null to avoid calling this operator method
    // and causing an infinite loop.
    if ((object)a == null || (object)b == null)
    {
        return false;
    }

    return (a.Group1 == b.Group1 && a.Group2 == b.Group2) 
           || (a.Group1 == b.Group2 && a.Group2 == b.Group1);
}

public static bool operator !=(DistanceCell a, DistanceCell b)
{
    return !(a == b);
}

public override int GetHashCode()
{
    int hash;
    unchecked
    {
        hash = Group1.GetHashCode() * Group2.GetHashCode();
    }

    return hash;
}

As you can see, one of the requirements of DistanceCell is that Group1 and Group2 are interchangeable. So for two strings x and y, DistanceCell("x", "y") must equal DistanceCell("y", "x"). This is why I implemented GetHashCode() with multiplication because DistanceCell("x", "y").GetHashCode() must equal DistanceCell("y", "x").GetHashCode().

The problem that I'm having is that it works correctly roughly 90% of the time, but it throws a KeyNotFoundException or a NullReferenceException the remainder of the time. The former is thrown when getting a key from the dictionary, and the latter when I iterate over the dictionary with a foreach loop and it retrieves a key that is null that it then tries to call Equals() on. I suspect this has something to do with an error in my GetHashCode() implementation, but I'm not positive. Also note that there should never be a case where the key wouldn't exist in the dictionary when I check it because of the nature of my algorithm. The algorithm takes the same path every execution.

Update

I just wanted to update everyone that the problem is fixed. It turns out that it had nothing to do with my Equals() or GetHashCode() implementation. I did some extensive debugging and found that the reason I was getting a KeyNotFoundException was because the key didn't exist in the dictionary in the first place, which was strange because I was positive that it was being added. The problem was that I was adding the keys to the dictionary with multiple threads, and according to this, the c# Dictionary class isn't thread-safe. So the timing must have been perfect that an Add() failed and thus the key was never added to the dictionary. I believe this can also explain how the foreach loop was bringing up a null key on occasion. The Add()'s from multiple threads must have messed up some internal structures in the dictionary and introduced a null key.

Thanks to every one for your help! I'm sorry that it ended up being a fault entirely on my end.

Answer 1

Take a look at this blog post by Eric Lippert

It says that the result of GetHashCode should never change even if you change the content of the object. The reason is that Dictionary is using buckets for faster indexing. Once you change the GetHasCode result, the Dictionary will not be able to find the right bucket for your object and this can lead to "Key not found"

I might be wrong, but it is worth testing.

Answer 2

I believe what is missing for you is this answer Using an object as a generic Dictionary key

You probably not stating you implement IEquatable interface

Answer 3

To me your code looks correct. (It can possibly be (micro-)optimized, but it looks as if it will be correct in all cases.) Can you provide some code where you create and use the Dictionary<DistanceCell, double>, and things go bad? The problem may lie in code you haven't shown us.