test/java/util/Map/Collisions.java

Print this page
rev 5714 : 7189926: Reduce test size for default run. Add additional run enabling alternative hashing.
Reviewed-by: duke


   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test
  26  * @bug 7126277


  27  * @summary Ensure Maps behave well with lots of hashCode() collisions.
  28  * @author Mike Duigou
  29  */
  30 import java.util.*;
  31 import java.util.concurrent.ConcurrentHashMap;
  32 import java.util.concurrent.ConcurrentSkipListMap;
  33 
  34 public class Collisions {
  35 





  36     final static class HashableInteger implements Comparable<HashableInteger> {
  37 
  38         final int value;
  39         final int hashmask; //yes duplication
  40 
  41         HashableInteger(int value, int hashmask) {
  42             this.value = value;
  43             this.hashmask = hashmask;
  44         }
  45 
  46         @Override
  47         public boolean equals(Object obj) {
  48             if (obj instanceof HashableInteger) {
  49                 HashableInteger other = (HashableInteger) obj;
  50 
  51                 return other.value == value;
  52             }
  53 
  54             return false;
  55         }
  56 
  57         @Override
  58         public int hashCode() {
  59             return value % hashmask;
  60         }
  61 
  62         @Override
  63         public int compareTo(HashableInteger o) {
  64             return value - o.value;
  65         }
  66 

  67         public String toString() {
  68             return Integer.toString(value);
  69         }
  70     }
  71     private static final int ITEMS = 5000;
  72     private static final Object KEYS[][];
  73 
  74     static {
  75         HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[ITEMS];
  76         HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[ITEMS];
  77         String UNIQUE_STRINGS[] = new String[ITEMS];
  78         String COLLIDING_STRINGS[] = new String[ITEMS];
  79 
  80         for (int i = 0; i < ITEMS; i++) {
  81             UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE);
  82             COLLIDING_OBJECTS[i] = new HashableInteger(i, 10);
  83             UNIQUE_STRINGS[i] = unhash(i);
  84             COLLIDING_STRINGS[i] = (0 == i % 2)
  85                     ? UNIQUE_STRINGS[i / 2]
  86                     : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1];
  87         }
  88 
  89      KEYS = new Object[][] {
  90             new Object[]{"Unique Objects", UNIQUE_OBJECTS},
  91             new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
  92             new Object[]{"Unique Strings", UNIQUE_STRINGS},
  93             new Object[]{"Colliding Strings", COLLIDING_STRINGS}
  94         };
  95     }
  96 
  97     /**
  98      * Returns a string with a hash equal to the argument.
  99      *
 100      * @return string with a hash equal to the argument.
 101      */
 102     public static String unhash(int target) {
 103         StringBuilder answer = new StringBuilder();
 104         if (target < 0) {
 105             // String with hash of Integer.MIN_VALUE, 0x80000000
 106             answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002");
 107 
 108             if (target == Integer.MIN_VALUE) {
 109                 return answer.toString();


 115         unhash0(answer, target);
 116         return answer.toString();
 117     }
 118 
 119     private static void unhash0(StringBuilder partial, int target) {
 120         int div = target / 31;
 121         int rem = target % 31;
 122 
 123         if (div <= Character.MAX_VALUE) {
 124             if (div != 0) {
 125                 partial.append((char) div);
 126             }
 127             partial.append((char) rem);
 128         } else {
 129             unhash0(partial, div);
 130             partial.append((char) rem);
 131         }
 132     }
 133 
 134     private static void realMain(String[] args) throws Throwable {
 135         for (Object[] keys_desc : KEYS) {
 136             Map<Object, Object>[] MAPS = (Map<Object, Object>[]) new Map[]{
 137                         new Hashtable<>(),




 138                         new HashMap<>(),

 139                         new IdentityHashMap<>(),
 140                         new LinkedHashMap<>(),
 141                         new ConcurrentHashMap<>(),
 142                         new WeakHashMap<>(),
 143                         new TreeMap<>(),


 144                         new ConcurrentSkipListMap<>()
 145                     };
 146 
 147             for (Map<Object, Object> map : MAPS) {

 148                 String desc = (String) keys_desc[0];
 149                 Object[] keys = (Object[]) keys_desc[1];
 150                 try {
 151                 testMap(map, desc, keys);
 152                 } catch(Exception all) {
 153                     unexpected("Failed for " + map.getClass().getName() + " with " + desc, all);
 154                 }
 155             }
 156         }
 157     }
 158 
 159     private static <T> void testMap(Map<T, T> map, String keys_desc, T[] keys) {
 160         System.out.println(map.getClass() + " : " + keys_desc);
 161         System.out.flush();
 162         testInsertion(map, keys_desc, keys);
 163 
 164         if (keys[0] instanceof HashableInteger) {
 165             testIntegerIteration((Map<HashableInteger, HashableInteger>) map, (HashableInteger[]) keys);
 166         } else {
 167             testStringIteration((Map<String, String>) map, (String[]) keys);


 380         }
 381     }
 382 
 383     static void check(String desc, boolean cond) {
 384         if (cond) {
 385             pass();
 386         } else {
 387             fail(desc);
 388         }
 389     }
 390 
 391     static void equal(Object x, Object y) {
 392         if (Objects.equals(x, y)) {
 393             pass();
 394         } else {
 395             fail(x + " not equal to " + y);
 396         }
 397     }
 398 
 399     public static void main(String[] args) throws Throwable {
 400         Thread.currentThread().setName("Collisions");
 401 //        Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
 402         try {
 403             realMain(args);
 404         } catch (Throwable t) {
 405             unexpected(t);
 406         }
 407 
 408         System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
 409         if (failed > 0) {
 410             throw new Error("Some tests failed");
 411         }
 412     }
 413 }


   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /*
  25  * @test
  26  * @bug 7126277
  27  * @run main Collisions -shortrun
  28  * @run main Collisions -Djdk.map.althashing.threshold=0 -shortrun
  29  * @summary Ensure Maps behave well with lots of hashCode() collisions.
  30  * @author Mike Duigou
  31  */
  32 import java.util.*;
  33 import java.util.concurrent.ConcurrentHashMap;
  34 import java.util.concurrent.ConcurrentSkipListMap;
  35 
  36 public class Collisions {
  37 
  38     /**
  39      * Number of elements per map.
  40      */
  41     private static final int TEST_SIZE = 5000;
  42 
  43     final static class HashableInteger implements Comparable<HashableInteger> {
  44 
  45         final int value;
  46         final int hashmask; //yes duplication
  47 
  48         HashableInteger(int value, int hashmask) {
  49             this.value = value;
  50             this.hashmask = hashmask;
  51         }
  52 
  53         @Override
  54         public boolean equals(Object obj) {
  55             if (obj instanceof HashableInteger) {
  56                 HashableInteger other = (HashableInteger) obj;
  57 
  58                 return other.value == value;
  59             }
  60 
  61             return false;
  62         }
  63 
  64         @Override
  65         public int hashCode() {
  66             return value % hashmask;
  67         }
  68 
  69         @Override
  70         public int compareTo(HashableInteger o) {
  71             return value - o.value;
  72         }
  73 
  74         @Override
  75         public String toString() {
  76             return Integer.toString(value);
  77         }
  78     }


  79 
  80     private static Object[][] makeTestData(int size) {
  81         HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[size];
  82         HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[size];
  83         String UNIQUE_STRINGS[] = new String[size];
  84         String COLLIDING_STRINGS[] = new String[size];
  85 
  86         for (int i = 0; i < size; i++) {
  87             UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE);
  88             COLLIDING_OBJECTS[i] = new HashableInteger(i, 10);
  89             UNIQUE_STRINGS[i] = unhash(i);
  90             COLLIDING_STRINGS[i] = (0 == i % 2)
  91                     ? UNIQUE_STRINGS[i / 2]
  92                     : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1];
  93         }
  94 
  95      return new Object[][] {
  96             new Object[]{"Unique Objects", UNIQUE_OBJECTS},
  97             new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
  98             new Object[]{"Unique Strings", UNIQUE_STRINGS},
  99             new Object[]{"Colliding Strings", COLLIDING_STRINGS}
 100         };
 101     }
 102 
 103     /**
 104      * Returns a string with a hash equal to the argument.
 105      *
 106      * @return string with a hash equal to the argument.
 107      */
 108     public static String unhash(int target) {
 109         StringBuilder answer = new StringBuilder();
 110         if (target < 0) {
 111             // String with hash of Integer.MIN_VALUE, 0x80000000
 112             answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002");
 113 
 114             if (target == Integer.MIN_VALUE) {
 115                 return answer.toString();


 121         unhash0(answer, target);
 122         return answer.toString();
 123     }
 124 
 125     private static void unhash0(StringBuilder partial, int target) {
 126         int div = target / 31;
 127         int rem = target % 31;
 128 
 129         if (div <= Character.MAX_VALUE) {
 130             if (div != 0) {
 131                 partial.append((char) div);
 132             }
 133             partial.append((char) rem);
 134         } else {
 135             unhash0(partial, div);
 136             partial.append((char) rem);
 137         }
 138     }
 139 
 140     private static void realMain(String[] args) throws Throwable {
 141         boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
 142 
 143         Object[][] mapKeys = makeTestData(shortRun ? (TEST_SIZE / 2) : TEST_SIZE);
 144 
 145         // loop through data sets
 146         for (Object[] keys_desc : mapKeys) {
 147             Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{
 148                         new HashMap<>(),
 149                         new Hashtable<>(),
 150                         new IdentityHashMap<>(),
 151                         new LinkedHashMap<>(),


 152                         new TreeMap<>(),
 153                         new WeakHashMap<>(),
 154                         new ConcurrentHashMap<>(),
 155                         new ConcurrentSkipListMap<>()
 156                     };
 157 
 158             // for each map type.
 159             for (Map<Object, Object> map : maps) {
 160                 String desc = (String) keys_desc[0];
 161                 Object[] keys = (Object[]) keys_desc[1];
 162                 try {
 163                     testMap(map, desc, keys);
 164                 } catch(Exception all) {
 165                     unexpected("Failed for " + map.getClass().getName() + " with " + desc, all);
 166                 }
 167             }
 168         }
 169     }
 170 
 171     private static <T> void testMap(Map<T, T> map, String keys_desc, T[] keys) {
 172         System.out.println(map.getClass() + " : " + keys_desc);
 173         System.out.flush();
 174         testInsertion(map, keys_desc, keys);
 175 
 176         if (keys[0] instanceof HashableInteger) {
 177             testIntegerIteration((Map<HashableInteger, HashableInteger>) map, (HashableInteger[]) keys);
 178         } else {
 179             testStringIteration((Map<String, String>) map, (String[]) keys);


 392         }
 393     }
 394 
 395     static void check(String desc, boolean cond) {
 396         if (cond) {
 397             pass();
 398         } else {
 399             fail(desc);
 400         }
 401     }
 402 
 403     static void equal(Object x, Object y) {
 404         if (Objects.equals(x, y)) {
 405             pass();
 406         } else {
 407             fail(x + " not equal to " + y);
 408         }
 409     }
 410 
 411     public static void main(String[] args) throws Throwable {
 412         Thread.currentThread().setName(Collisions.class.getName());
 413 //        Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
 414         try {
 415             realMain(args);
 416         } catch (Throwable t) {
 417             unexpected(t);
 418         }
 419 
 420         System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
 421         if (failed > 0) {
 422             throw new Error("Some tests failed");
 423         }
 424     }
 425 }