Retrieved Dictionary Key Not Found

Question

I have a SortedDictionary declared like such:

SortedDictionary<MyObject,IMyInterface> dict = new SortedDictionary<MyObject,IMyInterface>();

When its populated with values, if I grab any key from the dictionary and then try to reference it immediately after, I get a KeyNotFoundException:

MyObject myObj = dict.Keys.First();
var value = dict[myObj];     // This line throws a KeyNotFoundException

As I hover over the dictionary (after the error) with the debugger, I can clearly see the same key that I tried to reference is in fact contained in the dictionary. I'm populating the dictionary using a ReadOnlyCollection of MyObjects. Perhaps something odd is happening there? I tried overriding the == operator and Equals methods to get the explicit comparison I wanted, but no such luck. That really shouldn't matter since I'm actually getting a key directly from the Dictionary then querying the Dictionary using that same key. I can't figure out what's causing this. Has anyone ever seen this behavior?

EDIT 1

In overriding Equals I also overloaded (as MS recommends) GetHashCode as well. Here's the implementation of MyObject for anyone interested:

public class MyObject
{
public string UserName { get; set;}
public UInt64 UserID  { get; set;}

    public override bool Equals(object obj)
    {
        if (obj == null || GetType()!= obj.GetType())
        {
            return false;
        }

        // Return true if the fields match:
        return this.Equals((MyObject)obj);
    }

    public bool Equals(MyObject other)
    {
        // Return true if the fields match
        return this.UserID == other.UserID;
    }

    public override int GetHashCode()
    {
        return (int)this.UserID;
    }


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

    // If one is null, but not both, return false.
    if (((object)a == null) || ((object)b == null))
    {
        return false;
    }

    // Return true if the fields match:
    return a.UserID == b.UserID
}

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

What I noticed from debugging is that if I add a quick watch (after the KeyNotFoundException is thrown) for the expression:

dict.ElementAt(0).Key == value;

it returns true. How can this be?

EDIT 2 So the problem ended up being because SortedDictionary (and Dictionary as well) are not thread-safe. There was a background thread that was performing some operations on the dictionary which seem to be triggering a resort of the collection (adding items to the collection would do this). At the same time, when the dictionary iterated through the values to find my key, the collection was being changed and it was not finding my key even though it was there.

Sorry for all of you who asked for code on this one, I'm currently debugging an application that I inherited and I didn't realize this was going on on a timed, background thread. As such, I thought I copied and pasted all the relevant code, but I didn't realize there was another thread running behind everything manipulating the collection.

Answer 1

It appears that the problem ended up being because SortedDictionary is not thread-safe. There was a background thread that was performing some operations on the dictionary (adding items to the collection) which seems to be triggering a resort of the collection. At the same time, when the dictionary was attempting to iterate through the values to find my key, the collection was being changed and resorted, rendering the enumerator invalid, and it was not finding my key even though it was there.

Answer 2

I have a suspicion - it's possible that you're changing the UserID of the key after insertion. For example, this would demonstrate the problem:

var key = new MyObject { UserId = 10 };
var dictionary = new Dictionary<MyObject, string>();
dictionary[key] = "foo";

key.UserId = 20; // This will change the hash code

var value = dict[key]; // Bang!

You shouldn't change properties involved in equality/hash-code considerations for an object which is being used as the key in a hash-based collection. Ideally, change your code so that this can't be changed - make UserId readonly, initialized on construction.

The above definitely would cause a problem - but it's possible that it's not the same as the problem you're seeing, of course.

Answer 3

In addition to overloading == and Equals, make sure you override GetHashCode with a suitable hash function. In particular, see this specification from the documentation:

• If two objects compare as equal, the GetHashCode method for each object must return the same value. However, if two objects do not compare as equal, the GetHashCode methods for the two objects do not have to return different values.
• The GetHashCode method for an object must consistently return the same hash code as long as there is no modification to the object state that determines the return value of the object's Equals method. Note that this is true only for the current execution of an application, and that a different hash code can be returned if the application is run again.
• For the best performance, a hash function should generate an even distribution for all input, including input that is heavily clustered. An implication is that small modifications to object state should result in large modifications to the resulting hash code for best hash table performance.
• Hash functions should be inexpensive to compute.
• The GetHashCode method should not throw exceptions.

---

I agree with Jon Skeet's suspicion that you're somehow unintentionally modifying UserID property after it's added as a key. But since the only property that's important for testing equality in MyObject is UserID (and therefore that's the only property that the Dictionary cares about), I'd recommend refactoring your code to use a simple Dictionary<ulong, IMyInterface> instead:

Dictionary<ulong, IMyInterface> dict = new Dictionary<string, IMyInterface>();
ulong userID = dict.Keys.First();
var value = dict[userID];