Как реализовать приближенное геометрическое равенство, используя equals () и hashCode ()

Question

Я хотел бы реализовать некоторые геометрические алгоритмы с числовой устойчивостью.

Для этого используется общесистемное delta для геометрического равенства. equals() для точек реализуется с помощью вычисления расстояния с использованием delta для приблизительного равенства.

Я бы хотел использовать обычные java-коллекции, например, Set. Но я не могу придумать разумную реализацию hashCode().

Я предполагаю, что реализация для эффективного использования HashSet приведет к разделению пространства с "мягкими" границами. Точки с расстоянием менее delta до границы раздела должны быть в состоянии классифицироваться в восьми (для 3D) смежных областях одновременно. Точки, достаточно близкие для того, чтобы считаться равными с точки зрения их расстояния, но лежащие по разные стороны перегородки, в противном случае были бы «неправильно классифицированы».

Это то, чего я не могу понять. hashCode() - это все равно, что складывать предметы в ведра с одним предметом, заканчивающимся в одном ведре, в то время как мне нужно было бы поместить их до восьми.

Каким было бы разумное решение? Я злоупотребляю целью hashCode()? И что было бы наиболее разумным решением при использовании hashCode():)

РЕДАКТИРОВАТЬ: Спасибо, у меня была интуиция, что с этой идеей было что-то не так, но я не мог понять, что с ней. Вы сделали это очень ясно

Пожалуйста, позвольте мне расширить мой вопрос: если я в порядке с более медленной операцией HashSet (которая не является showtopper), я мог бы получить hashCode() return 1, поскольку в моем случае нет правильной реализации, какие бы ужасные последствия были (это условия геометрических вычислений), если бы я реализовал equals(), отбросив требование транзитивности?

РЕДАКТИРОВАТЬ Я нашел этот пост , освещающий проблемы с отсутствующей транзитивностью и и этот пост , который тесно связан с этим.

Answer 1

hashCode() может быть равным для un- equals() объектов. Так что, действительно, ведро, вероятно, просто отлично. Например, если вы просто используете некоторую хеш-функцию ближайшей точки «сетки», где вы можете определить эту сетку так, как вы хотите, она будет работать как хеш-функция, если вы будете последовательно и правильно определять округление.

Однако вы не получите правильное представление о equals() из вашего первого определения. Если A и B, а также B и C находятся в дельте друг от друга, это не означает, что A и C находятся. Транзитивность не держится.

Вы можете определить equals() в терминах группирования. Это может дать немного неожиданные результаты, если точки близко, но по другую сторону линии не равны.

Answer 2

Это принципиально невозможно.

equals() / hashCode() равенство на основе может быть определено только для математических отношений эквивалентности , которые подчиняются трем правилам:

• а ~ а.(Рефлексивность)
• если a ~ b, то b ~ a.(Симметрия)
• если a ~ b и b ~ c, то a ~ c.(Транзитивность)

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

Answer 3

Я бы рекомендовал против всего этого подхода. Во-первых, это нарушит переходное свойство equals. (Если delta == 0,1, то 1 == 1.1 и 1.1 == 1.2, но 1! = 1.2.) Ни одна реализация хеш-кода не исправит это. Это также может испортить структуру коллекций в целом.