|
1
30
31
32 package org.hsqldb.test;
33
34 import java.util.Random  ;
35
36 import org.hsqldb.lib.DoubleIntIndex;
37 import org.hsqldb.lib.StopWatch;
38
39 import junit.framework.TestCase;
40
41
44 public class TestHashStructures extends TestCase {
45
46 public TestHashStructures(String s) {
47 super(s);
48 }
49
50 Random randomgen = new java.util.Random ();
51
52 public void testHashMap() throws Exception {
53
54 boolean failed = false;
55 int testSize = 33;
56 org.hsqldb.lib.HashMap hMap = new org.hsqldb.lib.HashMap();
57 org.hsqldb.lib.IntKeyHashMap hIntMap =
58 new org.hsqldb.lib.IntKeyHashMap();
59 java.util.HashMap uMap = new java.util.HashMap ();
60
61 try {
62 populateBySerialIntKeys(uMap, hMap, testSize);
63 compareByUIterator(uMap, hMap);
64 compareByHIterator(uMap, hMap);
65
66 populateByRandomIntKeys(uMap, hMap, testSize);
68 compareByUIterator(uMap, hMap);
69 compareByHIterator(uMap, hMap);
70
71 depopulateRandomly(uMap, hMap, 20);
73 compareByUIterator(uMap, hMap);
74 compareByHIterator(uMap, hMap);
75
76 populateBySerialIntKeys(uMap, hMap, testSize);
78 compareByUIterator(uMap, hMap);
79 compareByHIterator(uMap, hMap);
80
81 depopulateByIterator(uMap, hMap, 20);
83 compareByUIterator(uMap, hMap);
84 compareByHIterator(uMap, hMap);
85 } catch (Exception e) {
86 failed = true;
87 }
88
89 assertTrue(!failed);
90 }
91
92 public void testIntKeyHashMap() throws Exception {
93
94 boolean failed = false;
95 int testSize = 33;
96 org.hsqldb.lib.IntKeyHashMap hIntMap =
97 new org.hsqldb.lib.IntKeyHashMap();
98 java.util.HashMap uMap = new java.util.HashMap ();
99
100 try {
101 populateBySerialIntKeysInt(uMap, hIntMap, testSize);
102 compareByUIteratorInt(uMap, hIntMap);
103 populateByRandomIntKeysInt(uMap, hIntMap, testSize);
104 compareByUIteratorInt(uMap, hIntMap);
105 compareByHIteratorInt(uMap, hIntMap);
106
107 depopulateByIntIterator(uMap, hIntMap, 20);
109 compareByUIteratorInt(uMap, hIntMap);
110 compareByHIteratorInt(uMap, hIntMap);
111
112 clearByIntIterator(uMap, hIntMap);
114 compareByUIteratorInt(uMap, hIntMap);
115 compareByHIteratorInt(uMap, hIntMap);
116
117 populateBySerialIntKeysInt(uMap, hIntMap, testSize);
119 compareByUIteratorInt(uMap, hIntMap);
120 compareByHIteratorInt(uMap, hIntMap);
121
122 clearByIntIterator(uMap, hIntMap);
124 compareByUIteratorInt(uMap, hIntMap);
125 compareByHIteratorInt(uMap, hIntMap);
126 } catch (Exception e) {
127 failed = true;
128 }
129
130 assertTrue(!failed);
131 }
132
133 public void testHashMappedList() throws Exception {
134
135 boolean failed = false;
136 int testSize = 33;
137 org.hsqldb.lib.HashMappedList hMap =
138 new org.hsqldb.lib.HashMappedList();
139 java.util.HashMap uMap = new java.util.HashMap ();
140
141 try {
142 populateBySerialIntKeys(uMap, hMap, testSize);
143 compareByUIterator(uMap, hMap);
144 compareByHIterator(uMap, hMap);
145 populateByRandomIntKeys(uMap, hMap, testSize);
146 compareByUIterator(uMap, hMap);
147 compareByHIterator(uMap, hMap);
148 depopulateRandomly(uMap, hMap, 20);
149 compareByUIterator(uMap, hMap);
150 compareByHIterator(uMap, hMap);
151 populateByRandomIntKeys(uMap, hMap, testSize);
152 compareByUIterator(uMap, hMap);
153 compareByHIterator(uMap, hMap);
154 depopulateRandomly(uMap, hMap, 20);
155 populateBySerialIntKeys(uMap, hMap, testSize);
156 compareByUIterator(uMap, hMap);
157 compareByHIterator(uMap, hMap);
158 } catch (Exception e) {
159 failed = true;
160 }
161
162 assertTrue(!failed);
163 }
164
165 public void testDoubleIntLookup() throws Exception {
166
167 boolean failed = false;
168 int testSize = 512;
169 org.hsqldb.lib.IntKeyHashMap hIntMap =
170 new org.hsqldb.lib.IntKeyHashMap();
171 DoubleIntIndex intLookup = new DoubleIntIndex(12, false);
172
173 try {
174 intLookup.setKeysSearchTarget();
175 populateBySerialIntKeysInt(intLookup, hIntMap, testSize);
176 compareByHIteratorInt(intLookup, hIntMap);
177 populateByRandomIntKeysInt(intLookup, hIntMap, testSize);
178 compareByHIteratorInt(intLookup, hIntMap);
179 } catch (Exception e) {
180 failed = true;
181 }
182
183 assertTrue(!failed);
184 }
185
186 public void testDoubleIntSpeed() throws Exception {
187
188 boolean failed = false;
189 int testSize = 500;
190 org.hsqldb.lib.IntKeyHashMap hIntMap =
191 new org.hsqldb.lib.IntKeyHashMap();
192 DoubleIntIndex intLookup = new DoubleIntIndex(testSize, false);
193
194 intLookup.setKeysSearchTarget();
195 populateByRandomIntKeysInt(intLookup, hIntMap, testSize);
196 compareByHIteratorInt(intLookup, hIntMap);
197
198 int[] sample = getSampleIntArray(intLookup, 100);
199 int[] sampleVals = new int[sample.length];
200 int i = 0;
201 int j = 0;
202 StopWatch sw = new StopWatch();
203
204 try {
205 for (j = 0; j < 10000; j++) {
206 for (i = 0; i < sample.length; i++) {
207 int pos = intLookup.findFirstEqualKeyIndex(sample[i]);
208
209 sampleVals[i] = intLookup.getValue(pos);
210
211 intLookup.remove(pos);
212 }
213
214 for (i = 0; i < sample.length; i++) {
215 intLookup.addUnique(sample[i], sampleVals[i]);
216 }
217 }
218
219 System.out.println(
220 sw.elapsedTimeToMessage("Double int table times"));
221 intLookup.findFirstEqualKeyIndex(0); compareByHIteratorInt(intLookup, hIntMap);
223 } catch (Exception e) {
224 System.out.println(
225 sw.elapsedTimeToMessage("Double int table error: i =" + i));
226
227 failed = true;
228 }
229
230 assertTrue(!failed);
231 }
232
233 int[] getSampleIntArray(org.hsqldb.lib.DoubleIntIndex index, int size) {
234
235 int[] array = new int[size];
236 org.hsqldb.lib.IntKeyHashMap map = new org.hsqldb.lib.IntKeyHashMap();
237
238 for (; map.size() < size; ) {
239 int pos = nextIntRandom(randomgen, index.size());
240
241 map.put(pos, null);
242 }
243
244 org.hsqldb.lib.Iterator it = map.keySet().iterator();
245
246 for (int i = 0; i < size; i++) {
247 int pos = it.nextInt();
248
249 array[i] = index.getKey(pos);
250 }
251
252 return array;
253 }
254
255 void populateBySerialIntKeys(java.util.HashMap uMap,
256 org.hsqldb.lib.HashMap hMap,
257 int testSize) throws Exception {
258
259 for (int i = 0; i < testSize; i++) {
260 int intValue = randomgen.nextInt();
261
262 uMap.put(new Integer (i), new Integer (intValue));
263 hMap.put(new Integer (i), new Integer (intValue));
264
265 if (uMap.size() != hMap.size()) {
266 throw new Exception ("HashMap size mismatch");
267 }
268 }
269 }
270
271 void populateBySerialIntKeysInt(java.util.HashMap uMap,
272 org.hsqldb.lib.IntKeyHashMap hMap,
273 int testSize) throws Exception {
274
275 for (int i = 0; i < testSize; i++) {
276 int intValue = randomgen.nextInt();
277
278 uMap.put(new Integer (i), new Integer (intValue));
279 hMap.put(i, new Integer (intValue));
280
281 if (uMap.size() != hMap.size()) {
282 throw new Exception ("HashMap size mismatch");
283 }
284 }
285 }
286
287 void populateBySerialIntKeysInt(DoubleIntIndex intLookup,
288 org.hsqldb.lib.IntKeyHashMap hMap,
289 int testSize) throws Exception {
290
291 for (int i = 0; i < testSize; i++) {
292 int intValue = randomgen.nextInt();
293
294 intLookup.addUnique(i, intValue);
295 hMap.put(i, new Integer (intValue));
296
297 if (intLookup.size() != hMap.size()) {
298 throw new Exception ("HashMap size mismatch");
299 }
300 }
301 }
302
303 void populateByRandomIntKeysInt(DoubleIntIndex intLookup,
304 org.hsqldb.lib.IntKeyHashMap hMap,
305 int testSize) throws Exception {
306
307 for (int i = 0; i < testSize; i++) {
308 int intValue = randomgen.nextInt();
309
310 intLookup.addUnique(intValue, i);
311 hMap.put(intValue, new Integer (i));
312
313 if (intLookup.size() != hMap.size()) {
315 throw new Exception ("Duplicate random in int lookup");
316 }
317 }
318 }
319
320 void populateByRandomIntKeys(java.util.HashMap uMap,
321 org.hsqldb.lib.HashMap hMap,
322 int testSize) throws Exception {
323
324 for (int i = 0; i < testSize; i++) {
325 int intValue = randomgen.nextInt();
326
327 uMap.put(new Integer (intValue), new Integer (i));
328 hMap.put(new Integer (intValue), new Integer (i));
329
330 if (uMap.size() != hMap.size()) {
331 throw new Exception ("HashMap size mismatch");
332 }
333 }
334 }
335
336 void populateByRandomIntKeysInt(java.util.HashMap uMap,
337 org.hsqldb.lib.IntKeyHashMap hMap,
338 int testSize) throws Exception {
339
340 for (int i = 0; i < testSize; i++) {
341 int intValue = randomgen.nextInt();
342
343 uMap.put(new Integer (intValue), new Integer (i));
344 hMap.put(intValue, new Integer (i));
345
346 if (uMap.size() != hMap.size()) {
347 throw new Exception ("HashMap size mismatch");
348 }
349 }
350 }
351
352 void depopulateRandomly(java.util.HashMap uMap,
353 org.hsqldb.lib.HashMap hMap,
354 int testCount) throws Exception {
355
356 int removeCount = 0;
357 int size = uMap.size();
358
359 if (testCount > size / 2) {
360 testCount = size / 2;
361 }
362
363 while (removeCount < testCount) {
364 java.util.Iterator uIt = uMap.keySet().iterator();
365
366 for (int i = 0; uIt.hasNext(); i++) {
367 Object uKey = uIt.next();
368 int intValue = randomgen.nextInt(size);
369
370 if (intValue == i) {
371 uIt.remove();
372 hMap.remove(uKey);
373
374 removeCount++;
375 }
376
377 if (uMap.size() != hMap.size()) {
378 throw new Exception ("HashMap size mismatch");
379 }
380 }
381 }
382 }
383
384 void depopulateByIterator(java.util.HashMap uMap,
385 org.hsqldb.lib.HashMap hMap,
386 int testCount) throws Exception {
387
388 org.hsqldb.lib.Iterator hIt = hMap.keySet().iterator();
389
390 System.out.println(uMap.size());
391
392 for (int i = 0; hIt.hasNext(); i++) {
393 Object key = hIt.next();
394 int check = randomgen.nextInt(2);
395
396 if (check == i % 2) {
397 hIt.remove();
398 uMap.remove(key);
399 }
400
401 if (uMap.size() != hMap.size()) {
402 throw new Exception ("HashMap size mismatch");
403 }
404 }
405
406 System.out.println(uMap.size());
407 }
408
409 void depopulateByIntIterator(java.util.HashMap uMap,
410 org.hsqldb.lib.IntKeyHashMap hIntMap,
411 int testCount) throws Exception {
412
413 org.hsqldb.lib.Iterator hIt = hIntMap.keySet().iterator();
414
415 System.out.println(uMap.size());
416
417 for (int i = 0; hIt.hasNext(); i++) {
418 Object key = new Integer (hIt.nextInt());
419 int check = randomgen.nextInt(2);
420
421 if (check == i % 2) {
422 hIt.remove();
423 uMap.remove(key);
424 }
425
426 if (uMap.size() != hIntMap.size()) {
427 throw new Exception ("HashMap size mismatch");
428 }
429 }
430
431 System.out.println(uMap.size());
432 }
433
434 void clearByIntIterator(java.util.HashMap uMap,
435 org.hsqldb.lib.IntKeyHashMap hIntMap)
436 throws Exception {
437
438 org.hsqldb.lib.Iterator hIt = hIntMap.keySet().iterator();
439
440 System.out.println(uMap.size());
441
442 for (int i = 0; hIt.hasNext(); i++) {
443 Object key = new Integer (hIt.nextInt());
444
445 hIt.remove();
446 uMap.remove(key);
447
448 if (uMap.size() != hIntMap.size()) {
449 throw new Exception ("HashMap size mismatch");
450 }
451 }
452
453 System.out.println(uMap.size());
454 }
455
456 void compareByUIterator(java.util.HashMap uMap,
457 org.hsqldb.lib.HashMap hMap) throws Exception {
458
459 java.util.Iterator uIt = uMap.keySet().iterator();
460
461 for (int i = 0; uIt.hasNext(); i++) {
462 Object uKey = uIt.next();
463 Object oU = uMap.get(uKey);
464 Object hU = hMap.get(uKey);
465
466 if (!oU.equals(hU)) {
467 throw new Exception ("HashMap value mismatch");
468 }
469 }
470 }
471
472 void compareByHIterator(java.util.HashMap uMap,
473 org.hsqldb.lib.HashMap hMap) throws Exception {
474
475 org.hsqldb.lib.Iterator hIt = hMap.keySet().iterator();
476
477 for (int i = 0; hIt.hasNext(); i++) {
478 Object hKey = hIt.next();
479 Object oU = uMap.get(hKey);
480 Object hU = hMap.get(hKey);
481
482 if (!oU.equals(hU)) {
483 throw new Exception ("HashMap value mismatch");
484 }
485 }
486 }
487
488 void compareByUIteratorInt(java.util.HashMap uMap,
489 org.hsqldb.lib.IntKeyHashMap hMap)
490 throws Exception {
491
492 java.util.Iterator uIt = uMap.keySet().iterator();
493
494 for (int i = 0; uIt.hasNext(); i++) {
495 Object uKey = uIt.next();
496 Object oU = uMap.get(uKey);
497 Object hU = hMap.get(((Integer ) uKey).intValue());
498
499 if (!oU.equals(hU)) {
500 throw new Exception ("HashMap value mismatch");
501 }
502 }
503 }
504
505 void compareByHIteratorInt(java.util.HashMap uMap,
506 org.hsqldb.lib.IntKeyHashMap hMap)
507 throws Exception {
508
509 org.hsqldb.lib.Iterator hIt = hMap.keySet().iterator();
510
511 for (int i = 0; hIt.hasNext(); i++) {
512 Object hKey = new Integer (hIt.nextInt());
513 Object oU = uMap.get(hKey);
514 Object hU = hMap.get(((Integer ) hKey).intValue());
515
516 if (!oU.equals(hU)) {
517 throw new Exception ("HashMap value mismatch");
518 }
519 }
520 }
521
522 void compareByHIteratorInt(DoubleIntIndex intLookup,
523 org.hsqldb.lib.IntKeyHashMap hMap)
524 throws Exception {
525
526 org.hsqldb.lib.Iterator hIt = hMap.keySet().iterator();
527
528 for (int i = 0; hIt.hasNext(); i++) {
529 int hK = hIt.nextInt();
530 int lookup = intLookup.findFirstEqualKeyIndex(hK);
531 int lV = intLookup.getValue(lookup);
532 Integer hV = (Integer ) hMap.get(hK);
533
534 if (hV.intValue() != lV) {
535 throw new Exception ("HashMap value mismatch");
536 }
537 }
538 }
539
540 int nextIntRandom(Random r, int range) {
541
542 int b = Math.abs(r.nextInt());
543
544 return b % range;
545 }
546
547 public static void main(String [] argv) {
548
549 try {
550 TestHashStructures test = new TestHashStructures("testHashMap");
551
552 test.testHashMap();
553 test.testIntKeyHashMap();
554 test.testHashMappedList();
555 test.testDoubleIntLookup();
556 test.testDoubleIntSpeed();
557 } catch (Exception e) {
558 e.printStackTrace();
559 }
560 }
561 }
562 |
Popular Tags |
Java API By Example, From Geeks To Geeks.