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();
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);
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 }
|
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 * @run main Collisions -Djdk.map.althashing.threshold=0 -shortrun
29 * @summary Ensure Maps behave well with lots of hashCode() collisions.
30 * @author Mike Duigou
31 */
32 import java.util.*;
33 import java.util.concurrent.ConcurrentHashMap;
34 import java.util.concurrent.ConcurrentSkipListMap;
35
36 public class Collisions {
37
38 /**
39 * Number of elements per map.
40 */
41 private static final int TEST_SIZE = 5000;
42
43 final static class HashableInteger implements Comparable<HashableInteger> {
44
45 final int value;
46 final int hashmask; //yes duplication
47
48 HashableInteger(int value, int hashmask) {
49 this.value = value;
50 this.hashmask = hashmask;
51 }
52
53 @Override
54 public boolean equals(Object obj) {
55 if (obj instanceof HashableInteger) {
56 HashableInteger other = (HashableInteger) obj;
57
58 return other.value == value;
59 }
60
61 return false;
62 }
63
64 @Override
65 public int hashCode() {
66 return value % hashmask;
67 }
68
69 @Override
70 public int compareTo(HashableInteger o) {
71 return value - o.value;
72 }
73
74 @Override
75 public String toString() {
76 return Integer.toString(value);
77 }
78 }
79
80 private static Object[][] makeTestData(int size) {
81 HashableInteger UNIQUE_OBJECTS[] = new HashableInteger[size];
82 HashableInteger COLLIDING_OBJECTS[] = new HashableInteger[size];
83 String UNIQUE_STRINGS[] = new String[size];
84 String COLLIDING_STRINGS[] = new String[size];
85
86 for (int i = 0; i < size; i++) {
87 UNIQUE_OBJECTS[i] = new HashableInteger(i, Integer.MAX_VALUE);
88 COLLIDING_OBJECTS[i] = new HashableInteger(i, 10);
89 UNIQUE_STRINGS[i] = unhash(i);
90 COLLIDING_STRINGS[i] = (0 == i % 2)
91 ? UNIQUE_STRINGS[i / 2]
92 : "\u0000\u0000\u0000\u0000\u0000" + COLLIDING_STRINGS[i - 1];
93 }
94
95 return new Object[][] {
96 new Object[]{"Unique Objects", UNIQUE_OBJECTS},
97 new Object[]{"Colliding Objects", COLLIDING_OBJECTS},
98 new Object[]{"Unique Strings", UNIQUE_STRINGS},
99 new Object[]{"Colliding Strings", COLLIDING_STRINGS}
100 };
101 }
102
103 /**
104 * Returns a string with a hash equal to the argument.
105 *
106 * @return string with a hash equal to the argument.
107 */
108 public static String unhash(int target) {
109 StringBuilder answer = new StringBuilder();
110 if (target < 0) {
111 // String with hash of Integer.MIN_VALUE, 0x80000000
112 answer.append("\\u0915\\u0009\\u001e\\u000c\\u0002");
113
114 if (target == Integer.MIN_VALUE) {
115 return answer.toString();
121 unhash0(answer, target);
122 return answer.toString();
123 }
124
125 private static void unhash0(StringBuilder partial, int target) {
126 int div = target / 31;
127 int rem = target % 31;
128
129 if (div <= Character.MAX_VALUE) {
130 if (div != 0) {
131 partial.append((char) div);
132 }
133 partial.append((char) rem);
134 } else {
135 unhash0(partial, div);
136 partial.append((char) rem);
137 }
138 }
139
140 private static void realMain(String[] args) throws Throwable {
141 boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
142
143 Object[][] mapKeys = makeTestData(shortRun ? (TEST_SIZE / 2) : TEST_SIZE);
144
145 // loop through data sets
146 for (Object[] keys_desc : mapKeys) {
147 Map<Object, Object>[] maps = (Map<Object, Object>[]) new Map[]{
148 new HashMap<>(),
149 new Hashtable<>(),
150 new IdentityHashMap<>(),
151 new LinkedHashMap<>(),
152 new TreeMap<>(),
153 new WeakHashMap<>(),
154 new ConcurrentHashMap<>(),
155 new ConcurrentSkipListMap<>()
156 };
157
158 // for each map type.
159 for (Map<Object, Object> map : maps) {
160 String desc = (String) keys_desc[0];
161 Object[] keys = (Object[]) keys_desc[1];
162 try {
163 testMap(map, desc, keys);
164 } catch(Exception all) {
165 unexpected("Failed for " + map.getClass().getName() + " with " + desc, all);
166 }
167 }
168 }
169 }
170
171 private static <T> void testMap(Map<T, T> map, String keys_desc, T[] keys) {
172 System.out.println(map.getClass() + " : " + keys_desc);
173 System.out.flush();
174 testInsertion(map, keys_desc, keys);
175
176 if (keys[0] instanceof HashableInteger) {
177 testIntegerIteration((Map<HashableInteger, HashableInteger>) map, (HashableInteger[]) keys);
178 } else {
179 testStringIteration((Map<String, String>) map, (String[]) keys);
392 }
393 }
394
395 static void check(String desc, boolean cond) {
396 if (cond) {
397 pass();
398 } else {
399 fail(desc);
400 }
401 }
402
403 static void equal(Object x, Object y) {
404 if (Objects.equals(x, y)) {
405 pass();
406 } else {
407 fail(x + " not equal to " + y);
408 }
409 }
410
411 public static void main(String[] args) throws Throwable {
412 Thread.currentThread().setName(Collisions.class.getName());
413 // Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
414 try {
415 realMain(args);
416 } catch (Throwable t) {
417 unexpected(t);
418 }
419
420 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
421 if (failed > 0) {
422 throw new Error("Some tests failed");
423 }
424 }
425 }
|