new KeyValuePair(i, j).GetHashCode(); High Rate of Duplicates

Question

In search of a fast composite key for Dictionary I came upon anomaly I cannot understand nor justify. In limited testing ``` Dictionary, string> ``` is significantly slower (200:1) than ``` Dictionary, string> ``` Test on two loops from 0 to 1000 Populate and then ContainsKey ``` Poplulate ContainsKey UInt32 92085 86578 UInt16 2201 431 ``` The problem is that ``` new KeyValuePair(i, j).GetHashCode(); ``` yields MANY duplicates. In looping i and j 1024 only 1024 unique hash values are created. Based on avalanche comment from CasperOne tried i*31 and j*97 (two prime numbers) and that resulted in 105280 unique on 1024X1024. Still a lot of duplicates. CasperOne I know that is not the same as random. But it is not my job to randomize the input. GetHashCode() is supposed to randomize the output. Why the high number of duplicates? Same loop on ``` new KeyValuePair(i, j).GetHashCode(); ``` yields 1024 X…

Accepted Answer

Firstly, we can dispense with the timing aspect of this - it feels to me like this is really just about hash collisions, as obviously those will kill the performance. So, the question is really why there are more hash collisions for `KeyValuePair` than `KeyValuePair`. To help find out a bit more about that, I've written the following short program: ``` using System; using System.Collections.Generic; class Program { const int Sample1 = 100; const int Sample2 = 213; public static void Main() { Display(); Display(); Display(); Display(); } static void Display() { TKey key1 = (TKey) Convert.ChangeType(Sample1, typeof(TKey)); TValue value1 = (TValue) Convert.ChangeType(Sample1, typeof(TValue)); TKey key2 = (TKey) Convert.ChangeType(Sample2, typeof(TKey)); TValue value2 = (TValue) Convert.ChangeType(Sample2, typeof(TValue)); Console.WriteLine("Testing {0}, {1}", typeof(TKey).Name, typeof(TValue).Name); Console.WriteLine(new KeyValuePair(key1, value1).GetHashCode()); Console.WriteLine(new KeyValuePair(key1, value2).GetHashCode()); Console.WriteLine(new KeyValuePair(key2, value1).GetHashCode()); Console.WriteLine(new KeyValuePair(key2, value2).GetHashCode()); Console.WriteLine(); } } ``` The output on my machine is: ``` Testing UInt32, UInt16 -1888265981 -1888265981 -1888265806 -1888265806 Testing UInt16, UInt16 -466800447 -459525951 -466800528 -459526032 Testing UInt32, UInt32 958334947 958334802 958334802 958334947 Testing UInt16, UInt32 -1913331935 -1913331935 -1913331935 -1913331935 ``` You can obviously try varying the sample values to see where there are collisions. The results of `KeyValuePair` are particularly worrying, and the results of `KeyValuePair` are surprisingly good. In fact, `KeyValuePair` isn't just bad - it's ludicrously bad as far as I can see - I haven't to find any value which doesn't have the same hash code of -1913331935 when running the 64 bit CLR. Running the 32 bit CLR I get a different hash code, but still the same hash code for all values. It appears that in .NET 4.5 (which is what I'm running) the default implementation of `GetHashCode` doesn't just take the first instance field of the struct, as previously documented. I suspect that for at least some types, it just uses the first 4 bytes of memory beyond the header in the boxed value (and there will be boxing for every call here), and that ends up sometimes being just the first field (if that field is a `uint`), sometimes being more than one field (e.g. for `ushort, ushort` where both fields can fit "inside" 4 bytes) and sometimes being no fields at all (`ushort, uint`). (Actually, this doesn't explain why you get 1024 different hash codes in the `uint, uint` case instead of just 1000. I'm still unsure on that.) Ultimately, using a value type which doesn't override `GetHashCode` as a dictionary key seems like it's just a bad idea, unless you've tested to ensure that it's suitable for your specific requirements. There's just too much which is black magic to be confident about it, IMO.

new KeyValuePair<UInt32, UInt32>(i, j).GetHashCode(); High Rate of Duplicates

Solution

Problem

Related problems