1    package collections.buckettest; 
2     
3    import java.util.ArrayList; 
4    import java.util.List; 
5     
6    /** 
7     * Demonstrates the affect that hash code values 
8     * and initial capacity have on collisions in a HashMap. 
9     * 
10    * @author Thomas Rowland 
11    */ 
12   public class SimpleBucketTest { 
13       static Object[] buckets;    //array of buckets 
14    
15       //-- Test data - key Objects 
16       static Integer[] keyvalues = {new Integer(0), 
17                                     new Integer(1), 
18                                     new Integer(2), 
19                                     new Integer(7), 
20                                     new Integer(15), 
21                                     new Integer(16), 
22                                     new Integer(17), 
23                                     new Integer(31), 
24                                     new Integer(32), 
25                                     new Integer(33), 
26                                     new Integer(47), 
27                                     new Integer(48), 
28                                     new Integer(49), 
29                                     new Integer(62), 
30                                     new Integer(63), 
31                                     new Integer(64), 
32                                     new Integer(101), 
33                                     new Integer(102), 
34                                     new Integer(103)}; 
35    
36       public static void main(String[] args) { 
37           // test for different initial capacity values 
38           runTest(20); 
39           runTest(33); 
40           runTest(65); 
41           runTest(129); 
42       } 
43    
44       private static void runTest(int initialCapacity) { 
45           //-- Test initial capacity of array of buckets 
46           System.out.println( 
47                   "\nSpecified Initial Capacity = " + initialCapacity); 
48           createArray(initialCapacity); 
49           System.out.println( 
50                   "Real Initial Capacity = " + buckets.length); 
51    
52           //-- Test index of each populated bucket 
53           List indices = new ArrayList(); 
54           int collisionCount = 0; 
55    
56           System.out.println("key " + "\thashcode " + "\tindex"); 
57           for (int i = 0; i < keyvalues.length; i++) { 
58               Integer k = keyvalues[i]; 
59               int h = k.hashCode(); 
60               int modh = hash(k); 
61               int idx = indexFor(modh, buckets.length); 
62               if (indices.contains(new Integer(idx))) 
63                   collisionCount++;   //collision 
64               indices.add(new Integer(idx)); 
65    
66               System.out.println(k + "\t" + h 
67                       + "\t\t" + idx); 
68           } 
69           System.out.println("Collisions: " 
70                   + collisionCount); 
71       } 
72    
73       /** 
74        * Creates an array with a capacity 
75        * of a power of 2 >= initialCapacity 
76        */ 
77       static void createArray(int initialCapacity) { 
78           int capacity = 1; 
79           while (capacity < initialCapacity) { 
80               capacity <<= 1; 
81           } 
82           buckets = new Object[capacity]; 
83       } 
84    
85       /** 
86        * Returns index for hash code h. 
87        */ 
88       static int indexFor(int h, int length) { 
89           return (h & (length - 1)); 
90       } 
91    
92       /** 
93        * Returns a hash value for the specified object. 
94        * In addition to the object's own hashCode, this 
95        * method applies a "supplemental hash function," 
96        * which defends against poor quality hash functions. 
97        */ 
98       static int hash(Object key) { 
99           int h = key.hashCode(); 
100   
101          h += ~(h << 9); 
102          h ^= (h >>> 14); 
103          h += (h << 4); 
104          h ^= (h >>> 10); 
105          return h; 
106      } 
107  } 
108   
109