logo标签列表

新的KeyValuePair<UInt32, UInt32>(i, j).GetHashCode(); 高重复率

.netdictionarygethashcode
15
在寻找一个快速的字典复合键时，我遇到了一个我无法理解或证明的异常情况。
在有限的测试中
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 的和或差匹配。但无法找到何时求和、何时相减的模式。这是一个糟糕的哈希，所以知道它是什么对于价值来说很小。

你尝试过逐行分析吗？进行性能分析了吗？ - Krzysztof Kozmic
@KrzysztofKoźmic 别跟随，请解释。 - paparazzo
@casperOne 好的，你说得有道理，我会进行更多的测试。但是与 UInt16 和 UInt32 相比，1,000 很小。 - paparazzo
@casperOne 我明白。但是顺序是一个GetHashCode应该处理的模式。Tuple UInt32 UInt32受相同顺序的影响，产生了33792个独特的GetHashCode（与KVP的1024个相比）。从UInt32到UInt16的KVP退化在统计学上是不合理的。 - paparazzo
其实并不存在适用于所有情况的完美哈希码。鉴于您项目的限制，您最好自己实现。我发现这个页面有一些有用的指导方针；虽然是针对Java的，但同样的原则也适用。http://www.javamex.com/tutorials/collections/hash_function_guidelines.shtml - Katie Kilian
显示剩余5条评论
4个回答
8
首先，我们可以摒弃时间方面的考虑——对我来说，这似乎真的只是关于哈希碰撞的问题，因为很明显这会影响性能。
那么，问题实际上是为什么在KeyValuePair中有更多的哈希碰撞，而KeyValuePair中则没有。为了更好地了解这个问题，我编写了以下简短的程序：
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）。（实际上，这并不能解释为什么在uint，uint的情况下会得到1024个不同的哈希码而不仅仅是1000个。我仍然对此不确定。）总的来说，除非测试以确保其适用于特定要求，否则使用不覆盖GetHashCode的值类型作为字典键似乎只是一个坏主意。在我的看法中，有太多黑科技，难以保证其可靠性。
如果在1024 X 1024的UInt32上进行循环，会得到1024个独特的数字，每个数字都恰好重复1024次。 - paparazzo
1
@Blam：是的，这是有道理的-但当你只循环1000x1000次时，我预期只会有1000个键... - Jon Skeet
Hans已删除了他的答案，但我认为他有这个答案。 0,0 - 0,999会产生唯一的GetHashCode。8,992 - 8,999也会产生唯一的编号。而16,992 - 16,999和24,992 - 24,999也会产生唯一的编号。 - paparazzo
作为测试，我取i=0和j=0-1024来查看是否与新的i>0 j=0-1000匹配，答案是否定的。哈希UInt32 2281371105 = 哈希KVP 8,992。2281371104 = 8,993，2281371107 = 8,994。 - paparazzo
8
由于 GetHashCode 返回一个 Int32，每对 Int16（或 UInt16）都可以轻松返回一个唯一的值。对于一对 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() 合并结果值并为每个值对产生唯一的哈希，因为这是可能且直观的。
我给你点赞是因为你所写的是正确的。我怀疑那个踩你的人这么做是因为你没有直接回答问题。 - Enigmativity
+1 对问题的直接回答实际上比对问题的直接回答更有价值。 - paparazzo
1
正如其他回答者所提到的，KeyValuePair 没有重写 GetHashCode，并且对于结构体默认实现的 GetHashCode 不是最好的。您可以改用两个元素的元组来代替，例如：
var dict = new Dictionary<Tuple<uint, uint>, string>();
dict.Add(Tuple.Create(1u, 2u),"xxx"); // Tuples override GetHashCode

请注意，这将为额外的Tuple堆分配增加额外的开销。（不过这部分可以弥补，因为当你在一个不覆盖它的结构体上调用GetHashCode时，你会隐式地将其装箱）
正如我在问题中所述，元组也会生成很多重复项。你测试过吗？ - paparazzo
现在甚至有一个关于改进默认哈希码和相等性的 GitHub 问题，但我现在找不到它了。 - usr
0

底线是，如果您想将自己的大量内容放入类似于字典的结构中，则始终覆盖 GetHashCode。您可以使用此扩展程序查看字典填充情况。它将报告空槽，重复键等。即将在SourceForge上发布，但这里是;

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;

// This unit is Freeware. It was developed by Jerremy Koot & Ivo Tops. July 2011
//
// Version  By    Changes
// =======  ===== ==============================================================
// v1.02    Ivo   Removed not-working Hashtable support and simplified code
// v1.01    Ivo   Lowered memory usage
// v1.00    I&J   First Version

namespace FastLibrary
{
/// <summary>
/// Static Extension Methods for Dictionary, ConcurrentDictionary and HashSet
/// </summary>
public static class ExtHashContainers
{
    /// <summary>
    /// Checks a dictionary for performance statistics
    /// </summary>
    public static string Statistics<TKey, TValue>(this Dictionary<TKey, TValue> source)
    {
        return ExamineData(source.Keys, source);
    }

    /// <summary>
    /// Checks a concurrent dictionary for performance statistics
    /// </summary>
    public static string Statistics<TKey, TValue>(this ConcurrentDictionary<TKey, TValue> source)
    {
        return ExamineData(source.Keys, source);
    }

    /// <summary>
    /// Checks a HashSet for performance statistics
    /// </summary>
    public static string Statistics<TKey>(this HashSet<TKey> source)
    {
        return ExamineData(source, source);
    }

    private static string ExamineData<TKey>(ICollection<TKey> source, Object hashContainer)
    {
        if (!source.Any()) return "No Data found.";

        // Find Buckets
        var b = GetBuckets(hashContainer);
        if (b < 0) return ("Unable to get Buckets Field for HashContainer");

        // Create our counting temp dictionaries
        var d = new int[b];
        var h = new Dictionary<int, int>(source.Count);

        // Find Hash Collisions and Bucket Stats
        foreach (var k in source)
        {
            var hash = k.GetHashCode() & 0x7FFFFFFF; // Hashes are stripped of sign bit in HashContainers
            int bucket = hash%b; // .NET Hashers do not use negative hashes, and use % voor bucket selection
            // Bucket Stats
            d[bucket]++;

            // Hashing Stats
            int c;
            if (h.TryGetValue(hash, out c)) h.Remove(hash);
            else c = 0;
            c++;
            h.Add(hash, c);
        }

        // Do some math
        var maxInBucket = d.Max(q => q);
        var maxSameHash = h.Values.Max(q => q);
        var emptyBuckets = d.Count(q => q == 0);
        var emptyStr = b == 0 ? "0" : ((float) (emptyBuckets)/b*100).ToString("0.0");
        var worstHash = (from i in h where i.Value == maxSameHash select i.Key).FirstOrDefault();

        // Report our findings
        var r = Environment.NewLine + hashContainer.GetType().Name + " has " + b + " buckets with " + source.Count +
                " items. " +
                Environment.NewLine + "The Largest bucket contains " + maxInBucket + " items. " +
                Environment.NewLine + "It has " + (emptyBuckets) +
                " empty buckets (" + emptyStr + "%)" + Environment.NewLine + "Each non-empty bucket has on average " +
                ((source.Count/(float) (b - emptyBuckets))).ToString("0.0") + " items." + "The " + source.Count +
                " items share " + h.Count +
                " unique hashes. ";
        if (maxSameHash > 1)
            r += Environment.NewLine + "The largest collision has " + maxSameHash +
                 " items sharing the same hash, which == " + worstHash;
        return r;
    }

    private static Int32 GetBuckets(object dictionary)
    {
        var type = dictionary.GetType();
        while (type != null && !type.IsGenericType) type = type.BaseType;
        if (type == null) return -1;

        string field = null;
        if (type.GetGenericTypeDefinition() == typeof (Dictionary<,>)) field = "buckets";
        if (type.GetGenericTypeDefinition() == typeof (ConcurrentDictionary<,>)) field = "m_buckets";
        if (type.GetGenericTypeDefinition() == typeof (HashSet<>)) field = "m_buckets";
        if (field == null) return -1;

        var bucketsField = type.GetField(field, BindingFlags.NonPublic | BindingFlags.Instance);
        if (bucketsField == null) return -1;

        var buckets = bucketsField.GetValue(dictionary);
        if (buckets == null) return -1;

        var length = buckets.GetType().GetProperty("Length");
        return (int) length.GetGetMethod().Invoke(buckets, null);
    }
}
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接