Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-4895001

(coll) hashMap.put(hashMap, x) leads to infinite loop

    XMLWordPrintable

Details

    • Bug
    • Resolution: Won't Fix
    • P4
    • None
    • 1.3.1, 1.4.2
    • core-libs

    Description

      Name: gm110360 Date: 07/23/2003


      FULL PRODUCT VERSION :
      (build 1.4.0_02-b02)
      (build 1.4.1-rc-b19)


      FULL OPERATING SYSTEM VERSION :

      Linux XXXXXX 2.4.9-13 #1 Tue Oct 30 20:11:04 EST 2001 i686 unknown
      Red Hat Linux release 7.2 (Enigma)
      glibc-2.2.4-19

      A DESCRIPTION OF THE PROBLEM :
      HashMap#put() leads StackOverflowError with itself as key in the second call.
      Source code below describes better.

      I found this problem with (build 1.4.0_02-b02) and (build 1.4.1-rc-b19).
      But no error with (build 1.3.1-b24).

      I think this usage is rare and stupid, but Error is a last resort.
      Error can be avoid with something like IllegalArgumentException.

      REGRESSION. Last worked in version 1.3.1

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      1. Just execute the sample code.
      2.
      3.

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      import java.util.*;
      public class HashLoop{
          public static void main(String[] args){
              HashMap hm = new HashMap();
              
              hm.put( hm, "1" );
              hm.put( hm, "2" );// StackOverflowError!!
          }
      }

      ---------- END SOURCE ----------
      (Incident Review ID: 166064)
      ======================================================================

      Name: tb29552 Date: 09/08/2003


      FULL PRODUCT VERSION :
      java version "1.3.1_04"
      Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1_04-b02)
      Java HotSpot(TM) Client VM (build 1.3.1_04-b02, mixed mode)

      FULL OS VERSION :
      Microsoft Windows 2000 [Version 5.00.2195]

      A DESCRIPTION OF THE PROBLEM :
      If you create a HashMap that has a value that contains a cyclic reference to itself calling hashCode() on the original HashMap will fall into an infinite loop.

      I have looked at the source in the src.jar provided. I believe that the AbstractMap.hashCode() method should be changed to be something similar to the following (Note this is not tested code, only an implementation suggestion):


      -->
      private boolean hasCyclic = false;

      public int hashCode() {
          if (!hasCyclic) {
             hasCyclic = true;
             int h = 0;
             Iterator i = entrySet().iterator();
             while (i.hasNext())
                  h += i.next().hashCode();
             hasCyclic = false;
             return h;
         }
         else {
             return System.identityHashCode(this);
             // This code also return 0. Then any hashMap with as a cyclic
             // will return the same value for the cyclic reference.
         }
      }
      <--


      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      1) Create to HashMap instances (m1 and m2).
      2) "put()" m2 into m1 with some key.
      3) "put()" m1 into m2 with some key.
      4) Call hashCode() on m1.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      The code should complete without error.
      ACTUAL -
      The hashCode() method falls into an infinite loop.

      ERROR MESSAGES/STACK TRACES THAT OCCUR :
      ava.lang.StackOverflowError
      at java.util.HashMap$HashIterator.<init>(HashMap.java:713)
      at java.util.HashMap.getHashIterator(HashMap.java:612)
      at java.util.HashMap.access$000(HashMap.java:85)
      at java.util.HashMap$3.iterator(HashMap.java:551)
      at java.util.AbstractMap.hashCode(AbstractMap.java:529)
      at java.util.HashMap$Entry.hashCode(HashMap.java:663)
      at java.util.AbstractMap.hashCode(AbstractMap.java:531)
      at java.util.HashMap$Entry.hashCode(HashMap.java:663)
      at java.util.AbstractMap.hashCode(AbstractMap.java:531)
      at java.util.HashMap$Entry.hashCode(HashMap.java:663)
      ... Lines omitted.

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      public class CyclicTest {

      public static void main(String[] args) {

      HashMap m1 = new HashMap();
      HashMap m2 = new HashMap();

      System.out.println("Put 1");
      m1.put("Name", "Fred");
      System.out.println("Put 2");
      m2.put("Name", "John");
      System.out.println("Put 3");
      m1.put("child", m2);
      System.out.println("Put 4");
      m2.put("Cyclic", m1);
      System.out.println("Call hashCode()");
      m2.hashCode();
      System.out.println("Finish");
      }
      }

      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      Implemented my version of Map that will always use System.identityHashCode() for all methods.
      (Review ID: 206388)
      ======================================================================

      Attachments

        Activity

          People

            martin Martin Buchholz
            gmanwanisunw Girish Manwani (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved:
              Imported:
              Indexed: