StackOverflowError on HashMap.hashCode() due to self reference
Hi everyone, I'm sure somebody has seen this stack overflow before. My question is: is it expected (which should be documented to warn people not to do this), or is it considered a bug (which should be fixed)? Example: https://gist.github.com/rednaxelafx/930f8979473185cfc0a0 import java.util.*; public class HashMapStackOverflow { public static void main(String[] args) throws Exception { HashMap<String, Object> map = new HashMap<>(); map.put("self", map); System.out.println(map.hashCode()); } } $ ~/sdk/jdk1.8.0/Contents/Home/bin/java HashMapStackOverflow Exception in thread "main" java.lang.StackOverflowError at java.util.AbstractMap.hashCode(AbstractMap.java:505) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) ... This will cause a stack overflow because HashMap.hashCode() is inherited from AbstractMap, which sums the hash code of each entry, while one of the entries is itself so it goes recursive. Thanks, Kris
IMHO, this doesn't warrant any special wording -- if someone hits this, I think it's fairly evident what the issue is. You can get the same problem with adding an ArrayList to itself and calling hashCode(). On Fri, Jul 17, 2015 at 2:45 PM, Krystal Mok <rednaxelafx@gmail.com> wrote:
Hi everyone,
I'm sure somebody has seen this stack overflow before. My question is: is it expected (which should be documented to warn people not to do this), or is it considered a bug (which should be fixed)?
Example: https://gist.github.com/rednaxelafx/930f8979473185cfc0a0
import java.util.*;
public class HashMapStackOverflow { public static void main(String[] args) throws Exception { HashMap<String, Object> map = new HashMap<>(); map.put("self", map); System.out.println(map.hashCode()); } }
$ ~/sdk/jdk1.8.0/Contents/Home/bin/java HashMapStackOverflow Exception in thread "main" java.lang.StackOverflowError at java.util.AbstractMap.hashCode(AbstractMap.java:505) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) ...
This will cause a stack overflow because HashMap.hashCode() is inherited from AbstractMap, which sums the hash code of each entry, while one of the entries is itself so it goes recursive.
Thanks, Kris
Hi Vitaly, I can buy that argument. It wasn't hard for me to recognize it when I saw it in real world. But apparently whoever asked me about it couldn't wrap his head around it to understand why... Maybe it's a case for a Pitfalls book instead of for JavaDocs. Thanks, Kris On Friday, July 17, 2015, Vitaly Davidovich <vitalyd@gmail.com <javascript:_e(%7B%7D,'cvml','vitalyd@gmail.com');>> wrote:
IMHO, this doesn't warrant any special wording -- if someone hits this, I think it's fairly evident what the issue is. You can get the same problem with adding an ArrayList to itself and calling hashCode().
On Fri, Jul 17, 2015 at 2:45 PM, Krystal Mok <rednaxelafx@gmail.com> wrote:
Hi everyone,
I'm sure somebody has seen this stack overflow before. My question is: is it expected (which should be documented to warn people not to do this), or is it considered a bug (which should be fixed)?
Example: https://gist.github.com/rednaxelafx/930f8979473185cfc0a0
import java.util.*;
public class HashMapStackOverflow { public static void main(String[] args) throws Exception { HashMap<String, Object> map = new HashMap<>(); map.put("self", map); System.out.println(map.hashCode()); } }
$ ~/sdk/jdk1.8.0/Contents/Home/bin/java HashMapStackOverflow Exception in thread "main" java.lang.StackOverflowError at java.util.AbstractMap.hashCode(AbstractMap.java:505) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) ...
This will cause a stack overflow because HashMap.hashCode() is inherited from AbstractMap, which sums the hash code of each entry, while one of the entries is itself so it goes recursive.
Thanks, Kris
The Javadoc of Map already specifies:
Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. *A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the **equals and hashCode methods are no longer well defined on such a map.*
(emphasis added) On Fri, Jul 17, 2015 at 12:11 PM Krystal Mok <rednaxelafx@gmail.com> wrote:
Hi Vitaly,
I can buy that argument. It wasn't hard for me to recognize it when I saw it in real world.
But apparently whoever asked me about it couldn't wrap his head around it to understand why...
Maybe it's a case for a Pitfalls book instead of for JavaDocs.
Thanks, Kris
On Friday, July 17, 2015, Vitaly Davidovich <vitalyd@gmail.com <javascript:_e(%7B%7D,'cvml','vitalyd@gmail.com');>> wrote:
IMHO, this doesn't warrant any special wording -- if someone hits this, I think it's fairly evident what the issue is. You can get the same problem with adding an ArrayList to itself and calling hashCode().
On Fri, Jul 17, 2015 at 2:45 PM, Krystal Mok <rednaxelafx@gmail.com> wrote:
Hi everyone,
I'm sure somebody has seen this stack overflow before. My question is: is it expected (which should be documented to warn people not to do this), or is it considered a bug (which should be fixed)?
Example: https://gist.github.com/rednaxelafx/930f8979473185cfc0a0
import java.util.*;
public class HashMapStackOverflow { public static void main(String[] args) throws Exception { HashMap<String, Object> map = new HashMap<>(); map.put("self", map); System.out.println(map.hashCode()); } }
$ ~/sdk/jdk1.8.0/Contents/Home/bin/java HashMapStackOverflow Exception in thread "main" java.lang.StackOverflowError at java.util.AbstractMap.hashCode(AbstractMap.java:505) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) ...
This will cause a stack overflow because HashMap.hashCode() is inherited from AbstractMap, which sums the hash code of each entry, while one of the entries is itself so it goes recursive.
Thanks, Kris
Hi Louis, hanks! I thought I had seen it somewhere but I couldn't recall where. That's exactly what I need to answer the guys who asked me for a doc reference. Thanks, Kris On Friday, July 17, 2015, Louis Wasserman <lowasser@google.com> wrote:
The Javadoc of Map already specifies:
Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. *A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the **equals and hashCode methods are no longer well defined on such a map.*
(emphasis added)
On Fri, Jul 17, 2015 at 12:11 PM Krystal Mok <rednaxelafx@gmail.com <javascript:_e(%7B%7D,'cvml','rednaxelafx@gmail.com');>> wrote:
Hi Vitaly,
I can buy that argument. It wasn't hard for me to recognize it when I saw it in real world.
But apparently whoever asked me about it couldn't wrap his head around it to understand why...
Maybe it's a case for a Pitfalls book instead of for JavaDocs.
Thanks, Kris
On Friday, July 17, 2015, Vitaly Davidovich <vitalyd@gmail.com <javascript:_e(%7B%7D,'cvml','vitalyd@gmail.com');> <javascript:_e(%7B%7D,'cvml','vitalyd@gmail.com <javascript:_e(%7B%7D,'cvml','vitalyd@gmail.com');>');>> wrote:
IMHO, this doesn't warrant any special wording -- if someone hits this, I think it's fairly evident what the issue is. You can get the same problem with adding an ArrayList to itself and calling hashCode().
On Fri, Jul 17, 2015 at 2:45 PM, Krystal Mok <rednaxelafx@gmail.com <javascript:_e(%7B%7D,'cvml','rednaxelafx@gmail.com');>> wrote:
Hi everyone,
I'm sure somebody has seen this stack overflow before. My question is: is it expected (which should be documented to warn people not to do this), or is it considered a bug (which should be fixed)?
Example: https://gist.github.com/rednaxelafx/930f8979473185cfc0a0
import java.util.*;
public class HashMapStackOverflow { public static void main(String[] args) throws Exception { HashMap<String, Object> map = new HashMap<>(); map.put("self", map); System.out.println(map.hashCode()); } }
$ ~/sdk/jdk1.8.0/Contents/Home/bin/java HashMapStackOverflow Exception in thread "main" java.lang.StackOverflowError at java.util.AbstractMap.hashCode(AbstractMap.java:505) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) at java.util.Objects.hashCode(Objects.java:98) at java.util.HashMap$Node.hashCode(HashMap.java:296) at java.util.AbstractMap.hashCode(AbstractMap.java:507) ...
This will cause a stack overflow because HashMap.hashCode() is inherited from AbstractMap, which sums the hash code of each entry, while one of the entries is itself so it goes recursive.
Thanks, Kris
On 07/17/2015 09:25 PM, Louis Wasserman wrote:
The Javadoc of Map already specifies:
Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. *A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the **equals and hashCode methods are no longer well defined on such a map.*
The problematic entry had the self-reference in the value, not the key, so this explanation does not really apply here. But java.util.Collections does mention this problem: “ Some collection operations which perform recursive traversal of the collection may fail with an exception for self-referential instances where the collection directly or indirectly contains itself. This includes the clone(), equals(), hashCode() and toString() methods. Implementations may optionally handle the self-referential scenario, however most current implementations do not do so. ” -- Florian Weimer / Red Hat Product Security
participants (4)
-
Florian Weimer
-
Krystal Mok
-
Louis Wasserman
-
Vitaly Davidovich