1 /*
2 * Copyright (c) 2012, 2013, 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 empty", (map.size() == 0) && map.isEmpty());
202
203 for (int i = 0; i < keys.length; i++) {
204 check(String.format("insertion: map expected size m%d != i%d", map.size(), i),
205 map.size() == i);
206 check(String.format("insertion: put(%s[%d])", keys_desc, i), null == map.put(keys[i], keys[i]));
207 check(String.format("insertion: containsKey(%s[%d])", keys_desc, i), map.containsKey(keys[i]));
208 check(String.format("insertion: containsValue(%s[%d])", keys_desc, i), map.containsValue(keys[i]));
209 }
210
211 check(String.format("map expected size m%d != k%d", map.size(), keys.length),
212 map.size() == keys.length);
213 }
214
215 private static void testIntegerIteration(Map<HashableInteger, HashableInteger> map, HashableInteger[] keys) {
216 check(String.format("map expected size m%d != k%d", map.size(), keys.length),
217 map.size() == keys.length);
218
219 BitSet all = new BitSet(keys.length);
220 for (Map.Entry<HashableInteger, HashableInteger> each : map.entrySet()) {
221 check("Iteration: key already seen", !all.get(each.getKey().value));
222 all.set(each.getKey().value);
223 }
224
225 all.flip(0, keys.length);
226 check("Iteration: some keys not visited", all.isEmpty());
227
228 for (HashableInteger each : map.keySet()) {
229 check("Iteration: key already seen", !all.get(each.value));
230 all.set(each.value);
231 }
232
233 all.flip(0, keys.length);
234 check("Iteration: some keys not visited", all.isEmpty());
235
236 int count = 0;
237 for (HashableInteger each : map.values()) {
238 count++;
239 }
240
241 check(String.format("Iteration: value count matches size m%d != c%d", map.size(), count),
242 map.size() == count);
243 }
244
245 private static void testStringIteration(Map<String, String> map, String[] keys) {
246 check(String.format("map expected size m%d != k%d", map.size(), keys.length),
247 map.size() == keys.length);
248
249 BitSet all = new BitSet(keys.length);
250 for (Map.Entry<String, String> each : map.entrySet()) {
251 String key = each.getKey();
252 boolean longKey = key.length() > 5;
253 int index = key.hashCode() + (longKey ? keys.length / 2 : 0);
254 check("key already seen", !all.get(index));
255 all.set(index);
256 }
257
258 all.flip(0, keys.length);
259 check("some keys not visited", all.isEmpty());
260
261 for (String each : map.keySet()) {
262 boolean longKey = each.length() > 5;
263 int index = each.hashCode() + (longKey ? keys.length / 2 : 0);
264 check("key already seen", !all.get(index));
265 all.set(index);
266 }
267
268 all.flip(0, keys.length);
269 check("some keys not visited", all.isEmpty());
270
271 int count = 0;
272 for (String each : map.values()) {
273 count++;
274 }
275
276 check(String.format("value count matches size m%d != k%d", map.size(), keys.length),
277 map.size() == keys.length);
278 }
279
280 private static <T> void testContainsKey(Map<T, T> map, String keys_desc, T[] keys) {
281 for (int i = 0; i < keys.length; i++) {
282 T each = keys[i];
283 check("containsKey: " + keys_desc + "[" + i + "]" + each, map.containsKey(each));
284 }
285 }
286
287 private static <T> void testRemove(Map<T, T> map, String keys_desc, T[] keys) {
288 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
289 map.size() == keys.length);
290
291 for (int i = 0; i < keys.length; i++) {
292 T each = keys[i];
293 check("remove: " + keys_desc + "[" + i + "]" + each, null != map.remove(each));
294 }
295
296 check(String.format("remove: map empty. size=%d", map.size()),
297 (map.size() == 0) && map.isEmpty());
298 }
299
300 private static <T> void testKeysIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) {
301 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
302 map.size() == keys.length);
303
304 Iterator<T> each = map.keySet().iterator();
305 while (each.hasNext()) {
306 T t = each.next();
307 each.remove();
308 check("not removed: " + each, !map.containsKey(t) );
309 }
310
311 check(String.format("remove: map empty. size=%d", map.size()),
312 (map.size() == 0) && map.isEmpty());
313 }
314
315 private static <T> void testValuesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) {
316 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
317 map.size() == keys.length);
318
319 Iterator<T> each = map.values().iterator();
320 while (each.hasNext()) {
321 T t = each.next();
322 each.remove();
323 check("not removed: " + each, !map.containsValue(t) );
324 }
325
326 check(String.format("remove: map empty. size=%d", map.size()),
327 (map.size() == 0) && map.isEmpty());
328 }
329
330 private static <T> void testEntriesIteratorRemove(Map<T, T> map, String keys_desc, T[] keys) {
331 check(String.format("remove: map expected size m%d != k%d", map.size(), keys.length),
332 map.size() == keys.length);
333
334 Iterator<Map.Entry<T,T>> each = map.entrySet().iterator();
335 while (each.hasNext()) {
336 Map.Entry<T,T> t = each.next();
337 T key = t.getKey();
338 T value = t.getValue();
339 each.remove();
340 check("not removed: " + each, (map instanceof IdentityHashMap) || !map.entrySet().contains(t) );
341 check("not removed: " + each, !map.containsKey(key) );
342 check("not removed: " + each, !map.containsValue(value));
343 }
344
345 check(String.format("remove: map empty. size=%d", map.size()),
346 (map.size() == 0) && map.isEmpty());
347 }
348
349 //--------------------- Infrastructure ---------------------------
350 static volatile int passed = 0, failed = 0;
351
352 static void pass() {
353 passed++;
354 }
355
356 static void fail() {
357 failed++;
358 (new Error("Failure")).printStackTrace(System.err);
359 }
360
361 static void fail(String msg) {
362 failed++;
363 (new Error("Failure: " + msg)).printStackTrace(System.err);
364 }
365
366 static void abort() {
367 fail();
368 System.exit(1);
369 }
370
371 static void abort(String msg) {
372 fail(msg);
373 System.exit(1);
374 }
375
376 static void unexpected(String msg, Throwable t) {
377 System.err.println("Unexpected: " + msg);
378 unexpected(t);
379 }
380
381 static void unexpected(Throwable t) {
382 failed++;
383 t.printStackTrace(System.err);
384 }
385
386 static void check(boolean cond) {
387 if (cond) {
388 pass();
389 } else {
390 fail();
391 }
392 }
393
394 static void check(String desc, boolean cond) {
395 if (cond) {
396 pass();
397 } else {
398 fail(desc);
399 }
400 }
401
402 static void equal(Object x, Object y) {
403 if (Objects.equals(x, y)) {
404 pass();
405 } else {
406 fail(x + " not equal to " + y);
407 }
408 }
409
410 public static void main(String[] args) throws Throwable {
411 Thread.currentThread().setName(Collisions.class.getName());
412 // Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
413 try {
414 realMain(args);
415 } catch (Throwable t) {
416 unexpected(t);
417 }
418
419 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
420 if (failed > 0) {
421 throw new Error("Some tests failed");
422 }
423 }
424 }