11

我需要使用字典，其中 TKey 是一对整数。

我想使用 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?
4

6 回答 6

29

也许你应该考虑使用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 文档，Tuple对象Equals方法将使用两个Tuple对象的值。这将在Tuple外部字典中产生一个条目，并允许您存储每个键的值列表。

于 2012-09-24T18:09:21.217 回答
10

只需使用 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
}
于 2012-10-01T13:58:23.973 回答
6

为了性能，字典需要一个生成唯一 GetHashValue 的键。

KeyValuePair 是一种值类型，不建议用于键。

ValueType.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)。

于 2012-09-24T18:17:03.197 回答
0

更新：根据您对其他响应者的评论，下面的代码回答了您的问题。是的，重复会产生异常 System.ArgumentException

您列出的代码可以使用，但不会接受重复的 KeyValuePairs。如果您添加字典中已存在的 KeyValuePair，则会引发 System.ArgumentException 或类似情况。

例如，这段代码

using System;
using System.Collections;
using System.Collections.Generic;

namespace test{

    public class App {

        public static void Main(string[] args) {
            var myDictionary = new Dictionary<KeyValuePair<int,int>, string>(); 

            Console.WriteLine("Adding 2 items...");
            myDictionary.Add(new KeyValuePair<int,int>(3, 3), "FirstItem"); 
            myDictionary.Add(new KeyValuePair<int,int>(5, 5), "SecondItem"); 
            Console.WriteLine("Dictionary items: {0}", myDictionary.Count);

            Console.WriteLine("Adding 2 duplicate items...");
            myDictionary.Add(new KeyValuePair<int,int>(3, 3), "FirstItem"); 
            myDictionary.Add(new KeyValuePair<int,int>(5, 5), "SecondItem"); 
            Console.WriteLine("Dictionary items: {0}", myDictionary.Count);
        }
    }
}

给出以下

适用于 Microsoft (R) .NET Framework 4.5 的 Microsoft (R) Visual C# 编译器版本 4.0.30319.17626 版权所有 (C) Microsoft Corporation。版权所有。

添加 2 项... 字典项：2 添加 2 个重复项...

未处理的异常：System.ArgumentException：已添加具有相同键的项目。在 System.Collections.Generic.Dictionary`2.Insert(TKey key, TValue value, Boolean add) at test.App.Main(String[] args)

于 2012-09-24T18:18:08.390 回答
0

字典需要一个相等的实现来确定键是否相等。您可以IEqualityComparer<T>使用接受比较器参数的构造函数来指定通用接口的实现；如果您不指定实现，则使用默认的泛型相等比较器EqualityComparer<T>.Default。

所以，在你的情况下，因为你没有指定IEqualityComparer<T>，默认将被使用。

EqualityComparer<T>.Default检查类型 T 是否实现了System.IEquatable<T>接口，如果是，则返回使用该实现的 EqualityComparer 。否则，它返回一个EqualityComparer<T>使用 T 的覆盖Object.Equals和Object.GetHashCode由 T 提供的覆盖。

T is structKeyValuePair没有实现System.IEquatable<T>，所以它使用struct 的EqualandGetHashCode方法KeyValuePair。这两种方法都使用KeyandValue来检查相等并生成哈希码：

public override int GetHashCode()
{
    return Key.GetHashCode() ^ Value.GetHashCode();
}

因此，总而言之，在您的示例字典中不允许。

于 2012-09-24T18:46:13.473 回答
-1

使用 KeyValuePair 作为字典的键：

它在功能上可以使用 KeyValuePair 作为字典中的键；但是，从概念上讲，这可能不是您的应用程序的最佳选择，因为它暗示了两个整数之间的键值关系。

相反，正如 Mike 建议的那样，您应该使用 Tuple 作为您的密钥。

对于第二个问题：

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?

字典不允许这样做，字典本身是一组键值对，其中键必须是唯一的。如果您希望能够将多个值映射到同一个键，一种选择是将值设置为另一个集合：

var myDictionary = new Dictionary<KeyValuePair<int,int>, List<string>>();

但是您仍然无法像示例中那样使用 myDictionary.Add 。相反，您必须提供额外的功能来确定它们的键是否是字典的一部分并采取相应的行动：

public static class DictionaryHelper
{

    public static void Add(this Dictionary<Tuple<int,int>, List<string>> dict,Tuple<int,int> key, string value)
    {
        if(dict.ContainsKey(key))
        {
            dict[key].Add(value);
        }
        else
        {
            dict.Add(key, new List<string>{value});
        }
    } 
}
于 2012-09-24T18:31:09.460 回答