Creating a HashSet for Doubles

Question

I wish to create a HashSet for real numbers (at present Doubles) using a defined tolerance (epsilon), (cf Assert.assertEquals(double, double, double)
Since using Double.equals() only works for exact equality and Double is a final class I can't use it. My initial idea is to extend HashSet (e.g. to DoubleHashSet), with a setEpsilon(double) method and create a new class ComparableDouble where equals() uses this value from DoubleHashSet. However I'd like to check whether there are existing solutions already and existing F/OSS libraries.

(In the future I shall want to extend this to tuples of real numbers - e.g. rectangles and cubes - so a generic approach is preferable

NOTE: @NPE has suggested it's impossible. Unfortunately I suspect this is formally correct :-) So I'm wondering if there are approximate methods ... Others must have had this problem and solved it approximately. (I already regularly use a tool Real.isEqual(a, b, epsilon) and it's very useful.) I am prepared to accept some infrequent errors of transitivity.

NOTE: I shall use a TreeSet as that solves the problem of "nearly equals()". Later I shall be comparing complexNumbers, rectangles (and more complex objects) and it's really useful to be able to set a limit within which 2 things are equal. There is no simple natural ordering of complexNumbers (perhaps a Cantor approach would work), but we can tell whether they are nearly equal.

Answer 1

There are some fundamental flaws in this approach.

HashSet uses equals() to check two elements for equality. The contract on equals() has the following among its requirements:

It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.

Now consider the following example:

x = 0.0
y = 0.9 * epsilon
z = 1.8 * epsilon

It is clear that your proposed comparison scheme would break the transitivity requirement (x equals y and y equals z, yet x doesn't equal z). In these circumstances, HashSet cannot function correctly.

Furthermore, hashCode() will produce additional challenges, due to the following requirement:

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

The hashCode() requirement can be sidestepped by using a TreeSet instead of HashSet.

Answer 2

What I would do is round the doubles before using them (assuming this is appropriate)

e.g.

public static double roundByFactor(double d, long factor) {
    return (double) Math.round(d * factor) / factor;
}

TDoubleHashSet set = new TDoubleHashSet(); // more efficient than HashSet<Double>
set.add(roundByFactor(1.001, 100));
set.add(roundByFactor(1.005, 100));
set.add(roundByFactor(1.01, 100));
// set has two elements.

You can wrap this behaviour in your own DoubleHashSet. If you want to reserve the original value you can use HashMap or TDoubleDoubleHashMap where the key is the rounded value and the value is the original.

Answer 3

I have implemented @NPE's approach (I have accepted his/her answer so s/he gets the points :-) and give the code here

//Create a comparator:
public class RealComparator implements Comparator<Double> {

    private double epsilon = 0.0d;

    public RealComparator(double eps) {
        this.setEpsilon(eps);
    }

    /**
     * if Math.abs(d0-d1) <= epsilon  
     * return -1 if either arg is null
     */
    public int compare(Double d0, Double d1) {
        if (d0 == null || d1 == null) {
            return -1;
        }
        double delta = Math.abs(d0 - d1);
        if (delta <= epsilon) {
            return 0;
        }
        return (d0 < d1) ? -1 : 1;
    }

    /** set the tolerance
     * negative values are converted to positive
     * @param epsilon
     */
    public void setEpsilon(double epsilon) {
        this.epsilon = Math.abs(epsilon);
    }

and test it

public final static Double ONE = 1.0;
public final static Double THREE = 3.0;

@Test
public void testTreeSet(){
    RealComparator comparator = new RealComparator(0.0);
    Set<Double> set = new TreeSet<Double>(comparator);
    set.add(ONE);
    set.add(ONE);
    set.add(THREE);
    Assert.assertEquals(2, set.size());
}
@Test
public void testTreeSet1(){
    RealComparator comparator = new RealComparator(0.0);
    Set<Double> set = new TreeSet<Double>(comparator);
    set.add(ONE);
    set.add(ONE-0.001);
    set.add(THREE);
    Assert.assertEquals(3, set.size());
}
@Test
public void testTreeSet2(){
    RealComparator comparator = new RealComparator(0.01);
    Set<Double> set = new TreeSet<Double>(comparator);
    set.add(ONE);
    set.add(ONE - 0.001);
    set.add(THREE);
    Assert.assertEquals(2, set.size());
}
@Test
public void testTreeSet3(){
    RealComparator comparator = new RealComparator(0.01);
    Set<Double> set = new TreeSet<Double>(comparator);
    set.add(ONE - 0.001);
    set.add(ONE);
    set.add(THREE);
    Assert.assertEquals(2, set.size());
}