Why does the Java HashMap copy constructor affect floating point precision?

Question

I had some code calculating a linear combination on maps of floats, and ran into an interesting side-effect of using the copy constructor.

If I calculate the linear combination of values in two maps and compare it with the linear combination calculated using the values in two copies of those maps, the calculations actually have slightly different (in the neighborhood of 10^-7) results due to what appears to be floating point precision.

Why does this happen?

Here's some sample code:

import java.util.*;

public class WTF {
    public static void main(String[] args) {
        Random rand = new Random();

        for (int c = 0; c < 1000; c++) {
            Map<String, Float> weights = new HashMap<String, Float>();
            Map<String, Float> values = new HashMap<String, Float>();

            for (int j = 0; j < 10; j++) {
                weights.put("sig" + j, Float.valueOf(rand.nextFloat()));
                values.put("sig" + j, Float.valueOf(rand.nextFloat()));
            }

            Map<String, Float> weightsCopy = new HashMap<String, Float>(weights);
            Map<String, Float> valuesCopy = new HashMap<String, Float>(values);

            float score1 = getScore(weights, values);
            float score2 = getScore(weightsCopy, valuesCopy);

            if (score1 != score2) {
                System.out.println(score1-score2);
            }
        }
    }

    public static float getScore(Map<String, Float> weights, Map<String, Float> values) {
        float score = 0.0f;
        for (String name : weights.keySet()) {
            Float weight = weights.get(name);
            Float value = values.get(name);
            score += weight.floatValue() * value.floatValue();
        }
        return score;
    }
}

UPDATE:

The same issue also applies to the putAll operation. Using that to "copy" a HashMap results in the same floating point precision issues.

Answer 1

The order in the map is changing, causing the operations to be run in a different order. An example of the output changing for simple computation (note the flipped d and e):

class WTF {
    public static void main(String[] args) {
        final float a = 0.42890447f * 0.37233013f;
        final float b = 0.2648958f * 0.05867535f;
        final float c = 0.8928169f * 0.7546882f;
        final float d = 0.0039135218f * 0.59395087f;
        final float e = 0.9114683f * 0.33522367f;

        System.out.println(a + b + c + d + e);
        System.out.println(a + b + c + e + d);
    }
}

Answer 2

The iteration order is changing from the original maps to the copies, since it's rebuilding the hash table (probably with a different size).

The difference in the rounding comes from the fact that * and + on floats aren't quite commutative/associative, and you'll get different rounding errors depending on whether you do a * (b * c) or (a * c) * b or (a * b) * c. Since the ordering of entries and keys is changing between the originals and the copies, you're getting tiny rounding differences in the results.

If you use LinkedHashMap instead of HashMap to ensure preserved iteration order, you should get the exact same results each time. (I've confirmed this on my machine.)