Словарь составного ключа

У меня есть несколько объектов в List, скажем, List<MyClass>, и MyClass имеет несколько свойств. Я хотел бы создать индекс списка на основе 3 свойств MyClass. В этом случае 2 свойства являются целыми, а одно свойство является датой-временем.

По сути, я хотел бы иметь возможность сделать что-то вроде:

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

Я иногда создаю несколько словарей в списке, чтобы индексировать различные свойства классов, которые он содержит. Я не уверен, как лучше всего работать с композитными ключами. Я подумал сделать контрольную сумму трех значений, но это может привести к коллизиям.

71 голос | спросил AaronLS 21 Mayam10 2010, 00:45:19

9 ответов


0

Вы должны использовать кортежи. Они эквивалентны классу CompositeKey, но Equals () и GetHashCode () уже реализованы для вас.

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

Или используя System.Linq

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

Если вам не нужно настраивать вычисление хэша, проще использовать кортежи.

Если есть много свойств, которые вы хотите включить в составной ключ, имя типа Tuple может стать довольно длинным, но вы можете сократить имя, создав собственный класс, производный от Tuple <... & gt ;.


** отредактировано в 2017 году **

Начиная с C # 7, появилась новая опция: значение кортежей . Идея та же, но синтаксис другой, более легкий:

Тип Tuple<int, bool, string> становится (int, bool, string) и значение Tuple.Create(4, true, "t") становится (4, true, "t").

С помощью кортежей значений также становится возможным присваивать имена элементам. Обратите внимание, что производительность немного отличается, поэтому вы можете захотеть провести сравнительный анализ, если они важны для вас.

ответил Eldritch Conundrum 14 MarpmWed, 14 Mar 2012 13:53:14 +04002012-03-14T13:53:14+04:0001 2012, 13:53:14
0

Лучший способ, о котором я могу подумать, - это создать структуру CompositeKey и убедиться, что переопределяет методы GetHashCode () и Equals (), чтобы обеспечить скорость и точность при работе с коллекцией:

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

Статья MSDN о GetHashCode ():

http://msdn.microsoft.com/en -us /библиотека /system.object.gethashcode.aspx

ответил Allen E. Scharfenberg 21 Mayam10 2010, 00:58:58
0

Как насчет Dictionary<int, Dictionary<int, Dictionary<DateTime, MyClass>>>?

Это позволит вам сделать:

MyClass item = MyData[8][23923][date];
ответил Jason Kleban 21 Mayam10 2010, 01:02:57
0

Вы можете сохранить их в структуре и использовать в качестве ключа:

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

Ссылка для получения хеш-кода: http://msdn.microsoft.com/en-us/library /system.valuetype.gethashcode.aspx

ответил kemiller2002 21 Mayam10 2010, 00:50:07
0

На ум сразу приходят два подхода:

  1. Сделайте, как предложил Кевин, и напишите структуру, которая будет служить вашим ключом. Убедитесь, что в этой структуре реализовано IEquatable<TKey> и переопределите ее Equals и GetHashCode методы *.

  2. Напишите класс, который использует вложенные словари для внутренних целей. Что-то вроде: TripleKeyDictionary<TKey1, TKey2, TKey3, TValue> ... этот класс внутренне будет иметь член типа Dictionary<TKey1, Dictionary<TKey2, Dictionary<TKey3, TValue>>> и предоставит такие методы, как this[TKey1 k1, TKey2 k2, TKey3 k3], ContainsKeys(TKey1 k1, TKey2 k2, TKey3 k3) и т. д.

* Слово о необходимости переопределения метода Equals: правда, Equals для структуры сравнивает значение каждого элемента по умолчанию, он делает это с помощью отражения - что по своей природе влечет за собой снижение производительности - и, следовательно, не очень подходящая реализация для чего-то, что предназначено для использования в качестве ключа в словаре (на мой взгляд, в любом случае). Согласно документации MSDN на ValueType.Equals :

  

Реализация по умолчанию   Метод Equals использует отражение для   сравнить соответствующие поля   объект и этот экземпляр. Переопределить   Метод равных для определенного типа   улучшить производительность метода   и более близко представлять концепцию   равенства для типа.

ответил Dan Tao 21 Mayam10 2010, 00:55:19
0

Теперь, когда вышла VS2017 /C # 7, лучший ответ - использовать 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)];

Я решил объявить словарь анонимным ValueTuple (string, string, int). Но я мог бы дать им имена (string name, string path, int id).

Во-первых, новый ValueTuple быстрее, чем Tuple в GetHashCode, но медленнее в Equals. Я думаю, что вам нужно выполнить полные эксперименты, чтобы выяснить, какой из них действительно самый быстрый для вашего сценария. Но сквозной смысл и синтаксис языка для ValueTuple делают его победителем.

// 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
ответил Lucian Wischik 20 PMpThu, 20 Apr 2017 18:09:48 +030009Thursday 2017, 18:09:48
0

Если ключ является частью класса, используйте KeyedCollection.
Это словарь, в котором ключ получен из объекта.
Под обложками это словарь
Не нужно повторять ключ в ключе и значении.
Зачем рисковать, ключ не совпадает в ключе со значением.
Не нужно дублировать ту же информацию в памяти.

Класс KeyedCollection

Индексатор для предоставления составного ключа

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

Что касается использования значения типа fpr, то ключ, который Microsoft особо рекомендует против него.

ValueType.GetHashCode

Кортеж технически не является типом значения, но страдает от того же симптома (коллизии хеша) и не является хорошим кандидатом на ключ.

ответил paparazzo 2 +04002012-10-02T00:27:12+04:00312012bEurope/MoscowTue, 02 Oct 2012 00:27:12 +0400 2012, 00:27:12
0

Могу я предложить альтернативу - анонимный объект. То же самое мы используем в методе GroupBy LINQ с несколькими ключами.

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

Это может выглядеть странно, но я сравнил Tuple.GetHashCode и новые методы {a = 1, b = 2} .GetHashCode и анонимные объекты побеждают на моей машине в .NET 4.5.1:

Объект - 89,1732 мс на 10000 вызовов в 1000 циклов

Tuple - 738,4475 мс на 10000 вызовов в 1000 циклов

ответил Michael Logutov 14 +04002014-10-14T21:16:50+04:00312014bEurope/MoscowTue, 14 Oct 2014 21:16:50 +0400 2014, 21:16:50
0

Еще одним решением для уже упомянутых было бы сохранить какой-то список всех ключей, сгенерированных до сих пор, и когда генерируется новый объект, вы генерируете его хэш-код (просто в качестве отправной точки), проверяете, есть ли он уже в списке Если это так, то добавьте к нему случайное значение и т. д., пока не получите уникальный ключ, затем сохраните этот ключ в самом объекте и в списке и всегда возвращайте его в качестве ключа.

ответил Hans Olsson 21 Mayam10 2010, 01:00:42

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132