elementat - c# dictionary vs hashtable

Diccionario clave compuesto

Question

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 datetime.

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. Aunque no estoy seguro de cómo manejar mejor las claves compuestas. Consideré hacer una suma de comprobación de los tres valores, pero esto corre el riesgo de colisiones.

Answer 1

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

Esto te permitiría hacer:

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

Answer 2

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

Decidí declarar el diccionario con 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 GetHashCode pero más lento en Equals . Creo que tendrías que hacer experimentos completos de extremo a extremo para descubrir cuál es el más rápido para tu situación. Pero la amabilidad de extremo a extremo y la sintaxis del lenguaje para ValueTuple lo hacen ganar.

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

Answer 3

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

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 fácil usar tuplas.

Si hay muchas propiedades que desea incluir en la clave compuesta, el nombre de tipo Tuple puede ser 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: el valor de las tuplas . La idea es la misma, pero la sintaxis es diferente, más clara:

El tipo Tuple<int, bool, string> convierte en (int, bool, string) , y el valor 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 las actuaciones son ligeramente diferentes, por lo que es posible que desee hacer una evaluación comparativa si son importantes para usted.

Answer 4

Dos enfoques inmediatamente vienen a la mente:

1. Haz lo que Kevin sugirió y escribió una estructura que servirá como tu clave. Asegúrese de hacer que esta estructura implemente IEquatable<TKey> y anule sus métodos Equals y GetHashCode *.

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

* Una palabra sobre si es necesario reemplazar el método Equals : si bien es cierto que el método Equals para una estructura compara el valor de cada miembro por defecto, lo hace mediante el uso de la reflexión, que implica costos de rendimiento, y por lo tanto no una implementación muy apropiada para algo que debe usarse como clave en un diccionario (en mi opinión, de todos modos). De acuerdo con 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 particular para mejorar el rendimiento del método y represente más de cerca el concepto de igualdad para el tipo.

Answer 5

La mejor manera en que podría pensar es en crear una estructura CompositeKey y asegúrese 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 en GetHashCode ():

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

Answer 6

Otra solución a las ya mencionadas sería almacenar algún tipo de lista de todas las claves generadas hasta el momento y cuando se genere un nuevo objeto genere su código hash (solo como punto de partida), verifique 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.

Answer 7

Puede almacenarlos en una estructura y usarlos como la clave:

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

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

Answer 8

Puedo sugerir una alternativa, un objeto anónimo. Es lo mismo que utilizamos en el método GroupBy LINQ con varias claves.

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

Puede parecer extraño, pero he comparado los métodos Tuple.GetHashCode y new {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

Tuple - 738,4475 ms para 10000 llamadas en 1000 ciclos

Answer 9

Si la clave es parte de la clase, entonces use KeyedCollection.
Es un diccionario donde la clave se deriva del objeto.
Bajo las cubiertas es diccionario
No tiene que repetir la clave en la clave y el valor.
¿Por qué arriesgarse? La clave no es la misma en la clave que el valor.
No tiene que duplicar 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 Microsoft recomienda específicamente no hacerlo.

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

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