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

HashMap.HashIterator.remove method does not use cached value for the hash code.

    XMLWordPrintable

Details

    • b148
    • generic
    • generic
    • Not verified

    Description

      A DESCRIPTION OF THE REQUEST :
      The remove method of the instance class HashIterator, within java.util.HashMap, does not use the Node's cached value for the hash code. Instead, it recomputes it by calling the static hash(Object key) method.

      The method starts at line 1446 of java.util.HashMap.




      JUSTIFICATION :
      The first issue with this is that it can be faster by using the cached value.

      The second issue, even though developers are not supposed to let an object's hashCode change if it is used in hashing collections, iterator.remove() would fail if the hashCode of the key changed after insertion (given that the bucket for the new value is not the same as for the old hash).

      I provided a TestCase below for the second issue. The reason why it's an issue is pretty simple: If you traverse an iterator, removing all entries, the underlying collection should be empty afterwards. Because the recomputation of the hash has a different result, it doesn't work. If you use the cached value, you use the hash initially computed when the entry was added, and the program ends up actually finding the node you want to remove.


      ---------- BEGIN SOURCE ----------
      import junit.framework.TestCase;

      import java.util.HashMap;
      import java.util.Iterator;
      import java.util.Map;

      public class HashMapTest extends TestCase {
      // This only demonstrates issue #2, not the performance impact of recomputing the hash.
          
          public void testIteratorRemove() {
              Map map = new HashMap();
              Key key = new Key();
              Object value = new Object();
          
              map.put(key, value);
          
              // entrySet(), keySet() and values() iterators all subclass HashMap.HashIterator.
              removeAll(map.keySet().iterator());
              // works just fine as it always does
              assertTrue(map.isEmpty());
          }
          
          public void testIteratorRemoveWithMutableKey() {
              Map map = new HashMap();
              Key key = new Key();
              Object value = new Object();
              
              map.put(key, value);
              key.mutableHashCode = Integer.MAX_VALUE / 2;
              
              // entrySet(), keySet() and values() iterators all subclass HashMap.HashIterator.
              removeAll(map.keySet().iterator());
              // fails. But it's iterating on a Node, and if HashMap uses the cached hashCode, it would presumably not.
              // I think, regardless of whether the hashCode was changed, if you traverse an iterator and remove all entries, the map should be empty afterwards.
              assertTrue(map.isEmpty());
          }
          
          private void removeAll(Iterator iterator) {
              while (iterator.hasNext()) {
                  iterator.next();
                  iterator.remove();
              }
          }
          
          private static class Key {
              int mutableHashCode = 0;
          
              @Override
              public int hashCode() {
                  return mutableHashCode;
              }
          }
          
      }


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

      CUSTOMER SUBMITTED WORKAROUND :
      Replace the sequence "hash(key)" on line 1454 of java.util.HashMap with "p.hash"

      Attachments

        Activity

          People

            psandoz Paul Sandoz
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            7 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: