Блог

Мне нужно использовать Dictionary<long, string> коллекции, которые содержат два экземпляра d1 и d2 где у каждого из них одинаковое KeyValuePair<long, string> содержимое, которое может быть вставлено в любом порядке:

1. (d1 == d2) вычисляется как true
2. d1.GetHashCode() == d2.GetHashCode()

Первое требование было достигнуто проще всего с помощью SortedDictionary вместо обычного Dictionary .

Второе требование необходимо, потому что у меня есть одна точка, где мне нужно сохранить Dictionary<Dictionary<long, string>, List<string> — тип main Dictionary используется в качестве ключа для другого Dictionary , и если хэш-коды не вычисляются на основе идентичного содержимого, использование ContainsKey() не будет работать так, как я хочу (т. Е.: если в словарь уже вставлен элемент с d1 в качестве ключа, то dictionary.ContainsKey(d2) следует вычислить true .

Для достижения этого я создал новый объект class ComparableDictionary : SortedDictionary<long, string> и включил следующее:

 public override int GetHashCode() {            
   StringBuilder str = new StringBuilder();
   foreach (var item in this) {
      str.Append(item.Key);
      str.Append("_");
      str.Append(item.Value);
      str.Append("%%");
   }
   return str.ToString().GetHashCode();
 }
  

В моем модульном тестировании это соответствует критериям как для равенства, так и для хэш-кодов. Однако, читая рекомендации и правила для GetHashCode, я наткнулся на следующее:

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

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

Если хэш-код объекта может изменяться, пока он находится в хэш-таблице, то, очевидно, метод Contains перестает работать. Вы помещаете объект в корзину № 5, изменяете его, и когда вы спрашиваете набор, содержит ли он измененный объект, он ищет в корзине № 74 и не находит его.

Помните, объекты могут быть помещены в хэш-таблицы способами, которых вы не ожидали. Многие операторы последовательности LINQ используют хэш-таблицы внутри. Не подвергайте объекты опасному изменению при перечислении запроса LINQ, который их возвращает!

Теперь Dictionary<ComparableDictionary, List<String>> используется только один раз в коде, в месте, где должно быть установлено содержимое всех ComparableDictionary коллекций. Таким образом, в соответствии с этими рекомендациями, я думаю, что было бы приемлемо переопределить, GetHashCode как я сделал (полностью основываясь на содержимом словаря).

После этого введения мои вопросы таковы:

1. Я знаю, что производительность SortedDictionary очень низкая по сравнению с Dictionary (и у меня могут быть сотни экземпляров объекта). Единственная причина использования SortedDictionary заключается в том, что я могу выполнять сравнение равенства на основе содержимого словаря, независимо от порядка вставки. Есть ли лучший способ достичь этого требования равенства без использования SortedDictionary ?
2. Является ли моя реализация GetHashCode приемлемой на основе требований? Несмотря на то, что он основан на изменяемом содержимом, я не думаю, что это должно представлять какой-либо риск, поскольку единственное место, где он используется (я думаю), — это после того, как содержимое было установлено.

Примечание: хотя я настраивал их с помощью Dictionary или SortedDictionary , я не привязан к этим типам коллекций. Основная потребность — это коллекция, которая может хранить пары значений и удовлетворять требованиям равенства и хеширования, определенным выше.

Ваша GetHashCode реализация выглядит приемлемой для меня, но я бы сделал это не так.

Это то, что я бы сделал:

• Используйте композицию, а не наследование. Помимо всего прочего, наследование становится нечетным с точки зрения равенства
• Используйте Dictionary<TKey, TValue> переменную внутри словаря
• Реализовать GetHashCode , взяв XOR из отдельных хэш-кодов пары ключ / значение
• Реализуйте равенство, проверяя, совпадают ли размеры, затем проверяя каждый ключ в «this», чтобы увидеть, совпадает ли его значение в другом словаре.

Итак, что-то вроде этого:

 public sealed class EquatableDictionary<TKey, TValue>
    : IDictionary<TKey, TValue>, IEquatable<ComparableDictionary<TKey, TValue>>
{
    private readonly Dictionary<TKey, TValue> dictionary;

    public override bool Equals(object other)
    {
        return Equals(other as ComparableDictionary<TKey, TValue>);
    }

    public bool Equals(ComparableDictionary<TKey, TValue> other)
    {
        if (ReferenceEquals(other, null))
        {
            return false;
        }
        if (Count != other.Count)
        {
            return false;
        }
        foreach (var pair in this)
        {
            var otherValue;
            if (!other.TryGetValue(pair.Key, out otherValue))
            {
                return false;
            }
            if (!EqualityComparer<TValue>.Default.Equals(pair.Value,
                                                         otherValue))
            {
                return false;
            }
        }
        return true;
    }

    public override int GetHashCode()
    {
        int hash = 0;
        foreach (var pair in this)
        {
            int miniHash = 17;
            miniHash = miniHash * 31   
                   EqualityComparer<TKey>.Default.GetHashCode(pair.Key);
            miniHash = miniHash * 31   
                   EqualityComparer<Value>.Default.GetHashCode(pair.Value);
            hash ^= miniHash;
        }
        return hash;
    }

    // Implementation of IDictionary<,> which just delegates to the dictionary
}
  

Также обратите внимание, что я не могу вспомнить, EqualityComparer<T>.Default.GetHashCode справляется ли он с нулевыми значениями — у меня есть подозрение, что это так, возвращая 0 вместо null. Хотя стоит проверить 🙂