Composite Key Dictionary

Question

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

Basically I would like to be able 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 multiple dictionaries on a list to index different properties of the classes it holds. I am not sure how best to handle composite keys though. I considered doing a checksum of the three values but this runs the risk of collisions.

Answer 1

You can store them in a struct and use that as the key:

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

Link to get hash code: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

Answer 2

Two approaches immediately spring to mind:

1. Do as Kevin suggested and write a struct that will serve as your key. Be sure to make this struct implement IEquatable<TKey> and to override its Equals and GetHashCode methods*.

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

*A word on whether overriding the Equals method is necessary: while it's true that the Equals method for a struct compares the value of each member by default, it does so by using reflection -- which inherently entails performance costs -- and is therefore not a very appropriate implementation for something that is meant to be used as a key in a dictionary (in my opinion, anyway). According to the MSDN documentation on ValueType.Equals:

The default implementation of the Equals method uses reflection to compare the corresponding fields of obj and this instance. Override the Equals method for a particular type to improve the performance of the method and more closely represent the concept of equality for the type.

Answer 3

The best way I could think of is to create a CompositeKey struct and make sure to override the GetHashCode() and Equals() methods in order 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.Int1 = 304;
        compositeKey1.DateTime = firstTimestamp;

        compositeKeyDictionary[compositeKey1] = "FirstObject";

        CompositeKey compositeKey2 = new CompositeKey();
        compositeKey2.Int1 = 12;
        compositeKey2.Int1 = 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.Int1 = 304;
        compositeKeyLookup1.DateTime = firstTimestamp;

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

        CompositeKey compositeKeyLookup2 = new CompositeKey();
        compositeKeyLookup2.Int1 = 12;
        compositeKeyLookup2.Int1 = 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;
        }
    }
}

An MSDN article on GetHashCode():

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

Answer 4

Another solution to the ones already mentioned would be to store some kind of list of all keys generated so far and when a new object is generated you generate it's hashcode (just as a starting point), check if it's already in the list, if it is, then add some random value etc to it until you've got a unique key, then store that key in the object itself and in the list and return that as the key at all times.

Answer 5

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

This would allow you to do:

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