复合键字典

Question

我在List中有一些对象,比方说List<MyClass>,MyClass有几个属性.我想基于MyClass的3个属性创建列表的索引.在这种情况下,2个属性是int,而一个属性是datetime.

基本上我希望能够做到这样的事情:

Dictionary< CompositeKey , MyClass > MyClassListIndex = Dictionary< CompositeKey , MyClass >();
//Populate dictionary with items from the List<MyClass> MyClassList
MyClass aMyClass = Dicitonary[(keyTripletHere)];

我有时会在列表上创建多个字典来索引它所拥有的类的不同属性.我不知道如何最好地处理复合键.我考虑过对三个值进行校验和,但这会产生碰撞的风险.

Answer 1

你应该使用元组.它们等同于CompositeKey类,但已经为您实现了Equals()和GetHashCode().

var myClassIndex = new Dictionary<Tuple<int, bool, string>, MyClass>();
//Populate dictionary with items from the List<MyClass> MyClassList
foreach (var myObj in myClassList)
    myClassIndex.Add(Tuple.Create(myObj.MyInt, myObj.MyBool, myObj.MyString), myObj);
MyClass myObj = myClassIndex[Tuple.Create(4, true, "t")];

或者使用System.Linq

var myClassIndex = myClassList.ToDictionary(myObj => Tuple.Create(myObj.MyInt, myObj.MyBool, myObj.MyString));
MyClass myObj = myClassIndex[Tuple.Create(4, true, "t")];

除非您需要自定义散列的计算,否则使用元组会更简单.

如果要在复合键中包含许多属性,则元组类型名称可能会变得很长,但您可以通过创建从Tuple <...>派生的自己的类来缩短名称.

**2017年编辑**

从C#7开始有一个新选项:值元组.这个想法是一样的,但语法不同,更轻:

类型Tuple<int, bool, string>变为(int, bool, string),值Tuple.Create(4, true, "t")变为(4, true, "t").

使用值元组,也可以命名元素.请注意,性能略有不同,因此如果它们对您很重要,您可能需要进行一些基准测试.

Answer 2

我能想到的最好的方法是创建一个CompositeKey结构并确保覆盖GetHashCode()和Equals()方法,以确保在处理集合时的速度和准确性:

class Program
{
    static void Main(string[] args)
    {
        DateTime firstTimestamp = DateTime.Now;
        DateTime secondTimestamp = firstTimestamp.AddDays(1);

        /* begin composite key dictionary populate */
        Dictionary<CompositeKey, string> compositeKeyDictionary = new Dictionary<CompositeKey, string>();

        CompositeKey compositeKey1 = new CompositeKey();
        compositeKey1.Int1 = 11;
        compositeKey1.Int2 = 304;
        compositeKey1.DateTime = firstTimestamp;

        compositeKeyDictionary[compositeKey1] = "FirstObject";

        CompositeKey compositeKey2 = new CompositeKey();
        compositeKey2.Int1 = 12;
        compositeKey2.Int2 = 9852;
        compositeKey2.DateTime = secondTimestamp;

        compositeKeyDictionary[compositeKey2] = "SecondObject";
        /* end composite key dictionary populate */

        /* begin composite key dictionary lookup */
        CompositeKey compositeKeyLookup1 = new CompositeKey();
        compositeKeyLookup1.Int1 = 11;
        compositeKeyLookup1.Int2 = 304;
        compositeKeyLookup1.DateTime = firstTimestamp;

        Console.Out.WriteLine(compositeKeyDictionary[compositeKeyLookup1]);

        CompositeKey compositeKeyLookup2 = new CompositeKey();
        compositeKeyLookup2.Int1 = 12;
        compositeKeyLookup2.Int2 = 9852;
        compositeKeyLookup2.DateTime = secondTimestamp;

        Console.Out.WriteLine(compositeKeyDictionary[compositeKeyLookup2]);
        /* end composite key dictionary lookup */
    }

    struct CompositeKey
    {
        public int Int1 { get; set; }
        public int Int2 { get; set; }
        public DateTime DateTime { get; set; }

        public override int GetHashCode()
        {
            return Int1.GetHashCode() ^ Int2.GetHashCode() ^ DateTime.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            if (obj is CompositeKey)
            {
                CompositeKey compositeKey = (CompositeKey)obj;

                return ((this.Int1 == compositeKey.Int1) &&
                        (this.Int2 == compositeKey.Int2) &&
                        (this.DateTime == compositeKey.DateTime));
            }

            return false;
        }
    }
}

关于GetHashCode()的MSDN文章:

http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx

Answer 3

怎么样Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>>？

这将允许您:

MyClass item = MyData[8][23923][date];

Answer 4

您可以将它们存储在结构中并将其用作键:

struct CompositeKey
{
  public int value1;
  public int value2;
  public DateTime value3;
}

获取哈希码的链接:http: //msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

Answer 5

现在VS2017/C#7已经问世,最好的答案是使用ValueTuple:

// declare:
Dictionary<(string, string, int), MyClass) index;

// populate:
foreach (var m in myClassList) {
  index[(m.Name, m.Path, m.JobId)] = m;
}

// retrieve:
var aMyClass = index[("foo", "bar", 15)];

我选择使用匿名ValueTuple声明字典(string, string, int).但我可以给他们起名字(string name, string path, int id).

Perfwise,新的ValueTuple比Tuple快,GetHashCode但速度慢Equals.我认为您需要进行完整的端到端实验,以确定哪种方法最适合您的方案.但ValueTuple的端到端的优秀和语言语法使它赢得了胜利.

// Perf from https://gist.github.com/ljw1004/61bc96700d0b03c17cf83dbb51437a69
//
//              Tuple ValueTuple KeyValuePair
//  Allocation:  160   100        110
//    Argument:   75    80         80    
//      Return:   75   210        210
//        Load:  160   170        320
// GetHashCode:  820   420       2700
//      Equals:  280   470       6800

Answer 6

立即想到两种方法：

1. 按照凯文的建议做，写一个结构体作为你的钥匙。确保实现此结构IEquatable<TKey>并覆盖其Equals和GetHashCode方法*。

2. 编写一个在内部使用嵌套字典的类。喜欢的东西：TripleKeyDictionary<TKey1, TKey2, TKey3, TValue>......这个类内部有类型的成员Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>>，并且会暴露的方法，如this[TKey1 k1, TKey2 k2, TKey3 k3]，ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3)等

*关于是否需要覆盖该Equals方法的一句话：虽然Equals结构的方法默认比较每个成员的值，但它是通过使用反射来实现的——这固有地需要性能成本——因此不是一个非常适合用作字典中键的东西的适当实现（在我看来，无论如何）。根据 MSDN 文档ValueType.Equals：

Equals 方法的默认实现使用反射来比较 obj 和此实例的对应字段。重写特定类型的 Equals 方法以提高该方法的性能并更接近地表示该类型的相等概念。