Dicionário de Chave Composto

Tenho alguns objetos em List, digamos, List<MyClass>e MyClass tem várias propriedades. Eu gostaria de criar um índice da lista com base em 3 propriedades de MyClass. Neste caso, 2 das propriedades são int's e uma propriedade é uma data e hora.

Basicamente, gostaria de ser capaz de fazer algo como:

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

Às vezes, crio vários dicionários em uma lista para indexar diferentes propriedades das classes que ela contém. Não tenho certeza da melhor forma de lidar com chaves compostas. Considerei fazer uma soma de verificação dos três valores, mas isso corre o risco de colisões.

Você deve usar tuplas. Eles são equivalentes a uma classe CompositeKey, mas Equals () e GetHashCode () já estão implementados para você.

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

Ou 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 você precise personalizar o cálculo do hash, é mais simples usar tuplas.

Se houver muitas propriedades que você deseja incluir na chave composta, o nome do tipo Tupla pode ficar bem longo, mas você pode tornar o nome mais curto criando sua própria classe derivada de Tupla <...>.

** editado em 2017 **

Há uma nova opção começando com C # 7: as tuplas de valor . A ideia é a mesma, mas a sintaxe é diferente, mais leve:

O tipo Tuple<int, bool, string>se torna (int, bool, string)e o valor Tuple.Create(4, true, "t")se torna (4, true, "t").

Com tuplas de valor, também é possível nomear os elementos. Observe que as performances são ligeiramente diferentes, então você pode querer fazer alguns benchmarking se forem importantes para você.

A melhor maneira que eu poderia pensar é criar uma estrutura CompositeKey e certificar-se de substituir os métodos GetHashCode () e Equals () para garantir velocidade e precisão ao trabalhar com a coleção:

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

Um artigo MSDN sobre GetHashCode ():

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

Que tal Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>>?

Isso permitiria que você:

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

Você pode armazená-los em uma estrutura e usá-la como a chave:

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

Link para obter o código hash: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

Agora que o VS2017 / C # 7 foi lançado, a melhor resposta é 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)];

Decidi declarar o dicionário com um ValueTuple anônimo (string, string, int). Mas eu poderia ter dado nomes a eles (string name, string path, int id).

Perfwise, o novo ValueTuple é mais rápido do que Tuple em, GetHashCodemas mais lento em Equals. Acho que você precisa fazer experimentos completos de ponta a ponta para descobrir qual é realmente o mais rápido para o seu cenário. Mas a gentileza de ponta a ponta e a sintaxe da linguagem para ValueTuple o fazem vencer.

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

Duas abordagens vêm imediatamente à mente:

1. Faça como Kevin sugeriu e escreva uma estrutura que servirá como sua chave. Certifique-se de fazer essa estrutura implementar IEquatable<TKey>e substituir seus métodos Equalse GetHashCode*.

2. Escreva uma classe que utilize dicionários aninhados internamente. Algo como: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue>... esta classe seria internamente ter um membro do tipo Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>>, e iria expor métodos, como this[TKey1 k1, TKey2 k2, TKey3 k3], ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3), etc.

* Uma palavra sobre se a substituição do Equalsmétodo é necessária: embora seja verdade que o Equalsmétodo para uma estrutura compara o valor de cada membro por padrão, ele o faz usando reflexão - que inerentemente envolve custos de desempenho - e, portanto, não é muito implementação apropriada para algo que deve ser usado como uma chave em um dicionário (na minha opinião, pelo menos). De acordo com a documentação do MSDN sobre ValueType.Equals:

A implementação padrão do método Equals usa reflexão para comparar os campos correspondentes de obj e esta instância. Substitua o método Equals para um tipo específico para melhorar o desempenho do método e representar mais de perto o conceito de igualdade para o tipo.

Se a chave fizer parte da classe, use KeyedCollection.
É Dictionaryonde a chave é derivada do objeto.
Nos bastidores é o Dicionário.
Não é necessário repetir a chave no Keye Value.
Por que arriscar, a chave não é a mesma Keyque no Value.
Não precisa duplicar as mesmas informações na memória.

Classe KeyedCollection

Indexador para expor a chave composta

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

Quanto ao uso do tipo de valor fpr, a chave que a Microsoft especificamente recomenda contra ele.

ValueType.GetHashCode

Tuple tecnicamente não é um tipo de valor, mas sofre do mesmo sintoma (colisões de hash) e não é um bom candidato para uma chave.

Posso sugerir uma alternativa - um objeto anônimo. É o mesmo que usamos no método GroupBy LINQ com várias chaves.

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

Pode parecer estranho, mas eu comparei Tuple.GetHashCode e os novos métodos {a = 1, b = 2} .GetHashCode e os objetos anônimos vencem em minha máquina no .NET 4.5.1:

Objeto - 89,1732 ms para 10.000 chamadas em 1.000 ciclos

Tupla - 738,4475 ms para 10.000 chamadas em 1.000 ciclos

Outra solução às já citadas seria armazenar algum tipo de lista de todas as chaves geradas até agora e quando um novo objeto for gerado você gera o seu hashcode (apenas como ponto de partida), verifique se já está na lista, se estiver é, em seguida, adicione algum valor aleatório etc. a ele até que você tenha uma chave exclusiva, então armazene essa chave no próprio objeto e na lista e retorne-a como a chave o tempo todo.