Bug ID: JDK-8244572 AbstractMap, HashMap, TreeMap, and unmodifiable Maps' equals() methods operate in the wrong direction

Type: Bug
Component: core-libs
Sub-Component: java.util:collections

Priority: P4
Status: Open
Resolution: Unresolved

Submitted: 2020-05-07
Updated: 2023-10-23

Other
tbdUnresolved

AbstractMap.equals() is implemented incorrectly, which can lead to incorrect results if called on a Map with a different membership contract. Since HashMap, TreeMap, and the unmodifiable maps from Map.of et. al. inherit AbstractMap.equals, they all have this problem too.

Example:

var umap = Map.of("a", 0, "A", 0);
var hash = new HashMap<>(umap)
var tree = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER)
tree.put("a", 0);
tree.put("x", 0);

We now have:

umap ==> {a=0, A=0}
hash ==> {a=0, A=0}
tree ==> {a=0, x=0}

However:

hash.equals(tree)
==> true     *** !!! ***
tree.equals(hash)
==> false     *** !!! ***
hash.entrySet().equals(tree.entrySet())
==> false
tree.entrySet().equals(hash.entrySet())
==> true

Also:

umap.equals(tree)
==> true     *** !!! ***
tree.equals(umap)
==> false     *** !!! ***
umap.entrySet().equals(tree.entrySet())
==> false
tree.entrySet().equals(umap.entrySet())
==> true

Results above marked with *** !!! *** are incorrect. The 'true' results not so marked are surprising but correct.

(ConcurrentHashMap does not have this problem, because it uses a different algorithm for equals(). This is possibly in order to accommodate the case where there are more than Integer.MAX_VALUE mappings. At such sizes, the size() method is clamped at MAX_VALUE and is thus unreliable.)

Explication: Map.equals is essentially defined in terms of equality of the maps' entrySets. Set.equals is true if the argument is a set, the sets have the same size, and every element of the argument is contained in this set. (It also says "(or equivalently, every member of this set is contained in the specified set)" which is not equivalent.) Disregarding the incorrect "equivalently" comment, this essentially delegates to containsAll(). Set.containsAll is true if every element of the argument is contained in this set, using this set's membership contract. AbstractSet.equals does some preliminary instanceof and size tests and if they're met, it calls this.containsAll. This is inherited from AbstractCollection, which iterates the argument while calling this.contains. Thus, hash.entrySet().equals(tree.entrySet()) returns false, as expected. However, AbstractMap.equals checks that the sizes are equals and then iterates this map, essentially doing contains-checks on the argument map. Since the case-insensitive TreeMap's contains semantics are used, both "a" and "A" keys appear to be contained in the TreeMap, and its "x" key is ignored. The method thus returns true, which is incorrect regardless of any questions about whose membership contract is in play. The reason tree.entrySet().equals(hash.entrySet()) returns true has to do with the Set.equals contract. If we have var hset = new HashSet<>(Arrays.asList("a", "A")) var tset = new TreeSet<>(String.CASE_INSENSITIVE_ORDER) tset.addAll(Arrays.asList("a", "x")) hset.equals(tset) ==> false tset.equals(hset) ==> true This is counterintuitive but meets the letter of the contract. A similar phenomenon occurs when comparing the entrysets. This is quite surprising, but it isn't necessarily a bug! Note that if the roles of the maps in AbstractMap.equals are reversed, we will have hash.equals(tree) ==> false tree.equals(hash) ==> true which is again surprising, but is consistent with the specification and the comparison of the corresponding entrysets. ******* Another note of interest is that the AbstractMap::equals method issues get() calls on its argument map. This has the side effect of changing the order of an access-ordered LinkedHashMap. Example: (added 2023-10-23) var map = new LinkedHashMap<String, Integer>(16, 0.75f, true) map.put("a", 1) map.put("b", 2) map.put("c", 3) var map2 = new LinkedHashMap<>(map) map2.put("b", 999) map map ==> {a=1, b=2, c=3} map2 map2 ==> {a=1, b=999, c=3} map2.equals(map) ==> false map map ==> {c=3, a=1, b=2}

23-10-2023