Here is a reference implementation of Line object, my confusion is from line 40 to line 43, the question is, if two lines are different, but the OR results of slope/intercept happens to be the same, will it have any issues (e.g. treat different lines the same because of the same hash values)? Since I think same hash value means the same Line.
If the current implementation for hash value do have the issue I mentioned, appreciate if anyone could help to provide some insights what are good implementation for hash value in my case.
1 public static Line findBestLine(GraphPoint[] points) {
2 Line bestLine = null;
3 HashMap<Line, Integer> line_count = new HashMap<Line, Integer>();
4 for (int i = 0; i < points.length; i++) {
5 for (int j = i + 1; j < points.length; j++) {
6 Line line = new Line(points[i], points[j]);
7 if (!line_count.containsKey(line)) {
8 line_count.put(line, 0);
9 }
10 line_count.put(line, line_count.get(line) + 1);
11 if (bestLine == null ||
12 line_count.get(line) > line_count.get(bestLine)) {
13 bestLine = line;
14 }
15 }
16 }
17 return bestLine;
18 }
19
20 public class Line {
21 private static double epsilon = .0001;
22 public double slope;
23 public double intercept;
24 private boolean infinite_slope = false;
25 public Line(GraphPoint p, GraphPoint q) {
26 if (Math.abs(p.x - q.x) > epsilon) { // if x’s are different
27 slope = (p.y - q.y) / (p.x - q.x); // compute slope
28 intercept = p.y - slope * p.x; // y intercept from y=mx+b
29 } else {
30 infinite_slope = true;
31 intercept = p.x; // x-intercept, since slope is infinite
32 }
33 }
34
35 public boolean isEqual(double a, double b) {
36 return (Math.abs(a - b) < epsilon);
37 }
38
39 @Override
40 public int hashCode() {
41 int sl = (int)(slope * 1000);
42 int in = (int)(intercept * 1000);
43 return sl | in;
44 }
45
46 @Override
47 public boolean equals(Object o) {
48 Line l = (Line) o;
49 if (isEqual(l.slope, slope) && isEqual(l.intercept, intercept)
50 && (infinite_slope == l.infinite_slope)) {
51 return true;
52 }
53 return false;
54 }
55 }
Since I think same hash value means the same Line.
No, it doesn't. This is a common misconception. If two objects have the same hash code, they may be equal - but they don't have to be. You should never treat equal hash codes as proof that two objects are equal.
The hash code used here is definitely poor in various ways, but it is at least valid.
As an extreme example, it's always valid (but almost always unhelpful) to write:
public override int hashCode() {
return 5;
}
That guarantees that objects which are equal will have the same hash code, which is all that's required for correctness. Beyond correctness, ensuring that non-equal objects have different hash codes is a matter of making it efficient to use the type in a hash-based lookup.
See more on this question at Stackoverflow