Kamus Kunci Komposit

Saya memiliki beberapa objek di List, katakanlah List<MyClass>dan MyClass memiliki beberapa properti. Saya ingin membuat indeks dari daftar berdasarkan 3 properti MyClass. Dalam kasus ini 2 properti adalah int, dan satu properti adalah datetime.

Pada dasarnya saya ingin bisa melakukan sesuatu seperti:

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

Saya terkadang membuat beberapa kamus pada daftar untuk mengindeks properti berbeda dari kelas yang dimilikinya. Saya tidak yakin bagaimana cara terbaik menangani kunci komposit. Saya mempertimbangkan untuk melakukan checksum dari tiga nilai tetapi ini berisiko bentrok.

Anda harus menggunakan tupel. Mereka setara dengan kelas CompositeKey, tetapi Equals () dan GetHashCode () sudah diimplementasikan untuk Anda.

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

Atau menggunakan System.Linq

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

Kecuali Anda perlu menyesuaikan penghitungan hash, lebih mudah menggunakan tupel.

Jika ada banyak properti yang ingin Anda sertakan dalam kunci komposit, nama tipe Tuple bisa menjadi cukup panjang, tetapi Anda dapat membuat nama lebih pendek dengan membuat kelas Anda sendiri yang berasal dari Tuple <...>.

** diedit tahun 2017 **

Ada opsi baru yang dimulai dengan C # 7: tupel nilai . Idenya sama, tetapi sintaksnya berbeda, lebih ringan:

Jenisnya Tuple<int, bool, string>menjadi (int, bool, string), dan nilainya Tuple.Create(4, true, "t")menjadi (4, true, "t").

Dengan tupel nilai, dimungkinkan juga untuk memberi nama elemen. Perhatikan bahwa kinerja sedikit berbeda, jadi Anda mungkin ingin melakukan pembandingan jika itu penting bagi Anda.

Cara terbaik yang bisa saya pikirkan adalah dengan membuat struct CompositeKey dan pastikan untuk mengganti metode GetHashCode () dan Equals () untuk memastikan kecepatan dan akurasi saat bekerja dengan koleksi:

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

Artikel MSDN di GetHashCode ():

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

Bagaimana dengan Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>>?

Ini akan memungkinkan Anda untuk melakukan:

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

Anda dapat menyimpannya dalam struct dan menggunakannya sebagai kuncinya:

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

Tautan untuk mendapatkan kode hash: http://msdn.microsoft.com/en-us/library/system.valuetype.gethashcode.aspx

Sekarang VS2017 / C # 7 telah keluar, jawaban terbaik adalah menggunakan 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)];

Saya memilih untuk mendeklarasikan kamus dengan ValueTuple anonim (string, string, int). Tapi saya bisa memberi mereka nama (string name, string path, int id).

Secara sempurna, ValueTuple baru lebih cepat daripada Tuple GetHashCodetetapi lebih lambat pada Equals. Saya pikir Anda perlu melakukan eksperimen ujung ke ujung untuk mencari tahu mana yang paling cepat untuk skenario Anda. Namun kesempurnaan dan sintaks bahasa ujung ke ujung untuk ValueTuple membuatnya menang.

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

Dua pendekatan segera muncul di benak:

1. Lakukan seperti yang disarankan Kevin dan tulis struktur yang akan berfungsi sebagai kunci Anda. Pastikan untuk membuat struct ini mengimplementasikan IEquatable<TKey>dan mengganti metode Equalsdan GetHashCode* nya.

2. Tulis kelas yang menggunakan kamus bertingkat secara internal. Sesuatu seperti: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue>... kelas ini akan secara internal memiliki anggota tipe Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>>, dan akan mengekspos metode seperti this[TKey1 k1, TKey2 k2, TKey3 k3], ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3), dll

* Sepatah kata tentang apakah Equalsperlu mengganti metode: meskipun benar bahwa Equalsmetode untuk struct membandingkan nilai setiap anggota secara default, ia melakukannya dengan menggunakan refleksi - yang secara inheren memerlukan biaya kinerja - dan oleh karena itu tidak terlalu implementasi yang tepat untuk sesuatu yang dimaksudkan untuk digunakan sebagai kunci dalam kamus (menurut saya, bagaimanapun). Menurut dokumentasi MSDN di ValueType.Equals:

Implementasi default dari metode Equals menggunakan refleksi untuk membandingkan bidang yang sesuai dari obj dan contoh ini. Mengganti metode Sama dengan untuk jenis tertentu guna meningkatkan kinerja metode dan mewakili konsep kesetaraan untuk jenis tersebut dengan lebih dekat.

Jika kuncinya adalah bagian dari kelas maka gunakan KeyedCollection.
Di Dictionarysinilah kunci diturunkan dari objek.
Di bawah sampulnya adalah Kamus
Tidak perlu mengulang kunci dalam Keydan Value.
Mengapa mengambil kesempatan kuncinya tidak sama Keydengan Value.
Tidak perlu menduplikasi informasi yang sama di memori.

Kelas KeyedCollection

Pengindeks untuk mengekspos kunci komposit

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

Adapun untuk menggunakan tipe nilai fpr, kunci yang secara khusus disarankan oleh Microsoft untuk tidak menggunakannya.

ValueType.GetHashCode

Tuple secara teknis bukan tipe nilai tetapi menderita gejala yang sama (benturan hash) dan bukan kandidat yang baik untuk kunci.

Izinkan saya menyarankan alternatif - objek anonim. Ini sama dengan yang kami gunakan dalam metode GroupBy LINQ dengan banyak kunci.

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

Ini mungkin terlihat aneh, tetapi saya telah membandingkan Tuple.GetHashCode dan metode {a = 1, b = 2} baru .GetHashCode dan objek anonim menang di mesin saya pada .NET 4.5.1:

Objek - 89,1732 md untuk 10.000 panggilan dalam 1000 siklus

Tuple - 738,4475 ms untuk 10000 panggilan dalam 1000 siklus

Solusi lain untuk yang telah disebutkan adalah menyimpan semacam daftar semua kunci yang dihasilkan sejauh ini dan ketika objek baru dibuat, Anda menghasilkan kode hashnya (hanya sebagai titik awal), periksa apakah sudah ada dalam daftar, jika itu adalah, lalu tambahkan beberapa nilai acak dll ke dalamnya sampai Anda mendapatkan kunci unik, kemudian simpan kunci itu di objek itu sendiri dan dalam daftar dan kembalikan sebagai kunci setiap saat.