Dictionnaire de clés composite

J’ai des objects dans List, disons List 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, deux des propriétés sont int et une propriété est un datetime.

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

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

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

Vous devriez 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, MyClass>(); //Populate dictionary with items from the List MyClassList foreach (var myObj in myClassList) myClassIndex.Add(Tuple.Create(myObj.MyInt, myObj.MyBool, myObj.MySsortingng), 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.MySsortingng)); MyClass myObj = myClassIndex[Tuple.Create(4, true, "t")]; 

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

Si vous souhaitez inclure de nombreuses propriétés 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érivée 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 claire:

Le type Tuple devient (int, bool, ssortingng) 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 pouvez donc faire des parsings comparatives si elles vous intéressent.

La meilleure façon de penser à cela est de créer une structure CompositeKey et de vous assurer de remplacer les méthodes GetHashCode () et Equals () afin d’assurer la rapidité et la précision du travail avec la collection:

 class Program { static void Main(ssortingng[] args) { DateTime firstTimestamp = DateTime.Now; DateTime secondTimestamp = firstTimestamp.AddDays(1); /* begin composite key dictionary populate */ Dictionary compositeKeyDictionary = new Dictionary(); 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 de Dictionary>> ?

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

Deux approches viennent immédiatement à l’esprit:

  1. Faites comme Kevin l’a suggéré et écrivez une structure qui vous servira de clé. Veillez à faire en sorte que cette structure implémente IEquatable et remplace ses méthodes Equals et GetHashCode *.

  2. Ecrivez une classe qui utilise des dictionnaires nesteds en interne. Quelque chose comme: TripleKeyDictionary … cette classe aurait en interne un membre de type Dictionary>> et exposerait des méthodes comme celle- this[TKey1 k1, TKey2 k2, TKey3 k3] , ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3) , etc.

* Un mot pour savoir si le Equals méthode Equals est nécessaire: s’il est vrai que la méthode Equals pour une structure compare la valeur de chaque membre par défaut, elle le fait en utilisant la reflection – ce qui implique une implémentation très appropriée pour quelque chose qui doit être utilisé comme clé dans un dictionnaire (à mon avis, de toute façon). Selon la documentation MSDN sur ValueType.Equals :

L’implémentation par défaut de la méthode Equals utilise la reflection pour comparer les champs correspondants de obj et de cette instance. Remplacer la méthode Equals pour un type particulier pour améliorer les performances de la méthode et représenter plus étroitement le concept d’égalité pour le type.

Si la clé fait partie de la classe, utilisez KeyedCollection.
C’est un dictionnaire où la clé est dérivée de l’object.
Sous les couvertures c’est Dictionnaire
Ne pas avoir à répéter la clé dans la clé et la valeur.
Pourquoi prendre la chance que la clé ne soit pas la même dans la clé que la valeur?
Ne pas avoir à 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(ssortingng[] 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.ToSsortingng()); // reference by ordinal postion (note the is not the long key) Console.WriteLine("oridinal"); Console.WriteLine(int32Int32DateCollection[0].GetHashCode().ToSsortingng()); // reference by index Console.WriteLine("index"); Console.WriteLine(int32Int32DateCollection[0, 1, new DateTime(2008, 6, 1, 8, 30, 52)].GetHashCode().ToSsortingng()); Console.WriteLine("foreach"); foreach (Int32Int32DateO iio in int32Int32DateCollection) { Console.WriteLine(ssortingng.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(ssortingng.Format("HashCode {0} Int1 {1} Int2 {2} DateTime {3}", iio.GetHashCode(), iio.Int1, iio.Int2, iio.Date1)); } Console.ReadLine(); } public class Int32Int32DateCollection : KeyedCollection { // 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 ce qui concerne l'utilisation du type de valeur fpr, la clé que Microsoft lui recommande spécifiquement.

ValueType.GetHashCode

Le tuple n'est techniquement pas un type de 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 object anonyme. C’est la même chose que nous utilisons dans la méthode GroupBy LINQ avec plusieurs clés.

 var dictionary = new Dictionary (); 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 objects anonymes gagnent sur ma machine sur .NET 4.5.1:

Object – 89,1732 ms pour 10000 appels en 1000 cycles

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

Maintenant que VS2017 / C # 7 est sorti, la meilleure solution 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 (ssortingng, ssortingng, int) . Mais j'aurais pu leur donner des noms (ssortingng name, ssortingng path, int id) .

Perfwise, le nouveau ValueTuple est plus rapide que Tuple à GetHashCode mais plus lent à Equals . Je pense que vous devez faire des expériences complètes de bout en bout pour déterminer ce qui est le plus rapide pour votre scénario. Mais la syntaxe de la finesse et du langage de bout en bout pour ValueTuple le fait 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 

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