15

在寻找 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 的雪崩评论，尝试了 i*31 和 j*97（两个素数），这导致 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());
//  431

PS 最快的是打包.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


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 匹配。
但是找不到何时求和何时减去的模式。
这是一个糟糕的哈希，所以知道它是什么没有什么价值。

4

4 回答 4

8

由于GetHashCode返回 a Int32，因此每对Int16s（或UInt16s）都可以轻松返回唯一值。使用一对Int32s，您需要以某种方式组合这些值以与您的设计兼容。

KeyValuePair不会覆盖GetHashCode()，因此您只是使用 的默认实现ValueType.GetHashCode()，并且它的文档说明如下：

（来自：http: //msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx）

如果调用派生类型的 GetHashCode 方法，则返回值不太可能适合用作哈希表中的键。此外，如果其中一个或多个字段的值发生变化，则返回值可能不适合用作哈希表中的键。无论哪种情况，请考虑编写您自己的 GetHashCode 方法实现，以更接近地表示该类型的哈希码的概念。

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

此外，根据this question和this C# code，默认实现ValueType.GetHashCode()只是选择第一个非静态字段，并返回其GetHashCode()方法的结果。这解释了 的大量重复KeyValuePair<UInt32, UInt32>，尽管它不能解释KeyValuePair<UInt16, UInt16>.

我的猜测是 for KeyValuePair<UInt32, UInt32>,GetHashCode()确实只是返回GetHashCode()第一个值，而 for KeyValuePair<UInt16, UInt16>,GetHashCode()将这些值组合在一起，为每对值产生一个唯一的哈希值，因为这样做是可能且直接的。

于 2012-09-30T03:12:44.147 回答
8

首先，我们可以省去这个时间方面的问题——在我看来，这实际上只是关于哈希冲突，因为显然这些会影响性能。

所以，问题真的是为什么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，有太多的黑魔法让我们对此充满信心。

于 2012-09-30T07:23:48.383 回答
1

正如其他回答者提到的那样，KeyValuePair不会覆盖，并且for structsGetHashCode的默认实现不是最好的。您可以为此使用二元素元组，例如GetHashCode

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

但是请注意，这将为额外的元组堆分配增加额外的开销。（虽然它部分弥补了，因为当你调用GetHashCode一个不覆盖它的结构时，你会隐式地将它装箱）

于 2016-08-11T03:00:58.373 回答
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);
    }
}
}
于 2012-09-30T10:17:34.110 回答