Ivan Shuba created GEOMETRY-162:
-----------------------------------
Summary: Hash collision for vectors symmetrical about coordinate
hyperplanes
Key: GEOMETRY-162
URL: https://issues.apache.org/jira/browse/GEOMETRY-162
Project: Commons Geometry
Issue Type: Bug
Components: euclidean2D, euclidean3D
Reporter: Ivan Shuba
h1. Overview
This issue is related to that the same value of hash code is returned where it
is expected to be different for non-identical instances of `Vector2D` and
`Vector3D` classes.
In particular, for 2D case, if we generate a pair of vectors which are
symmetrical about the X, or Y coordinate axes, then both such vectors will
return same hash code value. For 3D case, the hash code seems to be equal only
if the vectors are symmetrical about YZ plane.
h2. Examples
The following examples illustrate the problem and can be easily reproduced.
h4. The Vector2D case, symmetrical about Y axis
For example, if we have a following pair of collinear `Vector2D` instances:
{{Vector2D a = Vector2D.of(-10.0, 0); //400556032}}
{{Vector2D b = Vector2D.of(+10.0, 0); //400556032}}
Then they both will return a value of 400556032 if the `hashCode()` method is
called.
The same will happen if we make non-collinear pair of symmetrical vectors (
with non-zero value of Y coordinate ):
{{Vector2D a = Vector2D.of(-20.0, 10.0); //-326631424}}
{{Vector2D b = Vector2D.of(+20.0, 10.0); //-326631424}}
h4. The Vector2D case, symmetrical about X axis
The same holds if we consider a pair of vectors symmetrical about X axis
{{Vector2D a = Vector2D.of(10.0, -30.0); //-1251213312}}
{{Vector2D b = Vector2D.of(10.0, +30.0); //-1251213312}}
Even if we generate arbitrary random number to test the issue, the vectors will
still return the same hash code value.
final double ANY = Math.random();
{{int hashA = Vector2D.of(10.0, ANY); }}
{{int hashB = Vector2D.of(10.0, ANY); }}
{{Assertions.assertNotEquals(hashA, hashB); // fails}}
h4. The Vector3D case
For Vector3D class, the issue seems to arise only if the instances are
symmetrical about YZ plane.
{{final double ANY = Math.random();}}
{{final double NEG = -ANY;}}
{{final double POS = +ANY;}}
{{int negX = Vector3D.of(NEG, 0.0, 0.0);}}
{{int posX = Vector3D.of(POS, 0.0, 0.0);}}
int negY = Vector3D.of(0.0, NEG, 0.0);{{int posY = Vector3D.of(0.0, POS, 0.0);}}
{{int negZ = Vector3D.of(0.0, 0.0, NEG);}}
{{int posZ = Vector3D.of(0.0, 0.0, POS);}}
{{Assertions.assertNotEquals(negX, posX); // fails}}
{{Assertions.assertNotEquals(negY, posY); // passes}}
{{Assertions.assertNotEquals(negZ, posZ); // passes}}
h2. Possible solution
To avoid clashes one could use modified version of the `hashCode` method.
Here's one for Vector3D class:
{{@Override}}
{{public int hashCode() {}}
{{ int result;}}
{{ long temp;}}
{{ temp = Double.doubleToLongBits(x);}}
{{ result = (int) (temp ^ (temp >>> 32));}}
{{ temp = Double.doubleToLongBits(y);}}
{{ result = 31 * result + (int) (temp ^ (temp >>> 32));}}
{{ temp = Double.doubleToLongBits(z);}}
{{ result = 31 * result + (int) (temp ^ (temp >>> 32));}}
{{ return result;}}
{{}}}
P.S. I've prepared a couple of simple unit tests in `Vector2DTest` and
`Vector3DTest` classes illustrating the issue.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
