Dictionnaire des clés composites

J'ai des objets dans la liste, disons List<MyClass> et MyClass a plusieurs propriétés. Je voudrais créer un index de la liste basé sur 3 propriétés de MyClass. Dans ce cas, 2 des propriétés sont des int et une propriété est une date / heure.

En gros, j'aimerais pouvoir faire quelque chose comme:

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

Je crée parfois plusieurs dictionnaires sur une liste pour indexer différentes propriétés des classes qu'elle contient. Je ne sais pas comment gérer au mieux les clés composites. J'ai envisagé de faire une somme de contrôle des trois valeurs mais cela risque de provoquer des collisions.

Vous devez utiliser des tuples. Ils sont équivalents à une classe CompositeKey, mais Equals () et GetHashCode () sont déjà implémentés pour vous.

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 en utilisant System.Linq

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

À moins que vous n'ayez besoin de personnaliser le calcul du hachage, il est plus simple d'utiliser des tuples.

S'il y a beaucoup de propriétés que vous souhaitez inclure dans la clé composite, le nom du type Tuple peut devenir assez long, mais vous pouvez raccourcir le nom en créant votre propre classe dérivant de Tuple <...>.

** édité en 2017 **

Il existe une nouvelle option commençant par C # 7: les tuples de valeur . L'idée est la même, mais la syntaxe est différente, plus légère:

Le type Tuple<int, bool, string>devient (int, bool, string)et la valeur Tuple.Create(4, true, "t")devient (4, true, "t").

Avec les tuples de valeur, il devient également possible de nommer les éléments. Notez que les performances sont légèrement différentes, vous voudrez peut-être faire des analyses comparatives si elles comptent pour vous.

La meilleure façon de penser est de créer une structure CompositeKey et de vous assurer de remplacer les méthodes GetHashCode () et Equals () afin d'assurer la vitesse et la précision lorsque vous travaillez avec la 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;
        }
    }
}

Un article MSDN sur GetHashCode ():

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

Que diriez-vous Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>> ?

Cela vous permettrait de faire:

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

Vous pouvez les stocker dans une structure et l'utiliser comme clé:

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

Lien pour obtenir le code de hachage: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

Maintenant que VS2017 / C # 7 est sorti, la meilleure réponse est d'utiliser 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)];

J'ai choisi de déclarer le dictionnaire avec un ValueTuple anonyme (string, string, int). Mais j'aurais pu leur donner des noms(string name, string path, int id) .

Perfwise, le nouveau ValueTuple est plus rapide que Tuple à GetHashCodemais plus lent à Equals. Je pense que vous devrez faire des expériences complètes de bout en bout pour déterminer lequel est vraiment le plus rapide pour votre scénario. Mais la gentillesse de bout en bout et la syntaxe du langage de ValueTuple le font gagner.

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

Deux approches viennent immédiatement à l'esprit:

1. Faites comme Kevin l'a suggéré et écrivez une structure qui vous servira de clé. Assurez-vous de faire implémenter cette structure IEquatable<TKey>et de remplacer ses méthodes Equalset GetHashCode*.

2. Écrivez une classe qui utilise des dictionnaires imbriqués en interne. Quelque chose comme: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue>... cette classe aurait à l' intérieur d' un membre de type Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>>et exposerait des méthodes telles que this[TKey1 k1, TKey2 k2, TKey3 k3], ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3), etc.

* Un mot sur la nécessité de surcharger la Equalsméthode: s'il est vrai que la Equalsméthode pour une structure compare la valeur de chaque membre par défaut, elle le fait en utilisant la réflexion - qui implique intrinsèquement des coûts de performance - et n'est donc pas très implémentation appropriée pour quelque chose qui est censé être utilisé comme clé dans un dictionnaire (à mon avis, en tout cas). Selon la documentation MSDN sur ValueType.Equals:

L'implémentation par défaut de la méthode Equals utilise la réflexion pour comparer les champs correspondants de obj et de cette instance. Remplacez la méthode Equals pour un type particulier pour améliorer les performances de la méthode et représenter plus fidèlement le concept d'égalité pour le type.

Si la clé fait partie de la classe, utilisez KeyedCollection.
C'est un Dictionaryendroit où la clé est dérivée de l'objet.
Sous les couvertures, c'est le dictionnaire
. Pas besoin de répéter la clé dans le Keyet Value.
Pourquoi prendre une chance la clé n'est pas la même dans le Keyque le Value.
Pas besoin de dupliquer les mêmes informations en mémoire.

Classe KeyedCollection

Indexeur pour exposer la clé composite

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

Quant à l'utilisation du type valeur fpr, la clé Microsoft le déconseille spécifiquement.

ValueType.GetHashCode

Tuple n'est techniquement pas un type valeur mais souffre du même symptôme (collisions de hachage) et n'est pas un bon candidat pour une clé.

Puis-je suggérer une alternative - un objet anonyme. C'est la même chose que nous utilisons dans la méthode GroupBy LINQ avec plusieurs clés.

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

Cela peut sembler étrange, mais j'ai comparé Tuple.GetHashCode et les nouvelles méthodes {a = 1, b = 2} .GetHashCode et les objets anonymes gagnent sur ma machine sur .NET 4.5.1:

Objet - 89,1732 ms pour 10000 appels en 1000 cycles

Tuple - 738,4475 ms pour 10000 appels en 1000 cycles

Une autre solution à celles déjà mentionnées serait de stocker une sorte de liste de toutes les clés générées jusqu'à présent et lorsqu'un nouvel objet est généré, vous générez son hashcode (juste comme point de départ), vérifiez s'il est déjà dans la liste, s'il est, puis ajoutez-y une valeur aléatoire, etc. jusqu'à ce que vous ayez une clé unique, puis stockez cette clé dans l'objet lui-même et dans la liste et renvoyez-la comme clé à tout moment.