Dictionary does not contain key despite Comparer.Equals returning true

Question

I've been hunting down a bug where I have a dictionary that insists on saying a key does not exist, despite its comparer actually saying that it does. For example, in the following snippet, the exception is thrown:

if (!dictionary.ContainsKey(key))
{
    var comparer = dictionary.Comparer;

    foreach (var _key in dictionary.Keys)
    {
        if (comparer.Equals(key, _key) &&
            comparer.Equals(_key, key) &&
            comparer.GetHashCode(key) == comparer.GetHashCode(_key) &&
            comparer.GetHashCode(_key) == comparer.GetHashCode(key))
        {
            throw new Exception("Key exists, but dictionary doesn't find it");
        }
    }
}

The dictionary is a generic Dictionary<TKey, TValue> with the default equality comparer (empty constructor). The TKey class implements proper GetHashCode and Equals methods.

Is there anything I might be missing here? I'm at a complete loss!

Did the hash code change after you added it to the dictionary? — , Jan 30 '18 at 17:35
As usual true [MCVE] would have exposed the issue... https://stackoverflow.com/questions/3007296/c-sharp-dictionary-and-mutable-keys can probably be considered duplicate. — Alexei Levenkov, Jan 30 '18 at 18:08

score 7 · Accepted Answer · answered Jan 30 '18 at 17:38

The only way this could happen is if the key is mutable, and its content has been changed after it has been inserted into the dictionary.

Here is how it happens:

You insert a key into a dictionary; the dictionary gets its hash code, and puts it into a corresponding hash bucket, resolving conflicts by calling Equals
You mutate the key; now its hash code no longer corresponds to its hash bucket
You call ContainsKey. The dictionary looks for the key in its new bucket. Since the key is not there, false is reported
When you iterate the dictionary, all keys are returned, including ones that are no longer in their legitimate buckets. That's why you get a hit in the foreach loop.

That was indeed the case! `GetHashCode` depended on a mutable property. It was driving me mad, thank you! — Lazlo, Jan 30 '18 at 17:42

Dictionary does not contain key despite Comparer.Equals returning true

1 Answers1