Есть ли способ получить хеш-код с плавающей точкой с помощью epsilon?
Хорошо известно, что сравнивать поплавки с помощью == обычно ошибка. В классе трехмерных векторов (с плавающими компонентами X, Y, Z), которые я написал, два вектора считаются равными, если их расстояние считается нулевым.
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 и другие специальные значения возможны, но маловероятны, если это важно.
5 ответов
Невозможно предположить, что вы хотите иметь нормальные свойства хэш-кода / равенства:
- Если 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 должны иметь одинаковые хеш-коды и так далее. Поэтому у вас не может быть полезного хеш-кода - он должен быть константой.
Я не думаю, что вы можете иметь хеш-код, который согласуется с вашим методом сравнения, потому что последний не транзитивен: для любых трех векторов 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). Но равенство хеш-кодов всегда транзитивно, поскольку они просто числа.
В этом случае я бы просто создал метод хеш-кода, который вычисляет хеш на основе точных значений координат с плавающей запятой, и упоминал в документации, что он несовместим с равными. Я знаю, что это не совсем решение, но, учитывая, что я не думаю, что реального решения существует, лучше иметь нетривиальный хеш-код, чем просто 0.
Боюсь, что это не в общем случае. Эскиз доказательства выглядит так:
Возьмите любые два числа a и b. Пусть разница между ними будет d. Затем, если вы создаете числа d / epsilon с шагом epsilon между ними, каждый шаг должен быть "равен" предыдущему шагу, который по семантике хэш-кода имеет тот же хеш-код. Поэтому все числа должны иметь одинаковый хэш-код.
Вы можете решить эту проблему, только если добавите какое-то другое ограничение.
Кроме того, ваше определение Equals также неверно, так как может быть верно, что a.Equals(b) и b.Equals(c), но не a.Equals(c), что неверно для equals. Это известно как нарушение свойства транзитивности.
Что я могу сделать тогда?
Решение зависит от того, для чего вы используете хеш. Одним из решений будет введение концептуальной сетки. Измените equals и hashcode, чтобы два числа были равны, если в одном и том же кубе сетки, округляя до постоянного числа десятичных разрядов, затем получая equals и hashcode для округленного числа. Если значение близко к нулю является важным случаем, добавьте смещение epsilon/2 перед округлением, чтобы ноль был центром куба. Это правильно, но вы можете иметь два числа произвольно близко друг к другу (в пределах числа с плавающей точкой), не будучи равными. Так что для некоторых приложений это будет хорошо, для других - нет. Это похоже на идею от mghie.
Все правы...
ОДНАКО, что часто делается, это немного расширить концепцию хэширования. Рассмотрим раздел вашего трехмерного пространства с прямоугольниками со стороной >> epsilon.
Хеш точки - это поле, к которому он принадлежит. Когда вы хотите найти точку, вы проверяете ее не с соответствующим полем (как вы бы сделали для обычного хэша), а также с соседними полями. В 3d вы должны получить максимум 8 коробок.
Какой бы метод вы ни использовали, у вас будут проблемы, потому что вы поставили что-то, что невозможно решить.
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. Все равные точки будут сравниваться равными по одному из двух значений хеша. Для этого потребуется дважды ввести точку в хеш-таблицу, по одному разу для каждой подпрограммы хеширования.