Diccionario de claves compuestas

Tengo algunos objetos en List, digamos List<MyClass>y MyClass tiene varias propiedades. Me gustaría crear un índice de la lista basado en 3 propiedades de MyClass. En este caso, 2 de las propiedades son int y una propiedad es una fecha y hora.

Básicamente, me gustaría poder hacer algo como:

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

A veces creo varios diccionarios en una lista para indexar diferentes propiedades de las clases que contiene. Sin embargo, no estoy seguro de cuál es la mejor manera de manejar las claves compuestas. Consideré hacer una suma de comprobación de los tres valores, pero esto corre el riesgo de colisiones.

Deberías usar tuplas. Son equivalentes a una clase CompositeKey, pero Equals () y GetHashCode () ya están implementados.

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

O usando System.Linq

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

A menos que necesite personalizar el cálculo del hash, es más sencillo usar tuplas.

Si hay muchas propiedades que desea incluir en la clave compuesta, el nombre del tipo Tuple puede volverse bastante largo, pero puede acortar el nombre creando su propia clase derivada de Tuple <...>.

** editado en 2017 **

Hay una nueva opción que comienza con C # 7: las tuplas de valor . La idea es la misma, pero la sintaxis es diferente, más ligera:

El tipo se Tuple<int, bool, string>convierte en (int, bool, string)y el valor se Tuple.Create(4, true, "t")convierte en (4, true, "t").

Con tuplas de valor, también es posible nombrar los elementos. Tenga en cuenta que los rendimientos son ligeramente diferentes, por lo que es posible que desee realizar una evaluación comparativa si son importantes para usted.

La mejor manera que se me ocurre es crear una estructura CompositeKey y asegurarme de anular los métodos GetHashCode () y Equals () para garantizar la velocidad y precisión al trabajar con la colección:

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

Un artículo de MSDN sobre GetHashCode ():

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

¿Qué tal Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>>?

Esto le permitiría hacer:

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

Puede almacenarlos en una estructura y usar eso como clave:

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

Enlace para obtener el código hash: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

Ahora que ha salido VS2017 / C # 7, la mejor respuesta es usar 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)];

Elegí declarar el diccionario con un ValueTuple anónimo (string, string, int). Pero podría haberles dado nombres (string name, string path, int id).

Perfwise, el nuevo ValueTuple es más rápido que Tuple en GetHashCodepero más lento en Equals. Creo que necesitarías hacer experimentos completos de un extremo a otro para descubrir cuál es realmente más rápido para tu escenario. Pero la amabilidad de un extremo a otro y la sintaxis del lenguaje de ValueTuple hacen que gane.

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

Inmediatamente me vienen a la mente dos enfoques:

1. Haz lo que Kevin sugirió y escribe una estructura que te sirva como clave. Asegúrese de hacer que esta estructura se implemente IEquatable<TKey>y anule sus métodos Equalsy GetHashCode*.

2. Escriba una clase que utilice diccionarios anidados internamente. Algo así como: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue>... esta clase sería internamente tener un miembro de tipo Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>>, y expondría métodos tales como this[TKey1 k1, TKey2 k2, TKey3 k3], ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3), etc.

* Una palabra sobre si Equalses necesario anular el método: si bien es cierto que el Equalsmétodo para una estructura compara el valor de cada miembro de forma predeterminada, lo hace mediante la reflexión, que inherentemente implica costos de rendimiento, y por lo tanto no es muy implementación apropiada para algo que está destinado a ser utilizado como clave en un diccionario (en mi opinión, de todos modos). Según la documentación de MSDN sobre ValueType.Equals:

La implementación predeterminada del método Equals usa la reflexión para comparar los campos correspondientes de obj y esta instancia. Anule el método Equals para un tipo en particular para mejorar el rendimiento del método y representar más de cerca el concepto de igualdad para el tipo.

Si la clave es parte de la clase, utilice KeyedCollection.
Es un lugar Dictionarydonde la clave se deriva del objeto.
Debajo de las sábanas está el Diccionario.
No es necesario repetir la clave en Keyy Value.
Por qué arriesgarse, la clave no es la misma en Keyel Value.
No es necesario que duplique la misma información en la memoria.

Clase KeyedCollection

Indexador para exponer la clave compuesta

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

En cuanto al uso del tipo de valor fpr, la clave que Microsoft recomienda específicamente no hacerlo.

ValueType.GetHashCode

Tuple técnicamente no es un tipo de valor, pero sufre el mismo síntoma (colisiones hash) y no es un buen candidato para una clave.

Puedo sugerir una alternativa: un objeto anónimo. Es el mismo que usamos en el método GroupBy LINQ con múltiples claves.

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

Puede parecer extraño, pero he evaluado Tuple.GetHashCode y los nuevos métodos {a = 1, b = 2} .GetHashCode y los objetos anónimos ganan en mi máquina en .NET 4.5.1:

Objeto: 89,1732 ms para 10000 llamadas en 1000 ciclos

Tupla: 738,4475 ms para 10000 llamadas en 1000 ciclos

Otra solución a las ya mencionadas sería almacenar algún tipo de lista de todas las claves generadas hasta ahora y cuando se genera un nuevo objeto generas su código hash (solo como punto de partida), verifica si ya está en la lista, si es, luego agregue algún valor aleatorio, etc.hasta que tenga una clave única, luego almacene esa clave en el objeto mismo y en la lista y devuélvala como la clave en todo momento.