import java.util.*; import java.io.*; /** * * @author Sriram Pemmaraju * @date Nov 13th, 2008, modified on Nov 15th */ public class wordList{ private wordPair[] hashTable; // an array of wordPair objects used as a hash table private int M; // the size of the hash table private int numWords; // number of words in the has table private int numProbes; // keeps track of the total number of probes performed // the only purpose of this is to generate statistics on // average number of probes performed per insertion private int maxProbes; // keeps track of the maximum number of probes // made for any insertion /** * The default constructor assumes, somewhat arbitrarly that the user is interested * in inserting 20 words into the table. I want to define a table 5 times that size, * so I use the prime 101 as the table size. */ public wordList() { M = 101; // M is assigned a prime number about 5 times 20 hashTable = new wordPair[M]; // the default values of all slots is null numWords = 0; numProbes = 0; maxProbes = 0; } /** * This constructor is given the number of words t the user expects to insert into the * table. We want to pick a prime, just more than 5*t, as the hash table size * * @param: an int t that is the number of words that the user expects to place * in the hash table */ public wordList(int t) { M = getPrime(5*t); // this returns the smallest prime number >= 5*t hashTable = new wordPair[M]; // the default values of all slots is null numWords = 0; numProbes = 0; maxProbes = 0; } /** * This returns the smallest prime at least as large as the given parameter x * * @param: an int x that is a lower bound on the prime number returned */ private int getPrime(int x) { // Currently this is dummy code return x; } /** * A private method that expands the hashTable to twice its size and * rehashes all of the words into the new table. * * @param currentTable is the current hash table * @param newSize is the size we want to expand this hash table to * @return a new hash table twice as large as the old hash table */ private wordPair[] resize(wordPair[] currentTable, int newSize) { // A temporary hash table, whose size is specified by new size wordPair[] temp = new wordPair[newSize]; // Scan the slots of the old hash table for(int i = 0; i < hashTable.length; i++) { // If the ith slot is non-empty if(hashTable[i] != null) { int probe = 0; while(true){ // Find the index of the slot being probed String myWord = hashTable[i].getWord(); int slotIndex = hash(myWord, probe); // check if slot is empty if(temp[slotIndex] == null) { temp[slotIndex] = new wordPair(myWord); break; } probe++; } // end of while-loop } // end of if slot is non-empty } // end of for-loop // Return the expanded table return temp; } // end of resize /** * A private method that computes the hash value of a given string. * Assumes that the string consists of lower case letters, upper case letters, and * digits. Views the string as a base-32 number and returns equivalent * decimal value modulo 32. Uses bit shifting for multiplying * by 32 and Horner's rule for reducing number of multiplications * * @param s is the String whose hash value needs to be computed * @return an int value in the range 0..M-1 that is the hash value * of the given string s */ private int hash(String s) { int hashValue = 0; for(int i = 0; i < s.length(); i++) { // Also note that we are now bit-shifting by 2 to the 6th or 64. // Consider digits and map these to values in the range 1 - 10 if((s.charAt(i) >= '0') && (s.charAt(i) <= '9')) hashValue = ((hashValue << 6) + (s.charAt(i) - '0') + 1) % M; // Consider upper case characters and map these to values in the range 11 - 36 else if((s.charAt(i) >= 'A') && (s.charAt(i) <= 'Z')) hashValue = ((hashValue << 6) + (s.charAt(i) - 'A') + 11) % M; // Consider lower case characters and map these to values in the range 37 - 62 else if((s.charAt(i) >= 'a') && (s.charAt(i) <= 'z')) hashValue = ((hashValue << 6) + (s.charAt(i) - 'a') + 37) % M; } // end of for-loop return hashValue; } /** * A private method that computes the index at which the ith quadratic probe into * a hashtable of size M needs to be performed. The method returns the computed index. * * @param: s, the string for whom a slot is being probed * @return: the slot index at which the ith probe should be performed */ private int hash(String s, int i) { // I use a long variable to avoid possible overflow long square = i*i; // Use the quadratic probing formula (h(s) + i^2)%M int slotIndex = (int)((hash(s) + square) % (long) M); return slotIndex; } /** * This function inserts the given myWord into the hash table. * @param a given word called myWord that needs to be inserted into the hash table */ public void insert(String myWord) { int probe = 0; // this is the probe number int slotIndex; // this is the index of the slot being probed // This is just for error-checking and should be commented // out in the typical running mode //System.out.println("word being inserted: " + myWord); // This is the loop that repeatedly probes the hash table // until an empty slot has been found. We are always guaranteed // to find an empty slot; so it is ok to do this with a while-true // and break out when successful while(true){ // Find the index of the slot being probed slotIndex = hash(myWord, probe); // This is just for error-checking and should be commented // out in the typical running mode //System.out.println("slot index: " + slotIndex); // check if slot is empty if(hashTable[slotIndex] == null) { hashTable[slotIndex] = new wordPair(myWord); numWords++; // maxProbes is being updated just for reporting statistics if(probe > maxProbes) maxProbes = probe; // This is just for error-checking and should be commented // out in the typical running mode //System.out.println("Inserted word."); break; } // check if slot contains the word we are trying to insert // In this case we are done and we exit after updating maxProbes else if(myWord.equals(hashTable[slotIndex].getWord())) { // maxProbes is being updated just for reporting statistics if(probe > maxProbes) maxProbes = probe; // This is just for error-checking and should be commented // out in the typical running mode //System.out.println("Word already in table."); break; } probe++; numProbes++; // this is being updated just for reporting // statistics } // Check to see if the number of words in the hash table is more than half the // size of the hash table. If so, it is time to double the hash table // and rehash all the words in it. This is a fairly expensive operation if(numWords > hashTable.length/2) { // This is just for error-checking and should be commented // out in the typical running mode //System.out.println("Doubling the hash table. Old size = " + M); M = 2*M; hashTable = resize(hashTable, M); } } /** * @param a given word called myWord that needs to be searched for in the hash table * @return true if myWord is found in the hash table, false otherwise */ public boolean search(String myWord) { int slotIndex; // this is the index of the slot being probed // This is the loop that repeatedly probes the hash table // until the word we are looking for has been found or we // know for sure that there is no hope of finding the word // The fact that it is enough to use probe values from 0 through // (M-1)/2 is because it is known that for the probing function we are // using, the slot indices for these probe values will be distinct. // Since our table is at least half empty, every insertion succeeds // with probe values between 0..(M-1)/2 and therefore if myWord exists // in the table, it will found using just this many probe values. for(int probe = 0; probe <= (M-1)/2; probe++) { // Find the index of the slot being probed slotIndex = hash(myWord, probe); // check if slot is empty; in this case myWord cannot be in // the hashTable if(hashTable[slotIndex] == null) return false; if(myWord.equals(hashTable[slotIndex].getWord())) return true; } return false; } /** * @return: the number of words in the hash table. Runs in constant time */ public int numberWords() { return numWords; } /** * @return: the size of the hash table. Runs in constant time */ public int size() { return hashTable.length; } /** * @return: the average number of probes performed per insertion or * per word in the hash table */ public double averageNumberOfProbes() { return (numProbes*1.0)/(numWords*1.0); } /** * @return: the maximum number of probes performed over all insertions */ public double maxNumberOfProbes() { return maxProbes; } /** * Copies the strings in the hash table into an array of strings * in which the strings appear in contiguous slots and the size * of the array is exactly the number of strings in the hash table * * @return: the array of String objects */ String[] copyIntoArray() { // Make a new String[] to copy the words into String[] wordArray = new String[numWords]; // Counter for the wordArray int count = 0; // Scan the hash table and pick out words for(int i = 0; i < hashTable.length; i++) if(hashTable[i] != null) wordArray[count++] = hashTable[i].getWord(); return wordArray; } /** * Prints the words in the hash table in alphabetical order */ public void sortedPrint() { // Copy the strings in the hash table into an array of strings // in which the strings appear in contiguous slots and the size // of the array is exactly the number of strings in the hash table String[] wordArray = copyIntoArray(); // Just call the sort method in the Arrays class Arrays.sort(wordArray); for(int i = 0; i < wordArray.length; i++) System.out.println(wordArray[i]); } /** * Prints the words in the hash table into a file with name fileName in * alphabetical order */ public void sortedPrint(String fileName) { // Currently a dummy function; does nothing System.out.println("Inside sortedPrint(fileName)"); } }