Domanda Dizionario chiave composito


Ho alcuni oggetti in List, diciamo List<MyClass> e MyClass ha diverse proprietà. Vorrei creare un indice dell'elenco basato su 3 proprietà di MyClass. In questo caso, 2 delle proprietà sono int e una proprietà è un datetime.

Fondamentalmente mi piacerebbe essere in grado di fare qualcosa come:

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

A volte creo più dizionari su un elenco per indicizzare diverse proprietà delle classi che contiene. Non sono sicuro di come sia meglio gestire le chiavi composite. Ho considerato di fare un checksum dei tre valori, ma questo comporta il rischio di collisioni.


70
2018-05-20 20:45


origine


risposte:


Dovresti usare le tuple. Sono equivalenti a una classe CompositeKey, ma Equals () e GetHashCode () sono già stati implementati per te.

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 utilizzando System.Linq

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

A meno che non sia necessario personalizzare il calcolo dell'hash, è più semplice utilizzare le tuple.

Se ci sono molte proprietà che vuoi includere nella chiave composta, il nome del tipo Tupla può diventare piuttosto lungo, ma puoi rendere il nome più breve creando la tua classe derivata da Tuple <...>.


** modificato nel 2017 **

C'è una nuova opzione che inizia con C # 7: il valore tuple. L'idea è la stessa, ma la sintassi è diversa, più leggera:

Il tipo Tuple<int, bool, string> diventa (int, bool, string)e il valore Tuple.Create(4, true, "t") diventa (4, true, "t").

Con le tuple di valore, diventa anche possibile nominare gli elementi. Nota che le prestazioni sono leggermente diverse, quindi potresti voler fare un benchmarking se sono importanti per te.


87
2018-03-14 09:53



Il modo migliore che potrei pensare è creare una struttura CompositeKey e assicurarsi per sovrascrivere i metodi GetHashCode () ed Equals () per garantire velocità e precisione quando si lavora con la raccolta:

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 articolo MSDN su GetHashCode ():

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


20
2018-05-20 20:58



Che ne dite di Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>>?

Questo ti permetterebbe di fare:

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

12
2018-05-20 21:02



Puoi memorizzarli in una struttura e usarli come chiave:

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

Link per ottenere il codice hash: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx


11
2018-05-20 20:50



Mi vengono subito in mente due approcci:

  1. Fai come suggerito Kevin e scrivi una struttura che servirà da chiave. Assicurati di fare in modo che questa struttura si attui IEquatable<TKey> e per sovrascriverne Equals e GetHashCode metodi *.

  2. Scrivi una classe che utilizza internamente i dizionari nidificati. Qualcosa di simile a: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue>... questa classe avrebbe internamente un membro di tipo Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>>e esporrà metodi come this[TKey1 k1, TKey2 k2, TKey3 k3], ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3), eccetera.

* Una parola sull'override del Equals metodo è necessario: mentre è vero che il Equals il metodo per una struct confronta il valore di ciascun membro per impostazione predefinita, lo fa usando la reflection - che implica intrinsecamente i costi di performance - ed è quindi non un'implementazione molto appropriata per qualcosa che deve essere usato come chiave in un dizionario (secondo me, comunque). Secondo la documentazione MSDN su ValueType.Equals:

L'implementazione predefinita di   Il metodo uguale usa la riflessione su   confrontare i campi corrispondenti di   obj e questa istanza. Ignora il   Metodo uguale per un tipo particolare a   migliorare le prestazioni del metodo   e rappresentano più da vicino il concetto   di uguaglianza per il tipo.


4
2018-05-20 20:55



Se la chiave fa parte della classe, utilizzare KeyedCollection.
È un dizionario in cui la chiave è derivata dall'oggetto.
Sotto le coperte è Dictionary
Non è necessario ripetere la chiave nella chiave e nel valore.
Perché rischiare che la chiave non sia la stessa nella chiave come valore.
Non è necessario duplicare le stesse informazioni in memoria.

KeyedCollection Class

Indicizzatore per esporre la chiave 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;
                }
            }
        }
    }

Per quanto riguarda l'utilizzo del tipo di valore fpr, la chiave Microsoft lo consiglia in modo specifico.

ValueType.GetHashCode

Tuple non è tecnicamente un tipo di valore ma soffre dello stesso sintomo (collisione hash) e non è un buon candidato per una chiave.


3
2017-10-01 20:27



Posso suggerire un'alternativa, un oggetto anonimo. È lo stesso che usiamo nel metodo GroupBy LINQ con più chiavi.

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

Potrebbe sembrare strano, ma ho benchmarkato i metodi Tuple.GetHashCode e new {a = 1, b = 2}. GetHashCode e gli oggetti anonimi vinsero sulla mia macchina su .NET 4.5.1:

Oggetto: 89,1732 ms per 10000 chiamate in 1000 cicli

Tupla - 738,4475 ms per 10000 chiamate in 1000 cicli


3
2017-10-14 17:16



Ora che VS2017 / C # 7 è uscito, la risposta migliore è usare 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)];

Ho scelto di dichiarare il dizionario con un ValueTuple anonimo (string, string, int). Ma avrei potuto dare loro dei nomi (string name, string path, int id).

Perfwise, il nuovo ValueTuple è più veloce di Tuple in GetHashCode ma più lento Equals. Penso che avresti bisogno di fare degli esperimenti end-to-end completi per capire quale sia il più veloce per il tuo scenario. Ma la simpatia end-to-end e la sintassi del linguaggio per ValueTuple lo fanno vincere.

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

3
2018-04-20 15:09