Реализация словаря, в котором эквивалентное содержимое равно и возвращает один и тот же хэш-код независимо от порядка вставки

Question

Мне нужно использовать 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> - основной тип Dictionary используется в качестве ключа для другого Dictionary, и если HashCodes не оцениваются на основе идентичных содержимое, использование 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, я не привязан к этим типам коллекций. Основная потребность - это коллекция, которая может хранить пары значений и удовлетворять требованиям равенства и хеширования, определенным выше.

Answer 1

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

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

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

Так что-то вроде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 со значениями NULL - у меня есть подозрение, что это так, возвращая 0 для NULL.Хотя стоит проверить:)