1 /* 2 * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 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/othervm -Djdk.map.althashing.threshold=0 Collisions -shortrun 29 * @run main/othervm -Djdk.map.useRandomSeed=true Collisions -shortrun 30 * @summary Ensure Maps behave well with lots of hashCode() collisions. 31 * @author Mike Duigou 32 */ 33 import java.util.*; 34 import java.util.concurrent.ConcurrentHashMap; 35 import java.util.concurrent.ConcurrentSkipListMap; 36 37 public class Collisions { 38 39 /** 40 * Number of elements per map. 41 */ 42 private static final int TEST_SIZE = 5000; 43 44 final static class HashableInteger implements Comparable<HashableInteger> { 45 46 final int value; 47 final int hashmask; //yes duplication 48 49 HashableInteger(int value, int hashmask) { 50 this.value = value; 51 this.hashmask = hashmask; 52 } 53 54 @Override 55 public boolean equals(Object obj) { 56 if (obj instanceof HashableInteger) { 57 HashableInteger other = (HashableInteger) obj; 58 59 return other.value == value; 60 } 61 62 return false; 63 } 64 65 @Override 66 public int hashCode() { 67 return value % hashmask; 68 } 69 70 @Override 71 public int compareTo(HashableInteger o) { 72 return value - o.value; 73 } 74 75 @Override 76 public String toString() { 77 return Integer.toString(value); 78 } 79 } 80 81 private static Object[][] makeTestData(int size) { 82 HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[size]; 83 HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[size]; 84 String UNIQUE_STRINGS[] = new String[size]; 85 String COLLIDING_STRINGS[] = new String[size]; 86 87 for (int i = 0; i < size; i++) { 88 UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE); 89 COLLIDING_OBJECTS[i] = new HashableInteger(i, 10); 90 UNIQUE_STRINGS[i] = unhash(i); 91 COLLIDING_STRINGS[i] = (0 == i % 2) 92 ? UNIQUE_STRINGS[i / 2] 93 : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1]; 94 } 95 96 return new Object[][] { 97 new Object[]{"Unique Objects", UNIQUE_OBJECTS}, 98 new Object[]{"Colliding Objects", COLLIDING_OBJECTS}, 99 new Object[]{"Unique Strings", UNIQUE_STRINGS}, 100 new Object[]{"Colliding Strings", COLLIDING_STRINGS} 101 }; 102 } 103 104 /** 105 * Returns a string with a hash equal to the argument. 106 * 107 * @return string with a hash equal to the argument. 108 */ 109 public static String unhash(int target) { 110 StringBuilder answer = new StringBuilder(); 111 if (target < 0) { 112 // String with hash of Integer.MIN_VALUE, 0x80000000 113 answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002"); 114 115 if (target == Integer.MIN_VALUE) { 116 return answer.toString(); 117 } 118 // Find target without sign bit set 119 target = target & Integer.MAX_VALUE; 120 } 121 122 unhash0(answer, target); 123 return answer.toString(); 124 } 125 126 private static void unhash0(StringBuilder partial, int target) { 127 int div = target / 31; 128 int rem = target % 31; 129 130 if (div <= Character.MAX_VALUE) { 131 if (div != 0) { 132 partial.append((char) div); 133 } 134 partial.append((char) rem); 135 } else { 136 unhash0(partial, div); 137 partial.append((char) rem); 138 } 139 } 140 141 private static void realMain(String[] args) throws Throwable { 142 boolean shortRun = args.length > 0 && args[0].equals("-shortrun"); 143 144 Object[][] mapKeys = makeTestData(shortRun ? (TEST_SIZE / 2) : TEST_SIZE); 145 146 // loop through data sets 147 for (Object[] keys_desc : mapKeys) { 148 Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{ 149 new HashMap<>(), 150 new Hashtable<>(), 151 new IdentityHashMap<>(), 152 new LinkedHashMap<>(), 153 new TreeMap<>(), 154 new WeakHashMap<>(), 155 new ConcurrentHashMap<>(), 156 new ConcurrentSkipListMap<>() 157 }; 158 159 // for each map type. 160 for (Map<Object, Object> map : maps) { 161 String desc = (String) keys_desc[0]; 162 Object[] keys = (Object[]) keys_desc[1]; 163 try { 164 testMap(map, desc, keys); 165 } catch(Exception all) { 166 unexpected("Failed for " + map.getClass().getName() + " with " + desc, all); 167 } 168 } 169 } 170 } 171 172 private static <T> void testMap(Map<T, T> map, String keys_desc, T[] keys) { 173 System.out.println(map.getClass() + " : " + keys_desc); 174 System.out.flush(); 175 testInsertion(map, keys_desc, keys); 176 177 if (keys[0] instanceof HashableInteger) { 178 testIntegerIteration((Map<HashableInteger, HashableInteger>) map, (HashableInteger[]) keys); 179 } else { 180 testStringIteration((Map<String, String>) map, (String[]) keys); 181 } 182 183 testContainsKey(map, keys_desc, keys); 184 185 testRemove(map, keys_desc, keys); 186 187 map.clear(); 188 testInsertion(map, keys_desc, keys); 189 testKeysIteratorRemove(map, keys_desc, keys); 190 191 map.clear(); 192 testInsertion(map, keys_desc, keys); 193 testValuesIteratorRemove(map, keys_desc, keys); 194 195 map.clear(); 196 testInsertion(map, keys_desc, keys); 197 testEntriesIteratorRemove(map, keys_desc, keys); 198 199 check(map.isEmpty()); 200 } 201 202 private static <T> void testInsertion(Map<T, T> map, String keys_desc, T[] keys) { 203 check("map empty", (map.size() == 0) && map.isEmpty()); 204 205 for (int i = 0; i < keys.length; i++) { 206 check(String.format("insertion: map expected size m%d != i%d", map.size(), i), 207 map.size() == i); 208 check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], keys[i])); 209 check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); 210 check(String.format("insertion: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i])); 211 } 212 213 check(String.format("map expected size m%d != k%d", map.size(), keys.length), 214 map.size() == keys.length); 215 } 216 217 private static void testIntegerIteration(Map<HashableInteger, HashableInteger> map, HashableInteger[] keys) { 218 check(String.format("map expected size m%d != k%d", map.size(), keys.length), 219 map.size() == keys.length); 220 221 BitSet all = new BitSet(keys.length); 222 for (Map.Entry<HashableInteger, HashableInteger> each : map.entrySet()) { 223 check("Iteration: key already seen", !all.get(each.getKey().value)); 224 all.set(each.getKey().value); 225 } 226 227 all.flip(0, keys.length); 228 check("Iteration: some keys not visited", all.isEmpty()); 229 230 for (HashableInteger each : map.keySet()) { 231 check("Iteration: key already seen", !all.get(each.value)); 232 all.set(each.value); 233 } 234 235 all.flip(0, keys.length); 236 check("Iteration: some keys not visited", all.isEmpty()); 237 238 int count = 0; 239 for (HashableInteger each : map.values()) { 240 count++; 241 } 242 243 check(String.format("Iteration: value count matches size m%d != c%d", map.size(), count), 244 map.size() == count); 245 } 246 247 private static void testStringIteration(Map<String, String> map, String[] keys) { 248 check(String.format("map expected size m%d != k%d", map.size(), keys.length), 249 map.size() == keys.length); 250 251 BitSet all = new BitSet(keys.length); 252 for (Map.Entry<String, String> each : map.entrySet()) { 253 String key = each.getKey(); 254 boolean longKey = key.length() > 5; 255 int index = key.hashCode() + (longKey ? keys.length / 2 : 0); 256 check("key already seen", !all.get(index)); 257 all.set(index); 258 } 259 260 all.flip(0, keys.length); 261 check("some keys not visited", all.isEmpty()); 262 263 for (String each : map.keySet()) { 264 boolean longKey = each.length() > 5; 265 int index = each.hashCode() + (longKey ? keys.length / 2 : 0); 266 check("key already seen", !all.get(index)); 267 all.set(index); 268 } 269 270 all.flip(0, keys.length); 271 check("some keys not visited", all.isEmpty()); 272 273 int count = 0; 274 for (String each : map.values()) { 275 count++; 276 } 277 278 check(String.format("value count matches size m%d != k%d", map.size(), keys.length), 279 map.size() == keys.length); 280 } 281 282 private static <T> void testContainsKey(Map<T, T> map, String keys_desc, T[] keys) { 283 for (int i = 0; i < keys.length; i++) { 284 T each = keys[i]; 285 check("containsKey: " + keys_desc + "[" + i + "]" + each, map.containsKey(each)); 286 } 287 } 288 289 private static <T> void testRemove(Map<T, T> map, String keys_desc, T[] keys) { 290 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 291 map.size() == keys.length); 292 293 for (int i = 0; i < keys.length; i++) { 294 T each = keys[i]; 295 check("remove: " + keys_desc + "[" + i + "]" + each, null != map.remove(each)); 296 } 297 298 check(String.format("remove: map empty. size=%d", map.size()), 299 (map.size() == 0) && map.isEmpty()); 300 } 301 302 private static <T> void testKeysIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { 303 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 304 map.size() == keys.length); 305 306 Iterator<T> each = map.keySet().iterator(); 307 while (each.hasNext()) { 308 T t = each.next(); 309 each.remove(); 310 check("not removed: " + each, !map.containsKey(t) ); 311 } 312 313 check(String.format("remove: map empty. size=%d", map.size()), 314 (map.size() == 0) && map.isEmpty()); 315 } 316 317 private static <T> void testValuesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { 318 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 319 map.size() == keys.length); 320 321 Iterator<T> each = map.values().iterator(); 322 while (each.hasNext()) { 323 T t = each.next(); 324 each.remove(); 325 check("not removed: " + each, !map.containsValue(t) ); 326 } 327 328 check(String.format("remove: map empty. size=%d", map.size()), 329 (map.size() == 0) && map.isEmpty()); 330 } 331 332 private static <T> void testEntriesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { 333 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 334 map.size() == keys.length); 335 336 Iterator<Map.Entry<T,T>> each = map.entrySet().iterator(); 337 while (each.hasNext()) { 338 Map.Entry<T,T> t = each.next(); 339 T key = t.getKey(); 340 T value = t.getValue(); 341 each.remove(); 342 check("not removed: " + each, (map instanceof IdentityHashMap) || !map.entrySet().contains(t) ); 343 check("not removed: " + each, !map.containsKey(key) ); 344 check("not removed: " + each, !map.containsValue(value)); 345 } 346 347 check(String.format("remove: map empty. size=%d", map.size()), 348 (map.size() == 0) && map.isEmpty()); 349 } 350 351 //--------------------- Infrastructure --------------------------- 352 static volatile int passed = 0, failed = 0; 353 354 static void pass() { 355 passed++; 356 } 357 358 static void fail() { 359 failed++; 360 (new Error("Failure")).printStackTrace(System.err); 361 } 362 363 static void fail(String msg) { 364 failed++; 365 (new Error("Failure: " + msg)).printStackTrace(System.err); 366 } 367 368 static void abort() { 369 fail(); 370 System.exit(1); 371 } 372 373 static void abort(String msg) { 374 fail(msg); 375 System.exit(1); 376 } 377 378 static void unexpected(String msg, Throwable t) { 379 System.err.println("Unexpected: " + msg); 380 unexpected(t); 381 } 382 383 static void unexpected(Throwable t) { 384 failed++; 385 t.printStackTrace(System.err); 386 } 387 388 static void check(boolean cond) { 389 if (cond) { 390 pass(); 391 } else { 392 fail(); 393 } 394 } 395 396 static void check(String desc, boolean cond) { 397 if (cond) { 398 pass(); 399 } else { 400 fail(desc); 401 } 402 } 403 404 static void equal(Object x, Object y) { 405 if (Objects.equals(x, y)) { 406 pass(); 407 } else { 408 fail(x + " not equal to " + y); 409 } 410 } 411 412 public static void main(String[] args) throws Throwable { 413 Thread.currentThread().setName(Collisions.class.getName()); 414 // Thread.currentThread().setPriority(Thread.MAX_PRIORITY); 415 try { 416 realMain(args); 417 } catch (Throwable t) { 418 unexpected(t); 419 } 420 421 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 422 if (failed > 0) { 423 throw new Error("Some tests failed"); 424 } 425 } 426 }