复合键字典

List中有一些对象,比如List<MyClass>和MyClass有几个属性。 我想根据MyClass的3个属性创build列表的索引。 在这种情况下,2个属性是int的,一个属性是date时间。

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

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

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

你应该使用元组。 它们相当于一个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")]; 

除非你需要定制散列的计算,否则使用元组更简单。

如果要在组合键中包含很多属性,则元组types名称可能变得相当长,但可以通过创build自己的类派生自Tuple <…>来缩短名称的长度。


** 2017年编辑 **

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

typesTuple<int, bool, string>变为(int, bool, string) ,并且值Tuple.Create(4, true, "t")变成(4, true, "t")

使用值元组,也可以命名元素。 请注意,表演略有不同,所以你可能想要做一些基准,如果他们对你很重要。

我能想到的最好的方法是创build一个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

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

这可以让你做到:

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

您可以将它们存储在一个结构中,并将其用作关键字:

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

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

立即想到两种方法:

  1. 按照凯文的build议,写一个结构体作为你的钥匙。 一定要让这个结构实现IEquatable<TKey>并重写它的EqualsGetHashCode方法*。

  2. 编写一个在内部使用嵌套字典的类。 例如: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue> …这个类内部有一个Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>>types的成员,并且会暴露这样的方法this[TKey1 k1, TKey2 k2, TKey3 k3]ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3)

*关于是否需要重写Equals方法是有必要的:虽然结构的Equals方法默认情况下比较每个成员的值是真的,但是它通过使用reflection来实现 – 这本质上涉及性能成本 – 因此不是一个非常恰当的实现,是为了在字典中用作关键字(在我看来,无论如何)。 根据ValueType.Equals上的MSDN文档:

Equals方法的默认实现使用了reflection来比较obj和这个实例的相应字段。 覆盖特定types的Equals方法以提高方法的性能,并更密切地表示types相等的概念。

如果键是类的一部分,则使用KeyedCollection。
这是一个字典,其中的关键是从对象派生。
在封面下它是词典
不必重复键和值中的键。
为什么要把钥匙和价值钥匙不一样?
不必在内存中复制相同的信息。

KeyedCollection类

索引器显示组合键

  using System.Collections.ObjectModel; namespace IntIntKeyedCollection { class Program { static void Main(string[] args) { Int32Int32DateO iid1 = new Int32Int32DateO(0, 1, new DateTime(2007, 6, 1, 8, 30, 52)); Int32Int32DateO iid2 = new Int32Int32DateO(0, 1, new DateTime(2007, 6, 1, 8, 30, 52)); if (iid1 == iid2) Console.WriteLine("same"); if (iid1.Equals(iid2)) Console.WriteLine("equals"); // that are equal but not the same I don't override = so I have both features Int32Int32DateCollection int32Int32DateCollection = new Int32Int32DateCollection(); // dont't have to repeat the key like Dictionary int32Int32DateCollection.Add(new Int32Int32DateO(0, 0, new DateTime(2008, 5, 1, 8, 30, 52))); int32Int32DateCollection.Add(new Int32Int32DateO(0, 1, new DateTime(2008, 6, 1, 8, 30, 52))); int32Int32DateCollection.Add(iid1); //this would thow a duplicate key error //int32Int32DateCollection.Add(iid2); //this would thow a duplicate key error //int32Int32DateCollection.Add(new Int32Int32DateO(0, 1, new DateTime(2008, 6, 1, 8, 30, 52))); Console.WriteLine("count"); Console.WriteLine(int32Int32DateCollection.Count.ToString()); // reference by ordinal postion (note the is not the long key) Console.WriteLine("oridinal"); Console.WriteLine(int32Int32DateCollection[0].GetHashCode().ToString()); // reference by index Console.WriteLine("index"); Console.WriteLine(int32Int32DateCollection[0, 1, new DateTime(2008, 6, 1, 8, 30, 52)].GetHashCode().ToString()); Console.WriteLine("foreach"); foreach (Int32Int32DateO iio in int32Int32DateCollection) { Console.WriteLine(string.Format("HashCode {0} Int1 {1} Int2 {2} DateTime {3}", iio.GetHashCode(), iio.Int1, iio.Int2, iio.Date1)); } Console.WriteLine("sorted by date"); foreach (Int32Int32DateO iio in int32Int32DateCollection.OrderBy(x => x.Date1).ThenBy(x => x.Int1).ThenBy(x => x.Int2)) { Console.WriteLine(string.Format("HashCode {0} Int1 {1} Int2 {2} DateTime {3}", iio.GetHashCode(), iio.Int1, iio.Int2, iio.Date1)); } Console.ReadLine(); } public class Int32Int32DateCollection : KeyedCollection<Int32Int32DateS, Int32Int32DateO> { // This parameterless constructor calls the base class constructor // that specifies a dictionary threshold of 0, so that the internal // dictionary is created as soon as an item is added to the // collection. // public Int32Int32DateCollection() : base(null, 0) { } // This is the only method that absolutely must be overridden, // because without it the KeyedCollection cannot extract the // keys from the items. // protected override Int32Int32DateS GetKeyForItem(Int32Int32DateO item) { // In this example, the key is the part number. return item.Int32Int32Date; } // indexer public Int32Int32DateO this[Int32 Int1, Int32 Int2, DateTime Date1] { get { return this[new Int32Int32DateS(Int1, Int2, Date1)]; } } } public struct Int32Int32DateS { // required as KeyCollection Key must be a single item // but you don't really need to interact with Int32Int32DateS directly public readonly Int32 Int1, Int2; public readonly DateTime Date1; public Int32Int32DateS(Int32 int1, Int32 int2, DateTime date1) { this.Int1 = int1; this.Int2 = int2; this.Date1 = date1; } } public class Int32Int32DateO : Object { // implement other properties public Int32Int32DateS Int32Int32Date { get; private set; } public Int32 Int1 { get { return Int32Int32Date.Int1; } } public Int32 Int2 { get { return Int32Int32Date.Int2; } } public DateTime Date1 { get { return Int32Int32Date.Date1; } } public override bool Equals(Object obj) { //Check for null and compare run-time types. if (obj == null || !(obj is Int32Int32DateO)) return false; Int32Int32DateO item = (Int32Int32DateO)obj; return (this.Int32Int32Date.Int1 == item.Int32Int32Date.Int1 && this.Int32Int32Date.Int2 == item.Int32Int32Date.Int2 && this.Int32Int32Date.Date1 == item.Int32Int32Date.Date1); } public override int GetHashCode() { return (((Int64)Int32Int32Date.Int1 << 32) + Int32Int32Date.Int2).GetHashCode() ^ Int32Int32Date.GetHashCode(); } public Int32Int32DateO(Int32 Int1, Int32 Int2, DateTime Date1) { Int32Int32DateS int32Int32Date = new Int32Int32DateS(Int1, Int2, Date1); this.Int32Int32Date = int32Int32Date; } } } } 

至于使用值types的fpr微软专门针对它的build议。

ValueType.GetHashCode

元组在技术上不是一个值types,但遭受同样的症状(散列冲突),并不是一个密钥的好候选者。

我可以build议一个替代scheme – 一个匿名的对象。 这与我们在GroupBy LINQ方法中使用多个键是一样的。

 var dictionary = new Dictionary<object, string> (); dictionary[new { a = 1, b = 2 }] = "value"; 

这可能看起来很奇怪,但我已经用Tuple.GetHashCode和new {a = 1,b = 2}进行了基准testing.GetHashCode方法和匿名对象在我的机器上在.NET 4.5.1上胜出:

对象 – 1000个周期内10000个呼叫的89,1732毫秒

元组 – 在1000个周期内10000个呼叫的738,4475毫秒

现在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)]; 

我select用匿名ValueTuple (string, string, int)声明字典。 但我可以给他们的名字(string name, string path, int id)

Perfwise,新的ValueTuple在GetHashCode比Tuple快,但在Equals慢。 我想你需要做一些完整的端到端实验来找出哪个scheme是最快的。 但是,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 

另一个解决scheme已经提到的将存储到目前为止生成的所有键的列表,当一个新的对象生成时,你生成的哈希码(就像一个起点),检查它是否已经在列表中,如果它是,然后添加一些随机值等,直到你有一个唯一的关键,然后存储在对象本身和列表中的密钥,并返回作为关键在任何时候。