Генерация идентичных хэш-кодов для примерно одинаковых чисел

Question

Я создаю приложение в C # 3.5, которое использует API AutoCAD для чтения 2D-чертежа AutoCAD, вносит изменения в чертеж с использованием определенной бизнес-логики, а затем корректирует его обратно в AutoCAD. Из-за природы логики форму рисунка необходимо перестроить, например, прямоугольник состоит из 4 соединительных прямых линий.

Я создаю эти фигуры, используя начальную и конечную координаты каждой линии из AutoCAD, но некоторые координаты не совсем совпадают. Например, одна точка может иметь значение 0,69912839 (на одной оси), но линия, начинающаяся с той же точки, может быть 0,69990821. Они указаны в мм, поэтому расстояние составляет минуты (0,00078 мм!)

Я создал свой собственный класс (назовите его MyPoint, похожий на PointF), потому что мне нужно было добавить к нему дополнительную логику. В этом классе я создал метод, который принимает две двойные и возвращает истину или ложь в зависимости от того, находятся ли две точки в пределах 0,001 мм друг от друга. Затем я переопределил метод Equals, операторы == и! =, Чтобы я мог сделать (point1 == point2 или point1.Equals (point2)), который проверяет, все ли оси находятся в пределах 0,001 мм друг от друга - если они оцените это как одно и то же.

Это нормально и блестяще работает. Теперь мне нужно проверить коллекцию этих точечных классов, чтобы избавиться от всех дубликатов, поэтому я использую метод Distinct () LINQ в своей коллекции. Однако этот метод использует GetHashcode (), а не Equals (), чтобы определить, равны ли экземпляры. Итак, я переопределил GetHashcode (), который использует GetHashcode двойного класса.

Но вышеприведенный пример терпит неудачу, потому что, очевидно, они имеют разные значения и, следовательно, генерируют разные хеш-коды. Есть ли способ, что два числа, которые находятся в пределах 0,001 друг от друга, могут генерировать один и тот же хэш-код? (Обратите внимание, что числа не знают друг о друге, так как GetHashcode вызывается отдельно для разных экземпляров классов.) Я пробовал множество способов, которые работают для некоторых примеров, но не для других.

Одним из примеров является усечение числа до 3dp (умножение его на 10 ^ 3, затем усечение его) и создание хеш-кода для результата - который работает для приведенного выше примера (699 == 699.) Но это не работает для 0,69990821 и 0,70000120 (699! = 700). Я пробовал округление, которое работает для второго набора чисел (0,700 == 0,700), но не для первого (0,699! = 0,700.) Я даже пытался обрезать число в 3dp, затем корректируем его до следующего четного числа, которое работает для обоих предыдущих примеров, но не для 12.9809 и 12.9818 (12980! = 12982.)

Есть ли другой способ или я должен удалить переопределения Equals, ==,! = И GetHashcode и создать мои собственные методы MyPoint.IsEqualTo () и MyPointCollection.Distinct ()?

Answer 1

Я думаю, вы не должны переопределять Equals(), ==, != или GetHashCode()

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

Например, ваш == не может быть транзитивным для него, то есть тогда, если P1 составляет 0,001 мм от P2, P2 составляет 0,001 мм от P3 и P1 составляет 0,002 мм от P3, тогда P1 == P2, P2 == P3 и P1 == P3, а это не то, что вы хотите. В целом все точки равны всем остальным.

Я бы просто использовал отдельный метод для определения, достаточно ли близки точки.

EDIT

С вашим переопределением == теперь вы можете написать код, подобный этому:

if(P1 == P2 && P2 == P3 && P1 != P3)
{
    // Code here gets executed
}

Answer 2

Невозможно написать правильный хэш-код. давайте докажем это: у нас есть 2 балла. var a = point1.GetHashCode (); var b = point2.GetHashCode ();

если a! = B, создайте точку между точкой1 и точкой2. и т. д.

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

Так переутомить, как это:

public override int GetHashCode()
{
    return 0;
}

и реализуй равных тебе.

Answer 3

Было бы проще просто удалить зависимость от метода Distinct. Реализуйте System.Collections.IComparer (или универсальный эквивалент) и используйте простую коллекцию, например список. Затем определите, есть ли элемент в списке с помощью компаратора, и не добавляйте его, если он уже содержится.

Answer 4

Это должно быть более четким объяснением того, что сказали Стек и Паоло.

Предположим, вам удалось написать метод GetHashCode так, как вы хотите.

Тогда для любых точек a и b, независимо от расстояния между ними, a.GetHashCode() == b.GetHashCode().

Доказательство: предположим, a < b. Разделите расстояние между a и b на сегменты меньше 0,001. То есть a0 = a, a1 = a0 + 0.0005, a2 = a1 + 0.0005, и т. Д., Пока не доберетесь до b.

Тогда a.GetHashCode() == a1.GetHashCode() == a2.GetHashCode() == ... == b.GetHashCode().

Answer 5

следует ли мне удалить переопределения Equals, ==,! = И GetHashcode и создать мои собственные методы MyPoint.IsEqualTo () и MyPointCollection.Distinct ()?

Да.

Однако это не обязательно должна быть какая-то совершенно другая структура данных. При проверке дубликата необходимо проверить соседние хеш-коды, например, хэши для (х + 0,001, у), (х, у-0,001) и т. д. Это обеспечивает просто постоянное замедление по сравнению с обычным поиском дедупликации, и это не сложно, так что это может быть путь. (Очевидный момент, но я пока не вижу здесь этого явно.)

Обновление: Чтобы прояснить ситуацию, давайте рассмотрим одномерную версию проблемы. «Точки» - это отдельные числа, х. Мы считаем, что x1 и x2 совпадают, когда abs(x1 - x2) < .001. Теперь мы хотим выяснить, соответствует ли x любому из {x_0, ..., x_n}. X_i хранятся в хеш-таблице, где hash(x) = h(floor(1000*x)) для некоторой функции h (), которая распространяет информацию. Чтобы увидеть, есть ли x в таблице, мы вычисляем hash(x-.001), hash(x) и hash(x+.001), затем проверяем, соответствует ли x любому из x_i в любому из трех сегментов . Любой соответствующий x_i не может быть в другом ведре.

В 2-м варианте есть 9 соседних ведер для проверки (считая середины); в 3-е, 27.

Answer 6

Полагаю, что если вы всегда возвращаете один и тот же хеш (скажем, 0), LinQ попытается сравнить все элементы с equals. В конце концов, хеш полезен, чтобы доказать, что два элемента различны, а не равны.

Но в любом случае я бы порекомендовал вам использовать более подходящие структуры и алгоритмы для этой области, например, деревья Binary Splitting Partition (BSP).

Answer 7

Вот некоторый код, чтобы показать, что я делаю. Каждая пара чисел в «оригинале» должна возвращать одно и то же значение.

int tolerance = 3;
double[] original = new double[] {
0.69912839,
0.69990821,

0.69990821,
0.70000120,

12.980984087,
12.981808908
};
double[] modified = new double[original.Length];

for (int i = 0; i < original.Length; i++)
{
modified[i] = original[i];

/* Begin number adjustment logic */
modified[i] *= Math.Pow(10, tolerance);
modified[i] = Math.Truncate(modified[i]);

if (modified[i] % 2 != 0)
{
modified[i]++;
}
/* End number adjustment logic */

Console.WriteLine(modified[i]);

if (i % 2 != 0)
{
Console.WriteLine(string.Empty);
}
}

Указанный выше метод - это метод "усечь до 3dp, а затем настроить до ближайшего четного" Далее следует метод усечения (замените код между комментариями начала / конца):

/* Begin number adjustment logic */
modified[i] *= Math.Pow(10, tolerance);
modified[i] = Math.Truncate(modified[i]);
/* End number adjustment logic */

Это метод раунда:

/* Begin number adjustment logic */
modified[i] = Math.Round(modified[i], tolerance);
/* End number adjustment logic */