Preventing Hash Collisions
Articles —> Preventing Hash Collisions
Hashing is an irreversible digestion of data into a data type if uniform length. In Java, hashing of objects occurs via the hashCode method, and is important for storing and accessing objects in data structures (such as a Map or Set).
Because the hashCode method in java returns an int data type, it is limited to only the size of the int: 32-bits of information. Therefore with a large number of objects hash collisions are likely. This being said, even with a small number of objects, if the hashCode method does not return a number that is uniformly distributed across all plausible int values, hash collisions can be inevitable.
Take the following use case: a Line class defined by two end Point's:
Point
/** * Point class based upon an x and y coordinate * @author gcope * */ public class Point { private final int x; private final int y; public Point(int east, int south) { this.x = east; this.y = south; } public int getX(){ return x; } public int getY(){ return y; } @Override public int hashCode() { final int prime = 31; int result = 17; result = prime * result + y; result = prime * result + x; return result; } }
The Line class:
/** * Line class defined by two end Points * @author gcope * */ public class Line { private Point p1; private Point p2; public Line(Point startCell, Point endCell) { this.p1 = startCell; this.p2 = endCell; } @Override public int hashCode() { final int prime = 59; int result = 43; result = prime * result + ((p1 == null) ? 0 : p1.hashCode()); result = prime * result + ((p2 == null) ? 0 : p2.hashCode()); return result; } }
For brevity, accessor and equals methods are omitted, as are comments. Each class defines a simple hashCode method, returning an int value based upon its fields. The danger here of course, comes from hash collisions. A simple example:
Line line1 = new Line(new Point(154, 156), new Point(154, 156));
Line line2 = new Line(new Point(153, 156), new Point(151, 158));
System.out.println(line1.hashCode() + ":" + line2.hashCode());
Both line1 and line2 have the same hashCode: 1429303. In fact, in this particular case the level of collision is extremely high. Consider the test case below, in which 6,250,000 Lines with different endpoints get generated:
public static void main(String[] args) { List<Point> points = new ArrayList<Point>(); for ( int i = 0; i < 50; i++ ){ for ( int j = 0; j < 50; j++ ){ Point c = new Point(i,j); points.add(c); } } System.out.println(points.size() + " points generated"); System.out.println("Testing " + (points.size()*points.size()) + " number of Lines"); Set<Integer> set = new HashSet<Integer>(); int collisions = 0; for ( int i = 0; i < points.size(); i++ ){ for ( int j = 0; j < points.size(); j++ ){ Line r = new Line(points.get(i), points.get(j)); if ( set.contains(r.hashCode() ) ){ collisions++; } set.add(r.hashCode()); } } System.out.println(collisions); } }
The above results in an astounding 6,155,919 collisions!
How might one lower the probability of collisions? A hash can be defined by the fields of a class, but also inter-dependent properties of those fields. In simpler terms, a line has a length, and a line has a slope. What happens if we include these calculations within the hashCode method of the Line class?
slope = (startCell.getY() - endCell.getY()); if ( slope == 0 ){//prevent division by 0 slope = startCell.getX() - endCell.getX(); }else{ slope = slope / (startCell.getX()- endCell.getX()) / slope; } length = Math.sqrt(Math.pow(startCell.getX() - endCell.getX(), 2) + Math.pow(startCell.getY() - endCell.getY(), 2)); .... @Override public int hashCode() { final int prime = 59; int result = 43; result = prime * result + ((p1 == null) ? 0 : p1.hashCode()); long temp; temp = Double.doubleToLongBits(length); result = prime * result + ((int) (temp ^ (temp >> 32))); temp = Double.doubleToLongBits(slope); result = prime * result + ((int) (temp ^ (temp >> 32))); result = prime * result + ((p2 == null) ? 0 : p2.hashCode()); return result; }
With the above changes, there are 870116 collisions: still a lot, but an 85% reduction in hashCode collisions. Something to consider when hashing is an integral part of your application.
There are no comments on this article.