1    /* 
2       Hash code tests and analytics. 
3     */
4    
5    import java.io.BufferedReader;
6    import java.io.FileReader;
7    import java.util.Arrays;
8    
9    public class Hashing {
10   
11      /* 
12         Private 
13       */
14   
15      private static final String FILE_NAME = "magicitems.txt";
16      private static final int LINES_IN_FILE = 666;
17      private static final int HASH_TABLE_SIZE = 250;
18   
19      private static int makeHashCode(String str) {
20         str = str.toUpperCase();
21         int length = str.length();
22         int letterTotal = 0;
23   
24         // Iterate over all letters in the string, totalling their ASCII values.
25         for (int i = 0; i < length; i++) {
26            char thisLetter = str.charAt(i);
27            int thisValue = (int)thisLetter;
28            letterTotal = letterTotal + thisValue;
29   
30            // Test: print the char and the hash.
31            /* 
32            System.out.print(" ["); 
33            System.out.print(thisLetter); 
34            System.out.print(thisValue); 
35            System.out.print("] "); 
36            // */
37         }
38   
39         // Scale letterTotal to fit in HASH_TABLE_SIZE.
40         int hashCode = (letterTotal * 1) % HASH_TABLE_SIZE;  // % is the "mod" operator
41         // TODO: Experiment with letterTotal * 2, 3, 5, 50, etc.
42   
43         return hashCode;
44      }
45   
46      private static void analyzeHashValues(int[] hashValues) {
47         System.out.println("\nHash Table Usage:");
48   
49         // Sort the hash values.
50         Arrays.sort(hashValues);  // This is a "dual-pivot" quicksort.
51                                   // See https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/DualPivotQuicksort.java
52                                   
53   
54         // Test: print the sorted hash values.
55         /* 
56         for (int i=0; i < LINES_IN_FILE; i++) { 
57            System.out.println(hashValues[i]); 
58         } 
59         // */
60   
61         // Create a histogram-like report based on the count of each unique hash value,
62         // count the individual entry size,
63         // the total space used (in items),
64         // and the standard deviation of their distribution over the hash table.
65         int asteriskCount = 0;
66         int[] bucketCount = new int[HASH_TABLE_SIZE];
67         int totalCount = 0;
68         int arrayIndex = 0;
69   
70         for (int i=0; i < HASH_TABLE_SIZE; i++) {
71            System.out.format("%03d ", i);
72            asteriskCount = 0;
73            while ( (arrayIndex < LINES_IN_FILE) && (hashValues[arrayIndex] == i) ) {
74               System.out.print("*");
75               asteriskCount = asteriskCount + 1;
76               arrayIndex = arrayIndex + 1;
77            }
78            System.out.print(" ");
79            System.out.println(asteriskCount);
80            bucketCount[i] = asteriskCount;
81            totalCount = totalCount + asteriskCount;
82         }
83   
84         System.out.print("Average load (count): ");
85         float averageLoad = (float) totalCount / HASH_TABLE_SIZE;
86         System.out.format("%.2f%n", averageLoad);
87   
88         System.out.print("Average load (calc) : ");
89         averageLoad = (float) LINES_IN_FILE / HASH_TABLE_SIZE;
90         System.out.format("%.2f%n", averageLoad);
91   
92         System.out.print("Standard Deviation: ");
93         // TODO: Refactor this into its own method.
94         double sum = 0;
95         for (int i=0; i < HASH_TABLE_SIZE; i++) {
96            // For each value in the array...
97            // ... subtract the mean from each one ...
98            double result = bucketCount[i] - averageLoad;
99            // ... and square the result.
100           double square = result * result;
101           // Sum all of those squares.
102           sum = sum + square;
103        }
104        // Divide the sum by the number of values ...
105        double temp = sum / HASH_TABLE_SIZE;
106        // ... and take the square root of that.
107        double stdDev = Math.sqrt(temp);
108        System.out.format("%.2f%n", stdDev);
109     }
110  
111     /* 
112        Public 
113      */
114  
115     public static void main(String[] args) {
116        System.out.println("Hash code tests and analysis.");
117        System.out.println("-----------------------------");
118  
119        String[] magicItems = new String[LINES_IN_FILE];
120        int[] hashValues = new int[LINES_IN_FILE];
121  
122        // Read the contents of FILE_NAME into our array of size LINES_IN_FILE.
123        int index = 0;
124        try {
125           BufferedReader br = new BufferedReader(new FileReader(FILE_NAME));
126           String line = "";
127           line = br.readLine();
128           while (line != null) {
129              magicItems[index] = line;
130              index = index + 1;
131              line = br.readLine();
132           }
133           br.close();
134        } catch (Exception ex) {
135           ex.printStackTrace();
136        }
137  
138        // Print the array and hash values.
139        int hashCode = 0;
140        for (int i = 0; i < LINES_IN_FILE; i++) {
141           System.out.print(i);
142           System.out.print(". " + magicItems[i] + " - ");
143           hashCode = makeHashCode(magicItems[i]);
144           System.out.format("%03d%n", hashCode);
145           hashValues[i] = hashCode;
146        }
147  
148        // Analyze the distribution of hash values.
149        analyzeHashValues(hashValues);
150     }
151  
152  }
153