Словарь C #, который использует .Equals () вместо хеширования

Question

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

В моем случае у меня есть класс PointD, определяющий точку с десятичными X и Y. Из-за того, что десятичные типы немного неточны, создание хеша для этой точки невозможно, так как небольшая ошибка между двумя точками которые по сути одинаковы, вызовут существенную разницу в хеш-значениях.

По сути, я хочу иметь возможность подсчитывать количество очков каждой комбинации x, y. Существует ли механизм для этого, или мне нужно реализовать это самостоятельно?

Answer 1

Будь осторожен. Похоже, вы хотите определить Равные, чтобы значения в пределах определенного допуска считались равными. Если вы сделаете это, Equals не будет транзитивным, но для работы словаря он должен быть транзитивным.

Пример: предположим, что x меньше y в 0.8 раза больше допуска. Они будут считаться равными. Теперь рассмотрим значение z, которое больше y в 0,8 раза больше допуска. Поэтому y и z также равны. Но x и z не равны!

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

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

Answer 2

да, вы можете создать свой собственный IEqualityComparer и передать его в словарь при его создании .... он не использует Equal, но вы можете заставить его делать свой собственный хэш.

Это будет работать немного лучше, если вы хотите сохранить Hash в вашем текущем классе Point.

Answer 3

Если у вас большое количество очков, лучше всего использовать что-то вроде Dictionary<Point, List<PointD>>, превращая каждый PointD в Point. Если значение X таково, что значения в пределах допуска могут округляться до разных значений, сохраните округленную в большую и меньшую сторону версию в Dictionary. При поиске точки, если значение Y таково, что значения в пределах допуска могут округляться до разных значений, ищите оба в таблице.

Обратите внимание, что операции словаря могут возвращать один или два экземпляра List<PointD> (два экземпляра только в случае, когда округление Y было неоднозначным; возможно, что некоторые или все экземпляры PointD в этих списках могут оказаться неэффективными соответствует фактической точке интереса, но количество экземпляров, которые необходимо проверить, должно составлять небольшую долю от общего числа в Dictionary.

Answer 4

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

В моем случае я бы стандартизировал точки, чтобы использовать только определенное количество цифр.Вы можете сделать это с помощью метода Math.Round.Таким образом, вы сохраняете все необходимые свойства вашей комбинации has / равенство.

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

Answer 5

Просто переопределите метод GetHashCode в своем классе PointD, чтобы удовлетворить ваши потребности, не так ли?