CODEWITHSUNDEEP
c#.net
Anders Forsgren
Anders Forsgren

Reputation: 11101

Dictionary KeyCollection Strangeness

I have a mysterious situation involving a dictionary where I enumerate keys from the dictionary, but the dictionary doesn't contain some of the keys it says it contains.

Dictionary<uint, float> dict = GetDictionary(); // Gets values, 6268 pairs
foreach(uint key in dict.Keys)
{
   if (!dict.ContainsKey(key))
      Console.WriteLine("Wat? "+key);
}

The above will print two of the 6268 keys. Nothing special about those two keys, both positive values smaller than Int32.MaxValue (369099203 and 520093968).

A check on the counts reveals this:

Console.WriteLine(dict.Count);                           // 6268
Console.WriteLine(dict.Keys.Count());                    // 6268
Console.WriteLine(dict.Keys.Count(dict.Keys.Contains));  // 6266

This is single threaded .NET4 code running under .NET4.5 CLR. The dictionary is a vanilla Dictionary<uint, float> i.e. there is no custom equality comparer. I assume there is a hash problem occuring because of the uint/int difference, but shouldn't the ContainsKey(key) be guaranteed to be true for all keys returned in the Key collection of the dictionary? Especially when you ONLY look at the KeyCollection object as in the lower code snippet, there the total count and the count of contained objects is off, which feels like an odd ICollection behavior.

Edit:

As expected there appears to be a reasonable explanation: the collection was modified earlier by two concurrent threads during its initialization. When something "sometimes breaks" , it is a threadnig issue, and sure enough. Accessing a dict from several threads can apparently upset the internal state enough for it to be kust semi-functioning for the remainder of its lifetime, but without causing any exceptions.

I'm going to switch to a concurrent dictionary, and probably delete this question. Thanks.

Upvotes: 4

Views: 442

Answers (4)

Giacomo Tesio
Giacomo Tesio

Reputation: 7210

I encountered similar weird behaviours with System.Uri too.

It turned to be an architecture mismatch between the key that was stored in the dictionary and the key that I was using to lookup. In particular, the Uri stored in the dictionary was 32bit, while I was looking for a 64bit one. Obviously, since GetHashcode() is not granted to be equal between different architectures, the dictionary was unable to match the keys.

Upvotes: 0

Sam Harwell
Sam Harwell

Reputation: 99889

Important note: When I refer to GetHashCode throughout this post, I am referring to the result of IEqualityComparer<T>.GetHashCode. By default, the dictionary will use EqualityComparer<T>.Default, which will return the result of calling GetHashCode on the key itself. However, you can provide a specific implementation of IEqualityComparer<T> at the time the dictionary is created to use a different behavior.

This can happen if the result of GetHashCode for a key changes between the time the value is added to the dictionary and the point where you enumerated the keys. When you enumerated the keys, it returns the keys for all populated "buckets" in the array. However, when you look up a specific key it recalculates the expected bucket from the result of GetHashCode for the key. If the hash code changed, then the actual location of the key/value pair in the dictionary's buckets and the expected location may no longer be the same, in which case Contains would return false.

You should make sure that the result of GetHashCode for the keys in the dictionary can't change after a value is added to the dictionary for the key.

Upvotes: 0

JustAndrei
JustAndrei

Reputation: 859

Is there a chance of that GetDictionary() adds custom key equality comparer when constructing the dictionary? If so, the problem may be related to the comparer implementation.

Upvotes: 1

sidestepper
sidestepper

Reputation: 115

I don't have enough rep to comment - but I did try to reproduce your issue to no avail. I will suggest that you post how GetDictionary() is working and also I would suggest NOT iterating through a dictionary like that, do below instead and see if that seems to fix it:

foreach (KeyValuePair<uint, float> pair in dict)
    Console.WriteLine("[" + pair.Key + "]=" + pair.Value);

Upvotes: 1

Related Questions