Есть ли способ получить хэш-код поплавка с epsilon?

Хорошо известно, что сравнение float by == обычно является ошибкой. В классе 3D-вектора (с поплавковыми компонентами X, Y, Z) i, два вектора считаются равными, если их расстояние считается равным нулю.

    public override bool Equals(object obj)
    {
        if (obj == null) {
            return false;
        }

        if (GetType () != obj.GetType ()) {
            return false;
        }

        float d = DistSq ((Vec) obj);

        return IsConsideredZero (d);
    }

    public float DistSq(Vec p)
    {
        Vec d = this - p;
        return d.LengthSq ();
    }

    public float LengthSq()
    {
        return X * X + Y * Y + Z * Z;
    }

    private const float VEC_COMPARE_EPSILON_ABS = 1E-05f;
    public static bool IsConsideredZero(float f)
    {
        return Math.Abs (f) < VEC_COMPARE_EPSILON_ABS;
    }

До сих пор все работало нормально. Однако теперь я хочу получить хэш-код вектора. Я вижу, что что-то вроде hash = (int)X^(int)Y^(int)Z обязательно терпит неудачу.

Лучшее, что я мог придумать, было:

    public override int GetHashCode()
    {
        return 0;
    }

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

Ответы

Ответ 1

Невозможно предположить, что вы хотите иметь нормальные свойства hashcode/равенства:

Если X = Y и Y = Z, то X = Z (транзитивность)
Если X = Y, то Y = X (коммутативность)
X = X для всех X (рефлексивность)

Первое правило - проблема - потому что, если каждое значение считается "равным" следующему большему представимому числу, вы получаете все равные числа. Например, предположим, что число считается равным другому, они находятся в пределах 0,1:

0 равно 0,08 0,08 равно 0,16 0,16 равно 0,24

= > 0 равно 0,16 правилом транзитивности = > 0 равно 0,24 правилом транзитивности

(и т.д.)

Если вы игнорируете правило транзитивности, то вы все еще (предположительно) хотите, чтобы "равные" значения имели одинаковые хэш-коды. Это эффективно применяет правило транзитивности - в приведенном выше примере 0 и 0,08 должны иметь равные хэш-коды, как и 0 и 0,16. Поэтому 0 и 0,16 должны иметь равные хэш-коды и т.д. Поэтому у вас не может быть полезного хэш-кода - он должен быть постоянным.

Ответ 2

Я не думаю, что вы можете иметь hashcode, который согласуется с вашим методом сравнения, потому что последний не является транзитивным: для любых трех векторов A, B, C, если A.Equals(B) и B.Equals(C) являются истинными, это может все равно, что A.Equals(C) является ложным. (Представьте себе, если расстояние между A и B равно 6e-6, между B и C 6e-6, а между A и C равно 1,2e-5). Но равенство хэш-кодов всегда транзитивно, так как они являются просто цифрами.

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

Ответ 3

Я боюсь, что это не в общем случае. Эскиз доказательства выглядит следующим образом:

Возьмем любые два числа a и b. Пусть разница между ними равна d. Затем, если вы создаете числа d/epsilon с шагом epsilon между ними, каждый шаг должен быть "равен" предыдущему шагу, который по семантике hashcode имеет один и тот же хэш-код. Таким образом, все числа должны иметь один и тот же хэш-код.

Вы можете решить эту проблему только в том случае, если вы добавите другое ограничение.

В качестве альтернативы, вы также можете определить определение Equals, так как это может быть верно, что a.Equals(b) и b.Equals(c), но не a.Equals(c), что неверно для равных. Это известно как нарушение свойства Transitive.

Что я могу сделать?

Решение зависит от того, для чего вы используете хэш. Одним из решений было бы введение концептуальной сетки. Измените значения equals и hashcode, чтобы два числа были равны, если в одном и том же кубе сетки округлялось до постоянного числа десятичных знаков, а затем принимали равные и хэш-коды на округленное число. Если быть близким к нулю, это важный случай, добавьте смещение epsilon/2 перед округлением, так что нуль является центром куба. Это правильно, но вы можете иметь два числа произвольно близко друг к другу (под пределами float), не будучи равным. Поэтому для некоторых приложений это будет нормально, другие - не будут. Это похоже на идею из mghie.

Ответ 4

Все верны...

ОДНАКО, одна вещь, которая часто делается, заключается в том, чтобы немного расширить понятие хэша. Рассмотрим раздел вашего трехмерного пространства с ящиками со стороной → epsilon.

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

Ответ 5

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

То, что вы хотите, - это 1) равномерно распределенный хеш, такой, что для большинства чисел a и b, где a!= b, тогда a.GetHashCode()!= b.GetHashCode(), но 2), где a == b, затем a.GetHashCode() == b.GetHashCode() должен быть правдой.

Возвращение константы выполняется (2), но не (1).

Вы можете продемонстрировать, что округление на границах 1E-5 и использование этого как хэш нарушает выполнение (1), но нарушает (2). Например, возьмите 1E-5 и 2E-5. Округление будет производить два разных значения хэширования, но они сравнивают равные. Это нарушает ограничение (2) выше. Вы можете легко обобщить это, чтобы доказать, что любое округление числа столкнется с аналогичной проблемой.

Я рекомендую вам выбрать другой подход. Я предполагаю, что основная проблема заключается в определении того, близок ли какой-то момент к точке, которую вы уже имеете. Я рекомендую вкратце делить координатное пространство пополам (где точки вдоль границы (т.е. <= 1E-5 от границы) в обеих половинах). Если вы постепенно разделите свое пространство (подумайте о двоичном дереве), вы можете построить структуру данных, которая быстро вернет результат, который вы хотите, и будет довольно легко построить.

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