字典,其中键是一对整数

Question

我需要使用一个Dictionary,其中TKey是一对int.

我想使用KeyValuePair作为我的键的类型,我想知道这是否是最好的方法.

我也很想知道Dictionary是否会为具有相同整数和原因的两个不同KeyValuePair对象创建单独的条目.

例如:

var myDictionary = new Dictionary<KeyValuePair<int,int>, string>();
myDictionary.Add(new KeyValuePair<int,int>(3, 3), "FirstItem");
myDictionary.Add(new KeyValuePair<int,int>(3, 3), "SecondItem");
// does the dictionary allow this?

Answer 1

也许你应该考虑使用 Tuple

var myDictionary = new Dictionary<Tuple<int,int>, List<string>>(); 
myDictionary.Add(new Tuple<int,int>(3, 3), "FirstItem"); 
myDictionary.Add(new Tuple<int,int>(5, 5), "SecondItem"); 

根据MSDN文档,一个Tupleobjects Equals方法将使用两个Tuple对象的值.这将导致Tuple外部字典中每个条目一个条目,并允许您存储每个键的值列表.

Answer 2

只需使用 along作为键并组合两个int键

public class IntIntDict<T> : Dictionary<long, T>
{
    public void Add(int key1, int key2, T value)
    {
        Add((((long)key1) << 32) + key2, value);
    }

    //TODO: Overload other methods
}

更新

C# 7 引入了新的ValueTuple Struct以及简化的元组语法。这些元组对于复合键非常有用。您可以声明您的字典并添加如下条目：

var myDictionary = new Dictionary<(int, int), string>();
myDictionary.Add((3, 3), "FirstItem"); 
myDictionary.Add((5, 5), "SecondItem");

并查找这样的值

string result = myDictionary[(5, 5)];

或者

if (myDictionary.TryGetValue((5, 7), out string result)) {
    //TODO: use result
}

Answer 3

为了提高性能，Dictionary 需要一个生成唯一 GetHashValue 的键。

KeyValuePair 是一种值类型，不推荐用于键。

值类型.GetHashCode

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

Point 也是一种值值类型，也不推荐用于键。
Tuple 还会生成大量重复的 GetHashCode，并不是一个好的键。

最佳密钥是生成唯一密钥的密钥。

考虑 UInt16 i 和 UInt j 作为两个键。
它们如何组合并生成唯一的哈希？
轻松将它们组合成 UInt32。
UInt32 本机生成完美的散列。

将两个 UInt16 打包成 UInt32 的算法是

(i * (UInt16.MaxValue + 1)) + j;

但它甚至更快

(UInt32)i << 16 | j;


myDictionary = new Dictionary<UInt32, string>();

使用完美的哈希字典是 O(1)。
由于哈希不好，字典变为 O(n)。