W poszukiwaniu szybkiego klucza złożonego dla Słownika natknąłem się na anomalię, której nie mogę zrozumieć ani usprawiedliwić.

W ograniczonych testach

Dictionary<KeyValuePair<UInt32, UInt32>, string>

jest znacznie wolniejszy (200: 1) niż

Dictionary<KeyValuePair<UInt16, UInt16>, string>

Przetestuj na dwóch pętlach od 0 do 1000 Wypełnij, a następnie ContainsKey

         Poplulate     ContainsKey  
UInt32    92085         86578  
UInt16     2201           431

Problemem jest

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

daje WIELE duplikatów.
W pętli i i j 1024 tworzonych jest tylko 1024 unikalnych wartości skrótu.

Na podstawie komentarza lawinowego CasperOne próbowano i * 31 i j * 97 (dwie liczby pierwsze), co spowodowało, że na 1024X1024 było 105280 unikalnych. Nadal wiele duplikatów. CasperOne Wiem, że to nie to samo, co losowe. Ale nie jest moim zadaniem losowanie danych wejściowych. GetHashCode () ma losować dane wyjściowe.

Dlaczego duża liczba duplikatów?

Ta sama pętla

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

daje 1024 X 1024 unikalnych kodów skrótu (idealne).

Int32 ma ten sam problem.

Te zduplikowane wartości skrótu zabijają

Dictionary<KeyValuePair<UInt32, UInt32>, string> 

Tuple generuje również wiele duplikatów, które nie ulegają degradacji w Int32 w porównaniu z Int16.

Czas generowania surowego KVP i surowego KPV.GetHashCode jest podobny.

Ta sama anomalia z 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

P.S. Najszybszy jest spakowanie .E.G. ((UInt32) int1 << 16) | int2;

Wartość mieszania pierwszej kolumny UInt32 równa się hashowi KVP z następnych dwóch.

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

Jedyny wzór, jaki znalazłem, to to, że albo suma, albo różnica, albo KVP pasują.
Ale nie mógł znaleźć wzoru, kiedy sumować i kiedy odejmować.
Jest to zły hash, więc wiedza o tym, co to jest, ma małą wartość.