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 = 10000; 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, Boolean>[] MAPS = (Map<Object, Boolean>[]) 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, Boolean> map : MAPS) { 148 String desc = (String) keys_desc[0]; 149 Object[] keys = (Object[]) keys_desc[1]; 150 testMap(map, desc, keys); 151 } 152 } 153 } 154 155 private static <T> void testMap(Map<T, Boolean> map, String keys_desc, T[] keys) { 156 System.err.println(map.getClass() + " : " + keys_desc); 157 testInsertion(map, keys_desc, keys); 158 159 if (keys[0] instanceof HashableInteger) { 160 testIntegerIteration((Map<HashableInteger, Boolean>) map, (HashableInteger[]) keys); 161 } else { 162 testStringIteration((Map<String, Boolean>) map, (String[]) keys); 163 } 164 165 testContainsKey(map, keys_desc, keys); 166 167 testRemove(map, keys_desc, keys); 168 169 check(map.isEmpty()); 170 } 171 172 private static <T> void testInsertion(Map<T, Boolean> map, String keys_desc, T[] keys) { 173 check("map empty", (map.size() == 0) && map.isEmpty()); 174 175 for (int i = 0; i < keys.length; i++) { 176 check(String.format("insertion: map expected size m%d != i%d", map.size(), i), 177 map.size() == i); 178 check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], true)); 179 check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i])); 180 } 181 182 check(String.format("map expected size m%d != k%d", map.size(), keys.length), 183 map.size() == keys.length); 184 } 185 186 private static void testIntegerIteration(Map<HashableInteger, Boolean> map, HashableInteger[] keys) { 187 check(String.format("map expected size m%d != k%d", map.size(), keys.length), 188 map.size() == keys.length); 189 190 BitSet all = new BitSet(keys.length); 191 for (Map.Entry<HashableInteger, Boolean> each : map.entrySet()) { 192 check("Iteration: key already seen", !all.get(each.getKey().value)); 193 all.set(each.getKey().value); 194 } 195 196 all.flip(0, keys.length); 197 check("Iteration: some keys not visited", all.isEmpty()); 198 199 for (HashableInteger each : map.keySet()) { 200 check("Iteration: key already seen", !all.get(each.value)); 201 all.set(each.value); 202 } 203 204 all.flip(0, keys.length); 205 check("Iteration: some keys not visited", all.isEmpty()); 206 207 int count = 0; 208 for (Boolean each : map.values()) { 209 count++; 210 } 211 212 check(String.format("Iteration: value count matches size m%d != c%d", map.size(), count), 213 map.size() == count); 214 } 215 216 private static void testStringIteration(Map<String, Boolean> map, String[] 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<String, Boolean> each : map.entrySet()) { 222 String key = each.getKey(); 223 boolean longKey = key.length() > 5; 224 int index = key.hashCode() + (longKey ? keys.length / 2 : 0); 225 check("key already seen", !all.get(index)); 226 all.set(index); 227 } 228 229 all.flip(0, keys.length); 230 check("some keys not visited", all.isEmpty()); 231 232 for (String each : map.keySet()) { 233 boolean longKey = each.length() > 5; 234 int index = each.hashCode() + (longKey ? keys.length / 2 : 0); 235 check("key already seen", !all.get(index)); 236 all.set(index); 237 } 238 239 all.flip(0, keys.length); 240 check("some keys not visited", all.isEmpty()); 241 242 int count = 0; 243 for (Boolean each : map.values()) { 244 count++; 245 } 246 247 check(String.format("value count matches size m%d != k%d", map.size(), keys.length), 248 map.size() == keys.length); 249 } 250 251 private static <T> void testContainsKey(Map<T, Boolean> map, String keys_desc, T[] keys) { 252 for (int i = 0; i < keys.length; i++) { 253 T each = keys[i]; 254 check("containsKey: " + keys_desc + "[" + i + "]" + each, map.containsKey(each)); 255 } 256 } 257 258 private static <T> void testRemove(Map<T, Boolean> map, String keys_desc, T[] keys) { 259 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length), 260 map.size() == keys.length); 261 262 for (int i = 0; i < keys.length; i++) { 263 T each = keys[i]; 264 check("remove: " + keys_desc + "[" + i + "]" + each, null != map.remove(each)); 265 } 266 267 check(String.format("remove: map empty. size=%d", map.size()), 268 (map.size() == 0) && map.isEmpty()); 269 } 270 //--------------------- Infrastructure --------------------------- 271 static volatile int passed = 0, failed = 0; 272 273 static void pass() { 274 passed++; 275 } 276 277 static void fail() { 278 failed++; 279 (new Error("Failure")).printStackTrace(System.err); 280 } 281 282 static void fail(String msg) { 283 failed++; 284 (new Error("Failure: " + msg)).printStackTrace(System.err); 285 } 286 287 static void abort() { 288 fail(); 289 System.exit(1); 290 } 291 292 static void abort(String msg) { 293 fail(msg); 294 System.exit(1); 295 } 296 297 static void unexpected(String msg, Throwable t) { 298 System.err.println("Unexpected: " + msg); 299 unexpected(t); 300 } 301 302 static void unexpected(Throwable t) { 303 failed++; 304 t.printStackTrace(System.err); 305 } 306 307 static void check(boolean cond) { 308 if (cond) { 309 pass(); 310 } else { 311 fail(); 312 } 313 } 314 315 static void check(String desc, boolean cond) { 316 if (cond) { 317 pass(); 318 } else { 319 fail(desc); 320 } 321 } 322 323 static void equal(Object x, Object y) { 324 if (Objects.equals(x, y)) { 325 pass(); 326 } else { 327 fail(x + " not equal to " + y); 328 } 329 } 330 331 public static void main(String[] args) throws Throwable { 332 Thread.currentThread().setName("Collisions"); 333 // Thread.currentThread().setPriority(Thread.MAX_PRIORITY); 334 try { 335 realMain(args); 336 } catch (Throwable t) { 337 unexpected(t); 338 } 339 340 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 341 if (failed > 0) { 342 throw new Error("Some tests failed"); 343 } 344 } 345 }