Dictionary KeyCollection Oddity

Question

I have a mysterious situation using a dictionary, where I list the keys from the dictionary, but the dictionary does not contain some keys, which, according to him, contain.

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 version will output two of the 6268 keys. There is nothing special about these two keys, both positive values ​​are less than Int32.MaxValue (369099203 and 520093968).

A check on the counts shows this:

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

This is a single-threaded .NET4 code running under the .NET4.5 CLR. Dictionary is vanilla Dictionary<uint, float> ie there is no personalized comparison comparator . I assume there is a hash problem due to the uint / int difference, but should it not be guaranteed that ContainsKey(key) will be true for all keys returned in the dictionary key collection? Especially when you ONLY look at the KeyCollection object, as in the bottom code fragment, the total number and number of contained objects is calculated here, which is similar to the odd behavior of ICollection .

Edit:

As expected, there is a reasonable explanation: the collection was previously modified by two parallel threads during its initialization. When something "sometimes breaks", it is a thread problem and, of course, enough. Access to a dict from multiple threads can apparently violate an internal state sufficient to be semi-synchronized for the remainder of its life, but without causing any exceptions.

I am going to switch to a parallel dictionary and possibly delete this question. Thanks.

Answer 1

I do not have enough comments for comments, but I tried to reproduce your problem to no avail. I suggest you publish how GetDictionary () works, and also I suggest NOT Iterate through such a dictionary, do below and see if this fixes it:

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

Answer 2

Is there any chance that GetDictionary () will add its own key equality resolver when building the dictionary? If so, the problem may be with the implementation of the comparison.

Answer 3

Important Note: When I refer to GetHashCode on this post, I mean the result of IEqualityComparer<T>.GetHashCode . By default, the dictionary will use EqualityComparer<T>.Default , which will return the result of calling GetHashCode the key itself. However, you can provide a concrete implementation of IEqualityComparer<T> while the dictionary is designed to use a different behavior.

This can happen if the GetHashCode result for the key changes between the time the value was added to the dictionary and the point at which you listed the keys. When you list the keys, it returns the keys for all filled buckets in the array. However, when you look at a specific key, it recounts the expected bucket from the GetHashCode result for the key. If the hash code has changed, then the actual location of the key / value pair in the dictionary and the expected location may no longer be the same, in which case Contains will return false.

You must make sure that the result of GetHashCode for keys in the dictionary cannot change after adding the dictionary value for the key.

Answer 4

I also came across similar weird behavior with System.Uri.

It turned out to be an architecture mismatch between the key that was stored in the dictionary and the key that I used to search. In particular, the Uri stored in the dictionary was 32 bits, while I was looking for 64-bit. Obviously, since GetHashcode () cannot be equal between different architectures , the dictionary could not match keys.