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

Question

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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