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
mzzzzb
  • 1,422
  • 19
  • 38
  • 2
    possible duplicate of [Double in HashMap](http://stackoverflow.com/questions/1074781/double-in-hashmap) – Joe Mar 25 '14 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? – Dmitry Bychenko Mar 25 '14 at 10:04

2 Answers2

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.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
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.

jwenting
  • 5,505
  • 2
  • 25
  • 30
  • 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. – Peter Lawrey Mar 25 '14 at 10:32
  • @PeterLawrey true, but that's assuming the reverse of what you normally want for a key. – jwenting Mar 25 '14 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 '14 at 15:50