15

Dictionary の高速な複合キーを探していると、理解も正当化もできない異常に遭遇しました。

限定テストで 

Dictionary<KeyValuePair<UInt32, UInt32>, string>

よりも大幅に遅い (200:1)

Dictionary<KeyValuePair<UInt16, UInt16>, string>

0 から 1000 までの 2 つのループでテストします。

         Poplulate     ContainsKey  
UInt32    92085         86578  
UInt16     2201           431

問題はそれです 

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

多くの複製が得られます。
i と j 1024 のループでは、1024 個の一意のハッシュ値のみが作成されます。

CasperOne からの雪崩のコメントに基づいて、i*31 と j*97 (2 つの素数) を試したところ、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

PS 最速は .EG ((UInt32)int1 << 16) | をパックすることです。int2;

最初の UInt32 列のハッシュは、次の 2 つの 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
22813711510 1 6
2281371151 1 7
2281371136 8
2281371137 1 9 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 が一致することです。
しかし、いつ加算し、いつ減算するかのパターンを見つけることができませんでした。
これは悪いハッシュであるため、それが何であるかを知ることはほとんど価値がありません。

4

4 に答える 4

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。

uint, uint(実際には、このケースで 1000 ではなく1024 の異なるハッシュ コードを取得する理由が説明されていません。それについてはまだわかりません。)

最終的に、辞書キーとしてオーバーライドしない値型を使用することGetHashCodeは、特定の要件に適していることを確認するためにテストしない限り、悪い考えのように思えます。それについて確信するには、黒魔術が多すぎます.IMO.

于 2012-09-30T07:23:48.383 に答える
8

GetHashCodeは を返すため、Int32のすべてのペアInt16(またはUInt16) は簡単に一意の値を返すことができます。のペアではInt32、設計との互換性を保つために何らかの方法で値を組み合わせる必要があります。

KeyValuePairをオーバーライドしないGetHashCode()ため、 のデフォルトの実装を使用しているだけValueType.GetHashCode()であり、そのドキュメントには次のように記載されています。

(から: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx )

派生型の GetHashCode メソッドを呼び出す場合、戻り値はハッシュ テーブルのキーとして使用するのに適していない可能性があります。さらに、これらのフィールドの 1 つ以上の値が変更されると、戻り値がハッシュ テーブルのキーとして使用できなくなる可能性があります。いずれの場合も、型のハッシュ コードの概念をより厳密に表す GetHashCode メソッドの独自の実装を作成することを検討してください。

KeyValuePairをオーバーライドしないためGetHashCode()、キーとして使用することを意図していないと思いDictionaryます。

さらに、この質問とこの C# コードによると、のデフォルトの実装はValueType.GetHashCode()、最初の非静的フィールドを単に選択し、そのGetHashCode()メソッドの結果を返します。これは の重複数が多いことをKeyValuePair<UInt32, UInt32>説明していますが、 の重複がないことは説明していませんKeyValuePair<UInt16, UInt16>。

私の推測では、 forKeyValuePair<UInt32, UInt32>は単純に最初の値をGetHashCode()返し、 forは値を組み合わせて、値のペアごとに一意のハッシュを生成します。GetHashCode()KeyValuePair<UInt16, UInt16>GetHashCode()

于 2012-09-30T03:12:44.147 に答える
1

他の回答者が述べたように、KeyValuePairオーバーライドしません。また、 for structsGetHashCodeのデフォルトの実装は最適ではありません。代わりに、これには 2 要素のタプルを使用できます。GetHashCode

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

ただし、これにより、余分な Tuple ヒープ割り当てのオーバーヘッドが追加されることに注意してください。GetHashCode（ただし、それをオーバーライドしない構造体を呼び出すと、暗黙的にボックス化されるため、部分的に補われています）

于 2016-08-11T03:00:58.373 に答える
0

一番下のルールは、辞書のような has using 構造に多くの独自のものを入れたい場合は、常に 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 に答える