Details
-
Bug
-
Resolution: Fixed
-
P4
-
None
-
None
Description
Unlike for other collections, there don't seem to be any fundamental tests for IdentityHashMap. Most basically, there should be tests to ensure that membership in the map is identity-based and not value-based.
For example, consider what should happen if the following (erroneous!) patch is applied to IdentityHashMap.
--- a/src/java.base/share/classes/java/util/IdentityHashMap.java
+++ b/src/java.base/share/classes/java/util/IdentityHashMap.java
@@ -296,7 +296,7 @@ public class IdentityHashMap<K,V>
* Returns index for Object x.
*/
private static int hash(Object x, int length) {
- int h = System.identityHashCode(x);
+ int h = x.hashCode();
// Multiply by -254 to use the hash LSB and to ensure index is even
return ((h << 1) - (h << 8)) & (length - 1);
}
@@ -333,10 +333,10 @@ public class IdentityHashMap<K,V>
int i = hash(k, len);
while (true) {
Object item = tab[i];
- if (item == k)
- return (V) tab[i + 1];
if (item == null)
return null;
+ if (item.equals(k))
+ return (V) tab[i + 1];
i = nextKeyIndex(i, len);
}
}
This patch essentially changes the get() method to look up by value instead of by identity. Normally IDHM works like this:
jshell> record Box(int i) {}
jshell> var box1 = new Box(0)
box1 ==> Box[i=0]
jshell> var box2 = new Box(0)
box2 ==> Box[i=0]
jshell> box1 == box2
$79 ==> false
jshell> box1.equals(box2)
$80 ==> true
jshell> var map = new IdentityHashMap<Box, String>()
map ==> {}
jshell> map.put(box1, "a")
jshell> map.put(box2, "b")
jshell> map
map ==> {Box[i=0]=b, Box[i=0]=a}
jshell> map.get(box1)
$86 ==> "a"
jshell> map.get(box2)
$87 ==> "b"
jshell> map.get(new Box(0))
$88 ==> null
However, with this patch in place, the behavior is as follows:
jshell> record Box(int i) {}
jshell> var box1 = new Box(0)
box1 ==> Box[i=0]
jshell> var box2 = new Box(0)
box2 ==> Box[i=0]
jshell> box1 == box2
$4 ==> false
jshell> box1.equals(box2)
$5 ==> true
jshell> var map = new IdentityHashMap<Box, String>()
map ==> {}
jshell> map.put(box1, "a")
jshell> map.put(box2, "b")
jshell> map
map ==> {Box[i=0]=a, Box[i=0]=b}
jshell> map.get(box1)
$10 ==> "a"
jshell> map.get(box2)
$11 ==> "a"
jshell> map.get(new Box(0))
$12 ==> "a"
This is of course completely incorrect. However, with this patch applied, tiers 1, 2, and 3 of the regression suite don't report any failures at all! Failures do occur in a variety of java/beans/XMLEncoder tests (tier 4) because they apparently do rely on the identity semantics of IdentityHashMap.
Some fundamental tests for IdentityHashMap should be added to test/jdk/java/util/IdentityHashMap, which will put them into the jdk_collections_core test group, which is in tier 1.
For example, consider what should happen if the following (erroneous!) patch is applied to IdentityHashMap.
--- a/src/java.base/share/classes/java/util/IdentityHashMap.java
+++ b/src/java.base/share/classes/java/util/IdentityHashMap.java
@@ -296,7 +296,7 @@ public class IdentityHashMap<K,V>
* Returns index for Object x.
*/
private static int hash(Object x, int length) {
- int h = System.identityHashCode(x);
+ int h = x.hashCode();
// Multiply by -254 to use the hash LSB and to ensure index is even
return ((h << 1) - (h << 8)) & (length - 1);
}
@@ -333,10 +333,10 @@ public class IdentityHashMap<K,V>
int i = hash(k, len);
while (true) {
Object item = tab[i];
- if (item == k)
- return (V) tab[i + 1];
if (item == null)
return null;
+ if (item.equals(k))
+ return (V) tab[i + 1];
i = nextKeyIndex(i, len);
}
}
This patch essentially changes the get() method to look up by value instead of by identity. Normally IDHM works like this:
jshell> record Box(int i) {}
jshell> var box1 = new Box(0)
box1 ==> Box[i=0]
jshell> var box2 = new Box(0)
box2 ==> Box[i=0]
jshell> box1 == box2
$79 ==> false
jshell> box1.equals(box2)
$80 ==> true
jshell> var map = new IdentityHashMap<Box, String>()
map ==> {}
jshell> map.put(box1, "a")
jshell> map.put(box2, "b")
jshell> map
map ==> {Box[i=0]=b, Box[i=0]=a}
jshell> map.get(box1)
$86 ==> "a"
jshell> map.get(box2)
$87 ==> "b"
jshell> map.get(new Box(0))
$88 ==> null
However, with this patch in place, the behavior is as follows:
jshell> record Box(int i) {}
jshell> var box1 = new Box(0)
box1 ==> Box[i=0]
jshell> var box2 = new Box(0)
box2 ==> Box[i=0]
jshell> box1 == box2
$4 ==> false
jshell> box1.equals(box2)
$5 ==> true
jshell> var map = new IdentityHashMap<Box, String>()
map ==> {}
jshell> map.put(box1, "a")
jshell> map.put(box2, "b")
jshell> map
map ==> {Box[i=0]=a, Box[i=0]=b}
jshell> map.get(box1)
$10 ==> "a"
jshell> map.get(box2)
$11 ==> "a"
jshell> map.get(new Box(0))
$12 ==> "a"
This is of course completely incorrect. However, with this patch applied, tiers 1, 2, and 3 of the regression suite don't report any failures at all! Failures do occur in a variety of java/beans/XMLEncoder tests (tier 4) because they apparently do rely on the identity semantics of IdentityHashMap.
Some fundamental tests for IdentityHashMap should be added to test/jdk/java/util/IdentityHashMap, which will put them into the jdk_collections_core test group, which is in tier 1.
Attachments
Issue Links
- relates to
-
JDK-8178355 IdentityHashMap uses identity-based comparison for values everywhere except remove(K,V) and replace(K,V,V)
- Closed