C # Как выбрать хэш-код для класса, который нарушает контракт Equals?

Question

У меня есть несколько классов, которые по определенным причинам не соответствуют официальному Equals контракт.В перезаписанном GetHashCode() эти классы просто возвращают 0, поэтому их можно использовать в хэш-карте.

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

Вопрос в том, как выбрать это значение.Должен ли я просто позволить первому классу возвращать 1, следующему классу 2 и так далее?Или я должен попробовать что-то вроде

class SomeClass : SomeInterface {
    public overwrite int GetHashCode() {
        return "SomeClass".GetHashCode();
    }
}

значит, хэш распределяется более равномерно?(Должен ли я сам кэшировать возвращаемое значение или компилятор Microsoft способен оптимизировать это?)

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

Answer 1

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

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

Хеш-таблица - прекрасный пример непредсказуемого поведения, когда вы нарушаете равенство. Например:

//Assume a == b, b == c, but a != c
var T = new Dictionary<YourType, int>()
T[a] = 0
T[c] = 1
return T[b] //0 or 1? who knows!

Другим примером будет Set:

//Assume a == b, b == c, but a != c
var T = new HashSet<YourType>()
T.Add(a)
T.Add(c)
if (T.contains(b)) then T.remove(b)
//surely T can't contain b anymore! I sure hope no one breaks the properties of equality!
if (T.contains(b)) then throw new Exception()

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

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

Answer 2

Если он "нарушает контракт Equals", то я не уверен, что вы должны использовать его в качестве ключа.

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

Использование константной строки не очень поможет - вы получите значения, равномерно распределенные по типам, но это все ...

Answer 3

Мне любопытно, каковы были бы доводы в пользу переопределения GetHashCode() и возвращает постоянное значение.Зачем нарушать идею хэша, а не просто нарушать "контракт" и не переопределять GetHashCode() функционировать вообще и оставить реализацию по умолчанию из Object?

Редактировать

Если то, что вы сделали, заключается в том, что вы можете сопоставлять свои объекты на основе их содержимого, а не ссылки на них, то то, что вы предлагаете, когда разные классы просто используют разные константы, может РАБОТАТЬ, но крайне неэффективно.Что вы хотите сделать, это придумать алгоритм хеширования, который может использовать содержимое вашего класса и выдавать значение, которое уравновешивает скорость с равномерным распределением (это хэширование 101).

Наверное, я не уверен, что вы ищете ... не существует "хорошей" схемы выбора постоянных чисел для этой парадигмы.Одно ничуть не лучше другого.Попробуйте улучшить свои объекты так, чтобы вы создавали настоящий хэш.

Answer 4

Когда происходят коллизии хеша, HashTable / Dictionary вызывает Equals, чтобы найти ключ, который вы ищете. Использование постоянного хеш-кода устраняет преимущество в скорости использования хеша, во-первых, это линейный поиск.

Вы говорите, что метод Equals не был реализован в соответствии с контрактом. Что именно вы имеете в виду под этим? В зависимости от вида нарушения, HashTable или Dictionary будут просто медленными (линейный поиск) или не будут работать вообще.