3

I want to use Double (or Float) as keys in a Hashmap

Map<Double, String> map = new HashMap<Double, String>()
map.put(1.0, "one");
System.out.println(map.containsKey(Math.tan(Math.PI / 4)));

and this returns false.

if I were comparing these two numbers I would have done something like this

final double EPSILON = 1e-6;
Math.abs(1.0 - Math.tan(Math.PI / 4)) < EPSILON

But since Hashmap would use hashcode it breaks things for me.

I thought to implement a roundKey function that rounds to some multiple of EPSILON before using it as a key

map.put(roundKey(1.0), "one")
map.containsKey(roundKey(Math.tan(Math.PI / 4)))
  • is there a better way ?
  • what is the right way to implement this roundKey
2
  • 2
    possible duplicate of Double in HashMap
    – Joe
    Mar 25, 2014 at 10:03
  • 1
    It may be quite a thing to implement a good roundKey function without annoying "1.00000000001" and "0.999999999999": rounding float you have a float. May be you would like to implement floatToKey function which returns int? Mar 25, 2014 at 10:04

2 Answers 2

4

If you know what rounding is appropriate, you can use that. e.g. if you need to round to cents, you can round to two decimal places.

However, for the example above discrete rounding to a fixed precision might not be appropriate. e.g. if you round to 6 decimal places, 1.4999e-6 and 1.5001e-6 will not match as one rounds up and the other down even though the difference is << 1e-6.

In that situation the closest you can do is to use a NavigableMap

NavigableMap<Double, String> map = new TreeMap<>();

double x = ....;
double error = 1e-6;

NavigableMap<Double, String> map2 = map.subMap(x - error, x + error);

or you can use

Map.Entry<Double, String> higher = map.higherEntry(x);
Map.Entry<Double, String> lower = map.lowerEntry(x);
Map.Entry<Double, String> entry = null;
if (higher == null)
    entry = lower;
else if (lower == null)
    entry = higher;
else if (Math.abs(lower.getKey() - x) < Math.abs(higher.getkey() - x))
    entry = lower;
else
    entry = higher;
// entry is the closest match.
if (entry != null && Math.abs(entry - x) < error) {
    // found the closest entry within the error
}

This will find all the entries within a continuous range.

1
  • @mzzzzb note: NavigableMap can find multiple keys within range, but if it is empty, there was none. Mar 25, 2014 at 10:24
0

Best way is to not use floating point numbers as keys, as they are (as you discovered) not going to compare.
Kludgy "solutions" like calling them identical if they're within a certain range of each other only lead to problems later, as you're either going to have to stretch the filter or make it more strict in time, both leading to potential problems with existing code, and/or people will forget how things were supposed to work.
Of course in some applications you want to do that, but as a key for looking up something? No. You're probably better off using angles in degrees, and as integers, as the keys here. If you need greater precision than 1 degree, use the angle in e.g. tenth of degrees by storing a number of 0 through 3600.
That will give you reliable behaviour of your Map while retaining the data you're planning to store.

3
  • The key issue is having a value which is almost but not exactly the same and you still want it to match. Using integer instead won't change that. If you have 0 to 3600 but you want 1234 to match 1235 the problem is the same. Mar 25, 2014 at 10:32
  • @PeterLawrey true, but that's assuming the reverse of what you normally want for a key.
    – jwenting
    Mar 25, 2014 at 12:47
  • 1
    @jwenting Peter's point is that storing integer keys is not going to solve the problem, if those integers are the result of floating point computation. Either you're calculating exactly the same float value on store and lookup (in which case storing float keys would work), or you're not (in which case integers are just as kludgy and imperfect a solution). 44.4999999999 and 44.50000000001 are going to hash differently once rounded to int, for all that those are within floating point error of each other.
    – Sneftel
    Mar 25, 2014 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.