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 }