新KeyValuePair<UInt32，UInt32>(i，j).GetHashCode()；高重复率

Question

为了寻找字典的快速合成键，我偶然发现了异常，我无法理解，也无法证明。

在有限测试中

Dictionary<KeyValuePair<UInt32, UInt32>, string>

比(200:1)慢得多

Dictionary<KeyValuePair<UInt16, UInt16>, string>

测试从0到1000之间的两个循环，然后进行ContainsKey

         Poplulate     ContainsKey  
UInt32    92085         86578  
UInt16     2201           431

问题是

new KeyValuePair<UInt32, UInt32>(i, j).GetHashCode();

产生了许多重复。

在循环i和j 1024中，只创建了1024唯一的散列值。

根据CasperOne的雪崩注释，我尝试了i*31和j*97 (两个素数)，这导致了在1024X1024上唯一的105280。还是有很多重复的。CasperOne，我知道这和随机不一样。但随机输入不是我的工作。GetHashCode()应该将输出随机化。

为什么有大量的重复？

相同回路

new KeyValuePair<UInt16, UInt16>(i, j).GetHashCode();

产生1024×1024唯一的散列码(完美)。

Int32也有同样的问题。

这些重复的哈希值将杀死

Dictionary<KeyValuePair<UInt32, UInt32>, string> 

元组还会生成许多复制，与Int32相比，与Int16相比，它不会在Int16中退化。

生成原始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());
//  431

最快的是包装.E.G. (UInt32)int1 << 16) + int2；

第一个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匹配。

但是找不到什么时候该和什么时候减去的模式。

这是一个糟糕的杂凑，所以知道它是什么没有什么价值。

Answer 1

首先，我们可以省去这方面的时间问题--我觉得这真的是关于散列碰撞的，因为很明显，这些都会扼杀性能。

因此，问题是为什么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>的结果令人吃惊地好。

事实上，在运行64位CLR时，KeyValuePair<ushort, uint>并不仅仅是坏的--就我所能看到的是可笑的糟糕--我没有找到任何不具有-1913331935的哈希代码的值。运行32位CLR，我会得到一个不同的哈希码，但是对于所有的值仍然是相同的哈希码。

在.NET 4.5中(这是我正在运行的)，GetHashCode的默认实现似乎不只是像前面所描述的那样，只接受结构的第一个实例字段。我怀疑，至少在某些类型中，它只使用装箱值中的头以外的前4个字节的内存(这里的每个调用都会有装箱)，有时它只是第一个字段(如果该字段是uint)，有时是多个字段(例如，对于ushort, ushort，其中两个字段都可以容纳在“4字节”内)，有时根本不是字段(ushort, uint)。

(实际上，这并不能解释为什么在uint, uint情况下得到1024个不同的哈希码，而不是仅仅1000个。我对此仍不确定。)

最终，使用不覆盖GetHashCode作为字典键的值类型似乎是个坏主意，除非您已经测试过，以确保它适合您的特定需求。有太多的黑魔法对它充满信心，海事组织。

Answer 2

因为GetHashCode返回一个Int32，所以每对Int16s (或UInt16s)都可以很容易地返回一个唯一的值。有了一对Int32，您需要以某种方式组合这些值，以便与您的设计兼容。

KeyValuePair不覆盖GetHashCode()，因此您只是使用ValueType.GetHashCode()的默认实现，其文档如下所示：

(出发地：http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx) 如果调用派生类型的GetHashCode方法，则返回值可能不适合用作哈希表中的键。此外，如果其中一个或多个字段的值发生变化，则返回值可能不适合用作哈希表中的键。在这两种情况下，考虑编写您自己的GetHashCode方法的实现，该方法更紧密地表示类型的哈希代码的概念。

由于KeyValuePair不覆盖GetHashCode()，所以我认为它不打算用作Dictionary密钥。

此外，根据这个问题和这个C#代码，ValueType.GetHashCode()的默认实现只是选择第一个非静态字段，并返回其GetHashCode()方法的结果。这就解释了为什么KeyValuePair<UInt32, UInt32>的重复数很高，尽管这并不能解释为什么KeyValuePair<UInt16, UInt16>缺少重复。

我的猜测是，对于KeyValuePair<UInt32, UInt32>，GetHashCode()只返回第一个值的GetHashCode()，而对于KeyValuePair<UInt16, UInt16>，GetHashCode()是将导致对每个值的唯一散列的值组合在一起，因为这样做是可能的，而且是直接的。

Answer 3

正如其他回答者所提到的，KeyValuePair不覆盖GetHashCode，并且GetHashCode的默认实现用于structs 不是最好的。您可以使用双元素元组来实现这一点。

var dict = new Dictionary<Tuple<uint, uint>, string>();
dict.Add(Tuple.Create(1u, 2u),"xxx"); // Tuples override GetHashCode

注意，这将为额外的元组堆分配增加额外的开销。(不过，它是部分弥补的，因为当您在不覆盖结构的结构上调用GetHashCode时，就会隐式地将其装箱)