Uploaded image for project: 'Commons Geometry'
  1. Commons Geometry
  2. GEOMETRY-162

Hash collision for vectors symmetrical about coordinate hyperplanes

    XMLWordPrintableJSON

Details

    • Bug
    • Status: Open
    • Minor
    • Resolution: Unresolved
    • None
    • None
    • euclidean2D, euclidean3D

    Description

      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.

      Examples

      The following examples illustrate the problem and can be easily reproduced.

      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 

      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 

      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 

      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;
          result = (int) (temp ^ (temp >>> 32));
          temp = Double.doubleToLongBits;
          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. 

      Attachments

        Activity

          People

            Unassigned Unassigned
            ivanshuba Ivan Shuba
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

              Created:
              Updated: