Dictionary.GetKey Returns False Even Though Key Is Present - GetHashCode/Equals Already Overridden

Question

This is in C#. I have a problem whereby Dictionary.ContainsKey returns false even though I know the key to be in there.

I don't have any code to show unfortunately. The code is not easy to pull together; it is spread across multiple classes and triggered through events and so on. A quick unit test I wrote didn't reproduce the problem.

Here is the output of the immediate window during a debugging session (added comments and changed to protect details):

// throws KeyNotFoundException
myDict[key]  

// throws KeyNotFoundException
myDict[new MyKey("SomeString .1", "SomeOtherString", SomeEnum.Foo)]

// Element [5] is the key
myDict.Keys
Count = 10
    [0]: {...}
    [1]: {...}
    [2]: {...}
    [3]: {...}
    [4]: {...}
    [5]: {Foo SomeOtherString SomeString  .1}
    [6]: {...}
    [7]: {...}
    [8]: {...}
    [9]: {...}

// Get key at element [5]   
enumerator.Current
{Foo SomeOtherString SomeString  .1}
    [My.Namespace.KeyType]: {Foo SomeOtherString SomeString  .1}
    SomeEnum: Foo
    SomeOtherStringProperty: "SomeOtherString"

// key used to do lookup
key
{Foo SomeOtherString SomeString  .1}
    [My.Namespace.KeyType]: {Foo SomeOtherString SomeString  .1}
    SomeEnum: Foo
    SomeOtherStringProperty: "SomeOtherString"

// hash codes of key in dictionary matches hash code of lookup key
enumerator.Current.GetHashCode()
193014103
key.GetHashCode()
193014103

Some extra notes:

The type used as the key has overridden methods for GetHashCode and Equals.
The dictionary is constructed as new Dictionary() with no extra constructor arguments.
By debugging, I've verified that GetHashCode in the key type is called, but not Equals(obj)
When the application runs, there's only one DLL loaded that has the key type, so it's probably not a case of the same type in different versions of the same DLL

Does anyone know why this might be occuring?

Thanks for any help - I'm running out of ideas here.

score 4 · Accepted Answer · edited Jun 20 '20 at 09:12

4

The type used as the key has overridden methods for GetHashCode and Equals.

This is the first thing that I would check. If the hash code is based on a mutable value, it could definitely cause this problem.

From MSDN:

In general, for mutable reference types, you should override GetHashCode only if:

You can compute the hash code from fields that are not mutable; or

You can ensure that the hash code of a mutable object does not change while the object is contained in a collection that relies on its hash code.

Otherwise, you might think that the mutable object is lost in the hash table. If you do choose to override GetHashCode for a mutable reference type, your documentation should make it clear that users of your type should not modify object values while the object is stored in a hash table.

edited Jun 20 '20 at 09:12

Community

1
1

answered Sep 10 '14 at 00:48

itsme86

19,266
4
41
57

Indeed. If you mutate properties that participate in GetHashCode/Equality comparisons while the object in question is stored in a Dictionary (or any HashTable-like structure), you'll corrupt the Dictionary and all bets are off. All properties that participate in GetHashCode and Equality really should be immutable. Don't rely on documentation for this. – spender Sep 10 '14 at 00:51
Thanks. However, given that all the output of the immediate window above was taken while the app was held on a breakpoint and the hash codes were the same, it seems unlikely this was the problem. Am I missing something? – ck. Sep 10 '14 at 00:53
1

@ck: That the Dictionary corruption had occurred prior to the breakpoint, i.e. you mutated the key after it went into the dictionary causing it to generate a different code to the one that was used by the Dictionary to store it. Yes, you can enumerate the keys, but because they were stored against a different hash code, you can't find it. – spender Sep 10 '14 at 00:54
@spender: Good point. To test this, I got to the same breakpoint, then created in the immediate window an instance of MyKey using the same property values I expected the key in the dictionary to have. Both the immediate window's newly created key, and the key in the dictionary have the same hash code. – ck. Sep 10 '14 at 01:05
@ck: Sure, but did the key in the dictionary have the same hash code **at the moment when it was stored in the dictionary**? If not, your key lookup will fail because the item is in the wrong hashtable bucket. – spender Sep 10 '14 at 01:08
Checked out the code and I think you're right - thanks for the help! – ck. Sep 10 '14 at 20:20

Dictionary.GetKey Returns False Even Though Key Is Present - GetHashCode/Equals Already Overridden

1 Answers1