DictionaryReader.java

import java.io.*;

public class DictionaryReader
{
      public static final int DICTIONARY_SIZE = 125346;

      public static void main(String[] args) throws Exception
      {
         System.out.println("===== PART 1 =====");
         partOne();
         System.out.print("\n\n\n");
         System.out.println("===== PART 2 =====");
         partTwo();
      }

      private static void partOne() throws Exception
      {
         BufferedReader in =
            new BufferedReader(new FileReader("english"));

         int hashTableLength = getPrime((DICTIONARY_SIZE * 2) + 1);
         int[] hashTable = new int[hashTableLength];

         // Relying on all elements in hashTable automatically
         //   being initialized to 0

         String currentWord;
         while ((currentWord = in.readLine()) != null)
         {
            // Key difference between part 1 and 2
            hashTable[hash(currentWord, hashTableLength)] ++;
         }
         

         printInformation(hashTable);
      }

      private static void partTwo() throws Exception
      {
         BufferedReader in =
            new BufferedReader(new FileReader("english"));

         int hashTableLength = getPrime((DICTIONARY_SIZE * 2) + 1);
         int[] hashTable = new int[hashTableLength];

         // Relying on all elements in hashTable automatically
         //   being initialized to 0

         String currentWord;
         while ((currentWord = in.readLine()) != null)
         {
            // Key difference between part 1 and 2
            hashTable[Math.abs(currentWord.hashCode()) % hashTableLength] ++;
         }

         printInformation(hashTable);
      }

      public static void printInformation(int[] hashTable)
      {
         int numberOfBucketsWithCollisions = 0;

         int largestNumberOfCollisions = -1;
         int largestCollisionsIndex = 0;

         for (int currentBucketIndex = 0;
              currentBucketIndex < hashTable.length;
              currentBucketIndex ++)
         {
            int currentBucketValue = hashTable[currentBucketIndex];

            if (currentBucketValue > largestNumberOfCollisions)
            {
               largestNumberOfCollisions = currentBucketValue;
               largestCollisionsIndex = currentBucketIndex;
            }

            if (currentBucketValue >= 2)
            {
               numberOfBucketsWithCollisions ++;
            }
         }

         System.out.println("  " +largestNumberOfCollisions +
                            " collisions at hash code " +
                            largestCollisionsIndex);
         System.out.println("  " + numberOfBucketsWithCollisions +
                            " buckets have collisions");
      }

      // There are lots of ways to determine if a number is prime.
      // This is the most simple, but least efficient.
      private static int getPrime(int minCandidate)
      {
         final int INITIAL_DIVISOR = 2;

         int candidate = minCandidate;
         boolean isPrime = false;

         int currentDivisor = INITIAL_DIVISOR;

         // Sort of an "event driven" loop form
         while (!isPrime)
         {
            // We have tried every divisor from INITIAL_DIVISOR (2)
            //   to (candidate - 1)
            if (currentDivisor >= candidate)
            {
               isPrime = true;
            }
            // The candidate is divisible by the current divisor
            else if ((candidate % currentDivisor) == 0)
            {
               candidate ++;
               currentDivisor = INITIAL_DIVISOR;
            }
            // (currentDivisor < candidate) and candidate is
            //   not divisible by currentDivisor
            else
            {
               currentDivisor ++;
            }
         }

         return candidate;
      }



/*
      // WEISS HASH VERSION 1
      // Copied from Weiss (Figure 20.1 in the 2nd edition)
      private static int hash(String key, int tableSize)
      {
         int hashVal = 0;
         
         for (int i = 0; i < key.length(); i ++)
         {
            hashVal = ((hashVal * 128) + key.charAt(i)) % tableSize;
         }

         return hashVal;
      }
*/
      // WEISS HASH VERSION 2
      // Copied from Weiss (Figure 20.2 in the 2nd edition)
      private static int hash(String key, int tableSize)
      {
         int hashVal = 0;
         
         for (int i = 0; i < key.length(); i ++)
         {
            hashVal = (37 * hashVal) + key.charAt(i);
         }

         hashVal %= tableSize;
         if (hashVal < 0)
         {
            hashVal += tableSize;
         }

         return hashVal;
      }

}