I wish to create a HashSet
for real numbers (at present Double
s) 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.
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.
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.
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.
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.
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
, andz
, ifx.equals(y)
returnstrue
andy.equals(z)
returnstrue
, thenx.equals(z)
should returntrue
.
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 thehashCode
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
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With