在有限的测试中
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 X 1024个独一无二的哈希码(完美)。
Int32存在同样的问题。
这些重复的哈希值会导致问题。
Dictionary<KeyValuePair<UInt32, UInt32>, string>
元组还会生成很多重复项,但与Int16相比,它不会降级到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());
// 431
提示:最快的方法是打包 .E.G. ((UInt32)int1 << 16) | int2;
第一个 UInt32 列的哈希值等于下一个两个键值对的哈希值。
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 的和或差匹配。但无法找到何时求和、何时相减的模式。这是一个糟糕的哈希,所以知道它是什么对于价值来说很小。