新的 KeyValuePair<UInt32, UInt32>(i, j).GetHashCode();重複率高
在尋找 Dictionary 的快速復合鍵時，我遇到了我無法理解也無法證明的異常情況。
在有限的測試中
Dictionary<KeyValuePair<UInt32, UInt32>, string>明顯慢於 (200:1)
Dictionary<KeyValuePair<UInt16, UInt16>, string>測試從 0 到 1000 Populate 和 ContainsKey 的兩個循環
Poplulate ContainsKey UInt32 92085 86578 UInt16 2201 431問題是
new KeyValuePair<UInt32, UInt32>(i, j).GetHashCode();產生許多重複。
在循環 i 和 j 1024 中，僅創建了 1024 個唯一雜湊值。
根據 CasperOne 的雪崩評論，嘗試了 i31 和 j97（兩個素數），這導致 105280 在 1024X1024 上是唯一的。還是有很多重複的。CasperOne 我知道這和隨機的不一樣。但隨機化輸入不是我的工作。GetHashCode() 應該隨機化輸出。
為什麼重複次數多？
相同的循環
new KeyValuePair<UInt16, UInt16>(i, j).GetHashCode();產生 1024 X 1024 唯一雜湊碼（完美）。
Int32 也有同樣的問題。
這些重複的雜湊值殺死
Dictionary<KeyValuePair<UInt32, UInt32>, string>與 Int16 相比，Tuple 還會生成許多在 Int32 上不會降級的重複項。
生成原始 KVP 和原始 KPV.GetHashCode 的時間類似。
與 HashSet 相同的異常。
Dictionary<KeyValuePair<UInt32, UInt32>, string> dKVPu32 = new Dictionary<KeyValuePair<UInt32, UInt32>, string>(); Dictionary<KeyValuePair<UInt16, UInt16>, string> dKVPu16 = new Dictionary<KeyValuePair<UInt16, UInt16>, string>(); KeyValuePair<UInt32, UInt32> kvpUint32; KeyValuePair<UInt16, UInt16> kvpUint16; int range = 1000; Int32 hashCode; HashSet<Int32> kvpUint32Hash = new HashSet<Int32>(); HashSet<Int32> kvpUint16Hash = new HashSet<Int32>(); Stopwatch sw = new Stopwatch(); sw.Start(); for (UInt32 i = 0; i < range; i++) { for (UInt32 j = 0; j < range; j++) { kvpUint32 = new KeyValuePair<UInt32, UInt32>(i, j); } } Console.WriteLine("UInt32 raw " + sw.ElapsedMilliseconds.ToString()); // 7 sw.Restart(); for (UInt16 i = 0; i < range; i++) { for (UInt16 j = 0; j < range; j++) { kvpUint16 = new KeyValuePair<UInt16, UInt16>(i, j); } } Console.WriteLine("UInt16 raw " + sw.ElapsedMilliseconds.ToString()); // 6 sw.Restart(); for (UInt32 i = 0; i < range; i++) { for (UInt32 j = 0; j < range; j++) { hashCode = new KeyValuePair<UInt32, UInt32>(i, j).GetHashCode(); kvpUint32Hash.Add(hashCode); } } Console.WriteLine("UInt32 GetHashCode " + sw.ElapsedMilliseconds.ToString() + " unique count " + kvpUint32Hash.Count.ToString()); // 285 1024 sw.Restart(); for (UInt16 i = 0; i < range; i++) { for (UInt16 j = 0; j < range; j++) { hashCode = new KeyValuePair<UInt16, UInt16>(i, j).GetHashCode(); kvpUint16Hash.Add(hashCode); } } Console.WriteLine("UInt16 GetHashCode " + sw.ElapsedMilliseconds.ToString() + " unique count " + kvpUint16Hash.Count.ToString()); // 398 1000000 sw.Restart(); Console.ReadLine(); for (UInt32 i = 0; i < range; i++) { for (UInt32 j = 0; j < range; j++) { dKVPu32.Add(new KeyValuePair<UInt32, UInt32>(i, j), String.Format("{0} {1}", i.ToString(), j.ToString())); } } Console.WriteLine("hsKVPu32 pop " + sw.ElapsedMilliseconds.ToString()); // 92085 sw.Restart(); for (UInt32 i = 0; i < range; i++) { for (UInt32 j = 0; j < range; j++) { if (!dKVPu32.ContainsKey(new KeyValuePair<UInt32, UInt32>(i, j))) Debug.WriteLine("Opps"); ; } } Console.WriteLine("hsKVPu32 find " + sw.ElapsedMilliseconds.ToString()); // 86578 dKVPu32.Clear(); dKVPu32 = null; GC.Collect(); sw.Restart(); for (UInt16 i = 0; i < range; i++) { for (UInt16 j = 0; j < range; j++) { dKVPu16.Add(new KeyValuePair<UInt16, UInt16>(i, j), String.Format("{0} {1}", i.ToString(), j.ToString())); } } Console.WriteLine("hsKVPu16 pop " + sw.ElapsedMilliseconds.ToString()); // 2201 sw.Restart(); for (UInt16 i = 0; i < range; i++) { for (UInt16 j = 0; j < range; j++) { if (!dKVPu16.ContainsKey(new KeyValuePair<UInt16, UInt16>(i, j))) Debug.WriteLine("Opps"); ; } } sw.Stop(); Console.WriteLine("hsKVPu16 find " + sw.ElapsedMilliseconds.ToString()); // 431PS 最快的是打包.EG ((UInt32)int1 << 16) | 整數2；
第一個 UInt32 列的雜湊等於接下來兩個 KVP 的雜湊。
2281371105 8 992
2281371104 8 993
2281371107 8 994
2281371145 0 0
2281371147 0 2
2281371149 0 4
2281371151 0 6
2281371137 0 8
2281371144 0 1
2281371146 0 3
2281371148 0 5
2281371150 0 7
2281371136 0 9
2281371144 1 0
2281371145 1 1
2281371146 1 2
2281371147 1 3
2281371148 1 4
2281371149 1 5
2281371150 1 6
2281371151 1 7
2281371136 1 8
2281371137 1 9
2281371147 2 0
2281371146 2 1
2281371144 2 3
2281371151 2 4
2281371150 2 5
2281371149 2 6
2281371148 2 7
2281371139 2 8
我發現的唯一模式是和或差或 KVP 匹配。
但是找不到何時求和何時減去的模式。
這是一個糟糕的雜湊，所以知道它是什麼沒有什麼價值。
首先，我們可以省去這個時間方面的問題——在我看來，這實際上只是關於雜湊衝突，因為顯然這些會影響性能。
所以，問題真的是為什麼
KeyValuePair<uint, uint>比KeyValuePair<ushort, ushort>. 為了幫助了解更多相關資訊，我編寫了以下簡短程序：using System; using System.Collections.Generic; class Program { const int Sample1 = 100; const int Sample2 = 213; public static void Main() { Display<uint, ushort>(); Display<ushort, ushort>(); Display<uint, uint>(); Display<ushort, uint>(); } static void Display<TKey, TValue>() { 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<TKey, TValue>(key1, value1).GetHashCode()); Console.WriteLine(new KeyValuePair<TKey, TValue>(key1, value2).GetHashCode()); Console.WriteLine(new KeyValuePair<TKey, TValue>(key2, value1).GetHashCode()); Console.WriteLine(new KeyValuePair<TKey, TValue>(key2, value2).GetHashCode()); Console.WriteLine(); } }我機器上的輸出是：
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您顯然可以嘗試改變樣本值以查看發生衝突的位置。
結果
KeyValuePair<ushort, uint>特別令人擔憂，結果KeyValuePair<ushort, ushort>出奇的好。事實上，
KeyValuePair<ushort, uint>這不僅是糟糕的——據我所見，它非常糟糕——在執行 64 位 CLR 時，我沒有找到任何不具有相同雜湊碼 -1913331935 的值*。*執行 32 位 CLR 我得到不同的雜湊碼，但所有值的雜湊碼仍然相同。看來，在 .NET 4.5（這是我正在執行的）中，預設實現
GetHashCode不只是採用結構的第一個實例欄位，如前所述。我懷疑至少對於某些類型，它只使用裝箱值中標頭之外的前 4 個字節的記憶體（並且這裡的每個呼叫都會裝箱），最終有時只是第一個欄位（如果欄位是一個uint），有時是多個欄位（例如ushort, ushort，兩個欄位都可以容納“內部” 4 個字節），有時根本沒有欄位（ushort, uint）。（實際上，這並不能解釋為什麼你會得到 1024 個不同的雜湊碼，
uint, uint而不是只有 1000 個。我仍然不確定。）最終，使用不會覆蓋的值類型
GetHashCode作為字典鍵似乎只是一個壞主意，除非您已經測試以確保它適合您的特定要求。IMO，有太多的黑魔法讓我們對此充滿信心。