Composite Keyword Dictionary

Question

I have some objects in a List, say List<MyClass> , and MyClass has several properties. I would like to create a list index based on 3 properties of MyClass. In this case, 2 properties are int, and one property is datetime.

Basically, I would like to do something like:

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

I sometimes create several dictionaries in a list to index the various properties of the classes that it holds. I am not sure how best to work with composite keys. I considered performing a checksum of three values, but this runs the risk of collisions.

Answer 1

You must use tuples. They are equivalent to the CompositeKey class, but Equals () and GetHashCode () are already implemented for you.

 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")]; 

Or using System.Linq

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

If you do not need to configure hash calculation, it is easier to use tuples.

If there are many properties in the composite key that you want to include in the composite key, the Tuple type name can become quite long, but you can make it shorter by creating your own class derived from Tuple <...>.

---

** edited in 2017 **

There is a new parameter starting with C # 7: value tuples. The idea is the same, but the syntax is different, easier:

The type Tuple<int, bool, string> becomes (int, bool, string) , and the value Tuple.Create(4, true, "t") becomes (4, true, "t") .

With tuple values, it also becomes possible to name elements. Please note that performance is slightly different, so you might want to do a benchmarking if they are important to you.

Answer 2

The best way I could think of is to create a CompositeKey structure and make sure to override the GetHashCode () and Equals () methods to ensure speed and accuracy when working with the collection:

 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; } } } 

MSDN article in GetHashCode ():

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

Answer 3

What about Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>> ?

This will allow you to do:

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

Answer 4

You can save them in a structure and use as a key:

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

Hashcode link: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

Answer 5

Two approaches at once spring:

• Do as Kevin suggested, and write a structure that will serve as your key. Be sure to create this IEquatable<TKey> constructor and override its Equals and GetHashCode * methods.

• Write a class that uses nested dictionaries inside. Something like: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue> ... this class will internally have a member of type Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>> and will expose methods like this[TKey1 k1, TKey2 k2, TKey3 k3] , ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3) etc.

* It is necessary to indicate whether the Equals method should be redefined: although it is true that the Equals method for the structure compares the default value of each element, it does this with a reflection, which inherently entails cost performance - and therefore is not a very suitable implementation for something intended to be used as a key in a dictionary (in my opinion, anyway). According to the MSDN documentation on ValueType.Equals :

Standard implementation The Equals method uses reflection to compare the corresponding obj fields with this instance. Override the Equals Method for a specific type to increase the efficiency of the method and more accurately represent the concept of equality for a type.

Answer 6

If the key is part of a class, use KeyedCollection.
This is a dictionary in which the key is obtained from the object.
Under the covers is the Dictionary
No need to repeat the key in the key and value.
Why risk a key is not a key as a value.
No need to duplicate the same information in memory.

KeyedCollection Class

Composite key indexer

  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; } } } } 

Regarding the use of the fpr value type, he specifically recommends Microsoft.

ValueType.GetHashCode

Tuple is technically not a value type, but suffers from the same symptom (hash collision) and is not a good candidate for a key.

Answer 7

May I suggest an alternative - an anonymous object. We use the same thing in the GroupBy LINQ method with multiple keys.

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

This may seem odd, but I tested Tuple.GetHashCode and the new methods {a = 1, b = 2}. GetHashCode and anonymous objects on my machine on .NET 4.5.1:

Object - 89.1732 ms for 10,000 calls in 1000 cycles

Tuple - 738.4475 ms for 10,000 calls in 1000 cycles

Answer 8

Now that VS2017 / C # 7 is out, the best answer is to use 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)]; 

I decided to declare a dictionary with anonymous ValueTuple (string, string, int) . But I could call them names (string name, string path, int id) .

In the first case, the new ValueTuple is faster than the Tuple in GetHashCode , but slower on Equals . I think you will need to do a complete walkthrough experiment to find out which is the fastest for your scenario. But the end and end syntax for ValueTuple makes it a winner.

 // 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 9

Another solution for those already mentioned would be to keep some list of all the keys generated so far, and when a new object is created, you generate its hashcode (as a starting point), check if it is already in the list, if so, add to give it some random value and until you have a unique key, and then save this key in the object itself and in the list and return it as a key at all times.