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 }