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