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 * @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(); 116 } 117 // Find target without sign bit set 118 target = target & Integer.MAX_VALUE; 119 } 120 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); 180 } 181 182 testContainsKey(map, keys_desc, keys); 183 184 testRemove(map, keys_desc, keys); 185 186 map.clear(); 187 testInsertion(map, keys_desc, keys); 188 testKeysIteratorRemove(map, keys_desc, keys); 189 190 map.clear(); 191 testInsertion(map, keys_desc, keys); 192 testValuesIteratorRemove(map, keys_desc, keys); 193 194 map.clear(); 195 testInsertion(map, keys_desc, keys); 196 testEntriesIteratorRemove(map, keys_desc, keys); 197 198 check(map.isEmpty()); 199 } 200 201 private static <T> void testInsertion(Map<T, T> map, String keys_desc, T[] keys) { 202 check("map empty", (map.size() == 0) && map.isEmpty()); 203 204 for (int i = 0; i < keys.length; i++) { 205 check(String.format("insertion: map expected size m%d != i%d", map.size(), i), 206 map.size() == i); 207 check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], keys[i])); 208 check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); 209 check(String.format("insertion: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i])); 210 } 211 212 check(String.format("map expected size m%d != k%d", map.size(), keys.length), 213 map.size() == keys.length); 214 } 215 216 private static void testIntegerIteration(Map<HashableInteger, HashableInteger> map, HashableInteger[] keys) { 217 check(String.format("map expected size m%d != k%d", map.size(), keys.length), 218 map.size() == keys.length); 219 220 BitSet all = new BitSet(keys.length); 221 for (Map.Entry<HashableInteger, HashableInteger> each : map.entrySet()) { 222 check("Iteration: key already seen", !all.get(each.getKey().value)); 223 all.set(each.getKey().value); 224 } 225 226 all.flip(0, keys.length); 227 check("Iteration: some keys not visited", all.isEmpty()); 228 229 for (HashableInteger each : map.keySet()) { 230 check("Iteration: key already seen", !all.get(each.value)); 231 all.set(each.value); 232 } 233 234 all.flip(0, keys.length); 235 check("Iteration: some keys not visited", all.isEmpty()); 236 237 int count = 0; 238 for (HashableInteger each : map.values()) { 239 count++; 240 } 241 242 check(String.format("Iteration: value count matches size m%d != c%d", map.size(), count), 243 map.size() == count); 244 } 245 246 private static void testStringIteration(Map<String, String> map, String[] keys) { 247 check(String.format("map expected size m%d != k%d", map.size(), keys.length), 248 map.size() == keys.length); 249 250 BitSet all = new BitSet(keys.length); 251 for (Map.Entry<String, String> each : map.entrySet()) { 252 String key = each.getKey(); 253 boolean longKey = key.length() > 5; 254 int index = key.hashCode() + (longKey ? keys.length / 2 : 0); 255 check("key already seen", !all.get(index)); 256 all.set(index); 257 } 258 259 all.flip(0, keys.length); 260 check("some keys not visited", all.isEmpty()); 261 262 for (String each : map.keySet()) { 263 boolean longKey = each.length() > 5; 264 int index = each.hashCode() + (longKey ? keys.length / 2 : 0); 265 check("key already seen", !all.get(index)); 266 all.set(index); 267 } 268 269 all.flip(0, keys.length); 270 check("some keys not visited", all.isEmpty()); 271 272 int count = 0; 273 for (String each : map.values()) { 274 count++; 275 } 276 277 check(String.format("value count matches size m%d != k%d", map.size(), keys.length), 278 map.size() == keys.length); 279 } 280 281 private static <T> void testContainsKey(Map<T, T> map, String keys_desc, T[] keys) { 282 for (int i = 0; i < keys.length; i++) { 283 T each = keys[i]; 284 check("containsKey: " + keys_desc + "[" + i + "]" + each, map.containsKey(each)); 285 } 286 } 287 288 private static <T> void testRemove(Map<T, T> map, String keys_desc, T[] keys) { 289 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 290 map.size() == keys.length); 291 292 for (int i = 0; i < keys.length; i++) { 293 T each = keys[i]; 294 check("remove: " + keys_desc + "[" + i + "]" + each, null != map.remove(each)); 295 } 296 297 check(String.format("remove: map empty. size=%d", map.size()), 298 (map.size() == 0) && map.isEmpty()); 299 } 300 301 private static <T> void testKeysIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { 302 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 303 map.size() == keys.length); 304 305 Iterator<T> each = map.keySet().iterator(); 306 while (each.hasNext()) { 307 T t = each.next(); 308 each.remove(); 309 check("not removed: " + each, !map.containsKey(t) ); 310 } 311 312 check(String.format("remove: map empty. size=%d", map.size()), 313 (map.size() == 0) && map.isEmpty()); 314 } 315 316 private static <T> void testValuesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { 317 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 318 map.size() == keys.length); 319 320 Iterator<T> each = map.values().iterator(); 321 while (each.hasNext()) { 322 T t = each.next(); 323 each.remove(); 324 check("not removed: " + each, !map.containsValue(t) ); 325 } 326 327 check(String.format("remove: map empty. size=%d", map.size()), 328 (map.size() == 0) && map.isEmpty()); 329 } 330 331 private static <T> void testEntriesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) { 332 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 333 map.size() == keys.length); 334 335 Iterator<Map.Entry<T,T>> each = map.entrySet().iterator(); 336 while (each.hasNext()) { 337 Map.Entry<T,T> t = each.next(); 338 T key = t.getKey(); 339 T value = t.getValue(); 340 each.remove(); 341 check("not removed: " + each, (map instanceof IdentityHashMap) || !map.entrySet().contains(t) ); 342 check("not removed: " + each, !map.containsKey(key) ); 343 check("not removed: " + each, !map.containsValue(value)); 344 } 345 346 check(String.format("remove: map empty. size=%d", map.size()), 347 (map.size() == 0) && map.isEmpty()); 348 } 349 350 //--------------------- Infrastructure --------------------------- 351 static volatile int passed = 0, failed = 0; 352 353 static void pass() { 354 passed++; 355 } 356 357 static void fail() { 358 failed++; 359 (new Error("Failure")).printStackTrace(System.err); 360 } 361 362 static void fail(String msg) { 363 failed++; 364 (new Error("Failure: " + msg)).printStackTrace(System.err); 365 } 366 367 static void abort() { 368 fail(); 369 System.exit(1); 370 } 371 372 static void abort(String msg) { 373 fail(msg); 374 System.exit(1); 375 } 376 377 static void unexpected(String msg, Throwable t) { 378 System.err.println("Unexpected: " + msg); 379 unexpected(t); 380 } 381 382 static void unexpected(Throwable t) { 383 failed++; 384 t.printStackTrace(System.err); 385 } 386 387 static void check(boolean cond) { 388 if (cond) { 389 pass(); 390 } else { 391 fail(); 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 }