Правильное использование пользовательской структуры данных для многопользовательского словаря

Question

В какой-то момент во время моего приложения я столкнулся с необходимостью иметь три строковых ключа для экземпляра класса (я использую C# 3.5, поэтому я не мог использовать кортеж). Глядя в Интернете, я наткнулся на этот ответ код которого я использовал: https://stackoverflow.com/a/15804355/5090537

После пошива свои биты и куски для моих нужд, в конце концов, мой пользовательский класс выглядел следующим образом:

public class MultiKeyDictionary<K1, K2, K3, V> : Dictionary<K1, MultiKeyDictionary<K2, K3, V>> 
{ 
    public V this[K1 key1, K2 key2, K3 key3] 
    { 
     get 
     { 
      return ContainsKey(key1) ? this[key1][key2, key3] : default(V); 
     } 
     set 
     { 
      if (!ContainsKey(key1)) 
       this[key1] = new MultiKeyDictionary<K2, K3, V>(); 
      this[key1][key2, key3] = value; 
     } 
    } 

    public bool ContainsKey(K1 key1, K2 key2, K3 key3) 
    { 
     return base.ContainsKey(key1) && this[key1].ContainsKey(key2, key3); 
    } 

    public void Add(K1 key1, K2 key2, K3 key3, V value) 
    { 
     if (!ContainsKey(key1)) 
      this[key1] = new MultiKeyDictionary<K2, K3, V>(); 
     if (!this[key1].ContainsKey(key2, key3)) 
      this[key1][key2] = new Dictionary<K3, V>(); 
     this[key1][key2][key3] = value; 
    } 
} 

Это работало отлично подходит для мои потребности, но у меня есть несколько вопросов по этой структуре данных:

1) Поскольку я действительно наследую от Dictionary(K1, Dictionary(K2, V)), правильно ли предположить, что для меня реализовано GetHashCode, и мне не нужно указывать отдельную реализацию ? И то же самое для Равных?

2) Является ли также предпосылкой, что мне нужно было создать свой собственный пользовательский класс правильно? Так как я не мог использовать строковый массив или список строк, например, потому что тогда было бы сравнение ReferenceEquals вместо того, чтобы мне было необходимо сравнение попорядка (ключ1 равен ключу1, key2, равному ключу2, и key3, равному ключу3)?

Answer 1

Ну, это хороший план, чтобы создать собственную структуру с тремя ключами, которая будет хранить ключи, но сначала давайте посмотрим source code на KeyValuePair struct.

Теперь давайте определим нашу собственную TripleKey-структуру:

[Serializable] 
public struct TripleKey<TKeyA, TKeyB, TKeyC> 
{ 
    public TKeyA KeyA { get; }; 
    public TKeyB KeyB { get; }; 
    public TKeyC KeyC { get; }; 

    public TripleKey(TKeyA keyA, TKeyB keyB, TKeyC keyC) 
    { 
     this.KeyA = keyA; 
     this.KeyB = keyB; 
     this.KeyC = keyC; 
    } 

    // this code is almost the same as it is in Microsoft implementation 
    public override string ToString() 
    { 
     var sBuilder = new StringBuilder(); 
     sBuilder.Append('('); 
     if (KeyA != null) 
     { 
      sBuilder.Append(KeyA.ToString()); 
     } 
     sBuilder.Append(", "); 
     if (KeyB != null) 
     { 
      sBuilder.Append(KeyB.ToString()); 
     } 
     sBuilder.Append(", "); 
     if (KeyC != null) 
     { 
      sBuilder.Append(KeyC.ToString()); 
     } 
     sBuilder.Append(')'); 
     return sBuilder.ToString(); 
    } 
} 

public static class TripleKey 
{ 
    public static TripleKey<TKeyA, TKeyB, TKeyC> Create<TKeyA, TKeyB, TKeyC>(TKeyA keyA, TKeyB keyB, TKeyC keyC) 
    { 
     return new TripleKey<TKeyA, TKeyB, TKeyC>(keyA, keyB, keyC); 
    } 
} 

public class MultiKeyDictionary<TKeyA, TKeyB, TKeyC, TValue> : Dictionary<TripleKey<TKeyA, TKeyB, TKeyC>, TValue> 
{ 
    public TValue this[TKeyA keyA, TKeyB keyB, TKeyC keyC] 
    { 
     get 
     { 
      var key = TripleKey.Create(keyA, keyB, keyC); 
      return base.ContainsKey(key) ? base[key] : default(TValue); 
     } 
     set 
     { 
      var key = TripleKey.Create(keyA, keyB, keyC); 
      if (!ContainsKey(key)) 
       base.Add(key, value); 

      this[key] = value; 
     } 
    } 

    public bool ContainsKey(TKeyA keyA, TKeyB keyB, TKeyC keyC) 
    { 
     var key = TripleKey.Create(keyA, keyB, keyC); 

     return base.ContainsKey(key); 
    } 

    public void Add(TKeyA keyA, TKeyB keyB, TKeyC keyC, TValue value) 
    { 
     base.Add(TripleKey.Create(keyA, keyB, keyC), value); 
    } 
} 

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

Теперь у нас есть все, и мы готовы использовать либо MultiKeyDictionary<TKeyA, TKeyB, TKeyC, TValue>, либо просто Dictionary<TripleKey<TKeyA, TKeyB, TKeyC>, TValue>.

Простой пример:

var myDict = new MultiKeyDictionary<string, double, double, string> 
{ 
    {"Goodbye", 0.55, 9.00, "yaya"} // collection initializer works fine 
}; 

myDict.Add("Hello", 1.11, 2.99, "hi"); 

Console.WriteLine(myDict.ContainsKey("Hello", 1.11, 2.99)); // true 
Console.WriteLine(myDict.ContainsKey("a", 1.11, 2.99));  // false 
Console.WriteLine(myDict["Hello", 1.11, 2.99]);    // hi 

myDict.Add(TripleKey.Create("Hello", 1.11, 2.99), "gh");  // bang! exception, 
                  // key already exists 

P.S.

Как правильно отметил ScottChamberlain, метод ValueTypeimplementation of GetHashcode имеет свои плюсы и минусы. Он использует отражение, и это может привести к проблемам с производительностью, поэтому может быть лучше не полагаться на реализацию структуры GetHashCode и переопределить ее с помощью специальной реализации.

В блоге Эрика Липперта есть замечательная статья, которая называется «Guidelines and rules for GetHashCode».

Рабочий пример: https://dotnetfiddle.net/y1a30V

Answer 2

GetHashCode

Метод GetHashCode используется в качестве «дешевого» (быстрый) способ проверить два экземпляра вашего класса равенства. Вызов GetHashCode для двух одинаковых экземпляров должен всегда произвести тот же результат. Следовательно, если результат вызова не является одинаковым для обоих экземпляров, то они не могут быть равны, и поэтому нет необходимости делать более подробное (и более «дорогое») сравнение.

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

Итак, если вы не повторно определяя, что означает «равный» для вашего класса, вам, вероятно, не нужно беспокоиться о GetHashCode. Понятие «равенство» для вашего класса в любом случае не очень полезно.

Class Design

Я не уверен, что класс вы реализовали это идеальный вариант. Поскольку вы наследуете от Dictionary, вы унаследовали некоторые методы, которые на самом деле не соответствуют вашему классу.

Например, у вашего класса теперь есть метод Keys, который возвращает ключи верхнего уровня (key1), а не трехзначные ключи, которые ваш класс фактически представляет.

Интересно, если это было бы лучше реализовать класс, агрегаты словаря, а не тот, который наследует от словаря.

Другим вариантом в отсутствие Tuple было бы определить ваш собственный класс TriKey<K1, K2, K3> (с 3 свойствами, которые описывают ваши значения ключей), и просто используйте Dictionary<TriKey<K1, K2, K3>, V>. В этом случае вы абсолютно : хотите определить равенство для вашего класса TriKey, и вам нужно будет поддерживать GetHashCode в соответствии с этим определением равенства, поскольку поиск словарей является одним из мест, где он используется.

Разное

Один последний момент, что некоторые могли бы рассмотреть преждевременному оптимизации. Код:

this[key1][key2][key3] = value; 

... будет выполнять 2 подстановочные значения, которые у вас есть уже неправдоподобные (так как вы уже обращались this[key1] и this[key1][key2]). Возможно, вы захотите использовать локальные переменные для хранения этих промежуточных результатов.

Например:

MultiKeyDictionary<K2, K3, V> d1; 
if (!TryGetValue(key1, out d1)) 
{ 
    d1 = new MultiKeyDictionary<K2, K3, V>(); 
    this[key1] = d1; 
} 

// now use d1 rather than "this[key1]" 

... и так далее для других.

Answer 3

Это, вероятно, самый простой способ сделать то, что вы после:

public class MultiKeyDictionary<TKey, TValue> : Dictionary<Tuple<TKey, TKey, TKey>, TValue> 
{ 
    public MultiKeyDictionary() 
     : base() 
    { 
    } 
    ... 
} 

class Program 
{ 
    static void Main(string[] args) 
    { 
     // C# 6.0 syntax 
     var multiKeyDictionary = new MultiKeyDictionary<string, int>(); 
     multiKeyDictionary.Add(Tuple.Create("key1", "key2", "key3"), 36); 

     // C# 7.0 syntax (not yet released). 
     var multiKeyDictionary1 = new MultiDictionary<string, int>(); 
     multiKeyDictionary1.Add(("key1", "key2", "key3"), 36); 
    } 
} 

Когда C# 7.0 отпускании вы можете использовать изящную новую декларацию кортежа.