poor implementation of hashCode of LinkedHashMap #2733
Comments
|
Thank you for your finding and the minimal example! What do you mean by "Java implementation is right"? Do you suggest to use the hash algorithm used by Java's LinkedHashMap? |
|
I mean Java native hashCode implementation for HashMap returns different hashcodes for that example. The problem I faced is that I had a grid modeled with a linkedhashmap. The grid had always the same elements BUT in different positions. The current implementation returns always the same hashCode no matter the positions of the elements. Since I was storing the grids in a Set and all of them had the same hashcode, the performance was really bad... |
|
I made a stab at this, but I'm not sure if its the right way to "fix it". |
|
@jarlah You can not change hashCode without changing equals. The result of these two methods must agree. The contract for these two methods is defined in java.lang.Object. So, always change them both, and you are good. I believe, there is a contradiction between the API of the interface Traversable and the classes that implement it and their unit tests. (?) Interface Traversable states that hashCode and equals is different for collections with predictable iteration order and for collections with arbitrary iteration order. However, TreeMap and LinkedHashMap implement hashCode and equals for unordered collections: Maybe I am just confused about the Javadoc in Traversable? TreeMap.isOrdered() returns true, TreeMap.isSequential() returns false. I believe this makes TreeMap a collection with predictable iteration sequence. LinkedHashMap.isOrdered() returns false, LinkedHashMap.isSequential() returns true. I believe this makes LinkedHashMap a collection with predictable iteration sequence. |
Yes, of course. What i did was just to make a PR hightlighting how easy it was to change the behaviour. But it totally is not ready. |
|
@jarlah What do you think about the Javadoc in Traversable.hashCode and Traversable.equals? |
|
I think vavr is making itself a disservice by redifining such concepts. But i guess its ok, because vavrs collections will only be used and compapred to with vavr collections. I see your point @wrandelshofer that the doc talks about predictable iteration order and arbitrary iteration order. But i cannot say what it means. Or if you are right. What i can say however is that to fix my equals in my PR i would need to sort both collections and compare the two sorted collections. I dont think thats very effective, and im worried about the performance impliciations. |
|
Yes, I can not tell whether it is correct or incorrect. I would err on the side of the implementation, and assume that the hashValue/equals depends on the collection types Set/Seq/Map. I - personally - would not go in the direction of your fix. It is convenient to be able to check sets and maps for equality/hashCode regardless of their iteration order. But I am not the designer. So, it is a viable design direction, of course. |
For me - ideally vavr Collections can be swapped in and out with java.util Collections. The only difference being that the vavr Collections have persistent mutability, and have no API methods that can throw UnsupportedOperationException. |
|
I understand that the hash is computed via the underlying state, but - to me - the confusion arises in how those two hash maps - {"a": 1, "b": 2} and {"a": 2, "b": 1} - have the same underlying state? Wouldn't the keys and the values be associated with each other, regardless of any ordering concerns? In that case, why wouldn't the hash code calculation take the key-value relation into consideration? Playing with this a little because I'm bored and stalling on my "real" work, I can confirm that the only thing that seems to matter for the hash code is that all the keys and values are included - ordering of the keys doesn't matter. So {"b": 1, "a": 2} would have the same hash code as the other examples. This also isn't an edge case for a 2-pair map; I wasn't expecting that it was, but I did it with 3 pairs with the same results. It also doesn't appear to be a fluke where those permutations just happen to generate the same hash code - which would be unlikely, but there's no reason it would be impossible. It's acceptable - and even expected - that random states for a given object will have the same hash code, even if they're not equal; the important thing is that they have the same hash code when they are equal. So you could always return 1 as your hash code and you'd meet the contract requirements. You'd just have horrible performance if you used it as a key in a hash map. (And there's probably other places that use the hash code, but that's the obvious one at the moment.) From @wrandelshofer:
It's a little more subtle than this; in this particular case, where it appears that As an aside, while |
|
I have an idea how to approach this, PoC: #2803 |
|
I looked at your Pull Request #2803. But this should be |
|
Here's the explanation: #2803 (comment) |
|
I see your explanation. The explanation is fine. However, LinkedHashMap extends from Traversable. And Traversable defines the contract of the hashCode() Method. vavr/src/main/java/io/vavr/collection/Traversable.java Lines 686 to 698 in 5ba70a2 Maybe, in your pull request, you should change the contract in Traversable. Because LinkedHashMap does not fulfill the contract. |
|
Ok, that's a great point - I did not realize that |
|
Or, alternatively, move the contract for equals/hashCode out of Traversable into more specific interfaces. In the Java JDK API, the Iterable and Collection interfaces do not define equals/hashCode. This happens only in more specific interfaces: in the List, Map, Set interfaces. |
|
We'll probably need to do both:
|
The current implementation of the hashCode() method for `Tuple2` has a significant flaw that can easily lead to hash collisions, particularly in data structures like `LinkedHashMap`.
```java
LinkedHashMap<String, Integer> m1 = LinkedHashMap.of("a", 1, "b", 2);
LinkedHashMap<String, Integer> m2 = LinkedHashMap.of("a", 2, "b", 1);
System.out.println(m1.hashCode() == m2.hashCode()); // true
```
In this case, _m1_ and _m2_ should ideally produce different hash codes,
but they don't. This is because the current implementation of
`Tuple#hashCode()` simply sums the hash codes of all elements, which can
result in identical hash codes for different tuples.
A potential solution is to apply the XOR (^) operator to the hash codes
of all elements. XOR is order-sensitive, so it would resolve the issue
in the example above, where the order of elements differs between
tuples.
However, XOR has its limitations and is only a suitable solution for
tuples with up to two elements. This is because XOR is a commutative and
associative operation, meaning that the XOR of multiple elements can
still result in rather bad collisions:
```java
Tuple3<Integer, Integer, Integer> t1 = Tuple.of(1, 2, 3);
Tuple3<Integer, Integer, Integer> t2 = Tuple.of(1, 3, 2);
System.out.println(t1.hashCode() == t2.hashCode()); // true
```
The new implementation is not perfect as well:
```java
HashMap<Integer, Integer> hm1 = HashMap.of(0, 1, 1, 2);
HashMap<Integer, Integer> hm2 = HashMap.of(0, 2, 1, 3);
System.out.println(hm1.hashCode() == hm2.hashCode()); // true
```
But it is imperfect in the same way as standard library:
```java
java.util.HashMap<Integer, Integer> jhm1 = new java.util.HashMap<>();
jhm1.put(0, 1);
jhm1.put(1, 2);
java.util.HashMap<Integer, Integer> jhm2 = new java.util.HashMap<>();
jhm2.put(0, 2);
jhm2.put(1, 3);
System.out.println(jhm1.hashCode() == jhm2.hashCode()); // true
```
----
Related: #2733
|
Well, it's slightly more complicated since ordered hashcode breaks equals/hashcode contracts. Yes, this could be fixed by adjusting the |
|
I just noticed that LinkedHashSet also uses vavr/src/main/java/io/vavr/collection/LinkedHashSet.java Lines 966 to 968 in b1ce608 Maybe the most sensible thing would be to change the Javadoc in |
System.out.println(LinkedHashMap.of("a",1, "b",2).hashCode());
System.out.println(LinkedHashMap.of("a",2, "b",1 ).hashCode());
Both maps have the same hashCode and this is wrong. I found this bug while participating in Advent of Code. An algorithm was extremely slow because of that. Java implementations is right
The text was updated successfully, but these errors were encountered: