Java HashMap.hashCode() Not Unique With String Keys And Values

These two maps are different, but their hash codes are the same due to the fact that HashMap sums children hash codes rather than multiplies them and the entries values in this case happen to be perfectly collide with one another.

Just for clarity, HashMap's Map.Entry implementation is HashMap.Node, which creates hash code as:

key.hashCode() ^ value.hashCode()

Here's some code exemplifying the problem:

Map<String, String> mapOne = new HashMap<>();
mapOne.put("first", "valueB");
mapOne.put("second", "valueB");

Map<String, String> mapTwo = new HashMap<>();
mapTwo.put("first", "valueA");
mapTwo.put("second", "valueC");

System.out.println("\"first\".hashCode(): " + "first".hashCode());
System.out.println("\"second\".hashCode(): " + "second".hashCode());
System.out.println("\"valueA\".hashCode(): " + "valueA".hashCode());
System.out.println("\"valueB\".hashCode(): " + "valueB".hashCode());
System.out.println("\"valueC\".hashCode(): " + "valueC".hashCode());

System.out.println("Simulated mapOne hashcode math:");
int firstValueBHashCode = ("first".hashCode() ^ "valueB".hashCode());
System.out.println("Map one's first ^ valueB hashcode: " + firstValueBHashCode);
int secondValueBHashCode = ("second".hashCode() ^ "valueB".hashCode());
System.out.println("Map one's second ^ valueB hashcode: " + secondValueBHashCode);
int mapOneHashCode = firstValueBHashCode + secondValueBHashCode;
System.out.println("Map one's hashcode, (first ^ valueB) + (second ^ valueB): " + mapOneHashCode);

System.out.println("Simulated mapTwo hashcode math:");
int firstValueAHashCode = ("first".hashCode() ^ "valueA".hashCode());
System.out.println("Map two's first ^ valueA hashcode: " + firstValueAHashCode);
int secondValueCHashCode = ("second".hashCode() ^ "valueC".hashCode());
System.out.println("Map two's second ^ valueC hashcode: " + secondValueCHashCode);
int mapTwoHashCode = firstValueAHashCode + secondValueCHashCode;
System.out.println("Map two's hashcode, (first ^ valueA) + (second ^ valueB): " + mapTwoHashCode);

System.out.println("Final result:");
System.out.println("Map one's hashcode, (first ^ valueB) + (second ^ valueB): " + mapOneHashCode);
System.out.println("Map two's hashcode, (first ^ valueA) + (second ^ valueB): " + mapTwoHashCode);
System.out.println("Map hashcodes match: " + (mapOneHashCode == mapTwoHashCode));

Output from above looks like this:

"first".hashCode(): 97440432
"second".hashCode(): -906279820
"valueA".hashCode(): -823812880
"valueB".hashCode(): -823812879
"valueC".hashCode(): -823812878

Simulated mapOne hash code math:
Map one's first ^ valueB hash code: -886354367
Map one's second ^ valueB hash code: 119462021
Map one's hash code, (first ^ valueB) + (second ^ valueB): -766892346

Simulated mapTwo hash code math:
Map two's first ^ valueA hash code: -886354368
Map two's second ^ valueC hash code: 119462022
Map two's hash code, (first ^ valueA) + (second ^ valueB): -766892346

Final result:
Map one's hash code, (first ^ valueB) + (second ^ valueB): -766892346
Map two's hash code, (first ^ valueA) + (second ^ valueB): -766892346
Map hash codes match: true

To solve this problem, write your own utility function to compute the hash code with a prime number multiplier as generally recommended, like so:

public static <T extends Object, U extends Object> int createMapHashCode(Map<T,U> map) {
    int hashCode = 0;
    for (Map.Entry<T, U> entry : map.entrySet()) {
        if (entry != null) {
            hashCode = (hashCode * 31) + entry.hashCode();
        }
    }
    return hashCode;
}