Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Creating a HashSet for Doubles

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.

like image 748
peter.murray.rust Avatar asked Apr 14 '13 09:04

peter.murray.rust


People also ask

How do I allow duplicates in HashSet?

Duplicates: HashSet doesn't allow duplicate values. HashMap stores key, value pairs and it does not allow duplicate keys. If the key is duplicate then the old key is replaced with the new value.

How HashSet detect duplicates?

By using HashSet, a general-purpose Set implementation, we can find duplicates in O(n) time. All you need to do is iterate over an array using advanced for loop and insert every element into HashSet. Since it allows only unique elements, add() method will fail and return false when you try to add duplicates.

What happens if you add a duplicate to a HashSet?

HashSet doesn't allow duplicates. If you try to add a duplicate element in HashSet, the old value would be overwritten. HashSet allows null values, however if you insert more than one nulls, it would override the previous null value. HashSet is non-synchronized.

Can we add duplicate objects in set?

We can add duplicate non-final objects by overriding HashCode and equals method. In HashCode() you can return same hashcode in case of same parameters. The output will be 1.


1 Answers

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.

like image 123
NPE Avatar answered Sep 30 '22 12:09

NPE