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