/*
 * Author: Sriram Pemmaraju
 * Date: September 29, 2008
 * This is a simple implementation of hashing with chaining
 */

public class ChainingHashTable {

   private StringLinkList[] hashArray;  // array of singly linked lists of strings
   private int M;			// size of the hash table	


/**
 * Constructor for the ChainingHashTable class
 * 
 * @param n is the user's expectation of how many items they expect to store 
 */
 public ChainingHashTable(int n) {

	M = n/3;	// allows for a load factor of 3
      	hashArray = new StringLinkList[M];  	// create hash table 
	
	// Fill each individual slot in the hash table array with empty
	// linked lists
      	for(int j = 0; j < M; j++)          		// fill array
         	hashArray[j] = new StringLinkList();  	// with empty lists
      }


/**
 * Displays the contents of the hash table
 * 
 */
 public void displayTable() {
	// Scan each slot in the hash table
      	for(int j = 0; j < M; j++) {
         	System.out.print(j + ". "); // display cell number
         	hashArray[j].displayList(); // display list
         }
      }

/**
 * Prints the size-distribution of the linked lists in the different slots of the table
 * 
 */
 public void printDistribution() {

	// First scan each slot in the hash table to compute the total number of elements
	// in the hash table
	int sum = 0;
      	for(int j = 0; j < M; j++) 
		sum += hashArray[j].size();

	// The length of a list can range from 0 to sum, though it is quite unlikely that
	// there will be lists as long as sum. We expect each list to have size 3, so let us
	// report the number of lists that have sizes 0, 1, 2,..., 10, and more than 10.
	// The next loop computes the distribution
	int[] distribution = new int[12];
	for(int j = 0; j < M; j++)
	{
		int size = hashArray[j].size();
		if(size > 10)
			distribution[11]++;
		else
			distribution[size]++;
	}

	// Print the distribution
	for(int j  = 0; j < 12; j++)
		System.out.println(distribution[j]);
	
      }
		


/**
 * Computes the hash value of a given string. 
 * Assumes that the string consists of lower case letters, upper case letters, and 


/**
 * 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
 */
 public 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;

         }

         return hashValue;
 }


/**
 * Inserts a given string into the hash table.
 * 
 * @param s is the String which needs to be inserted into the hash table
 */
 public void insert(String s) {
      int hashVal = hash(s);   		// computes the hash value of the given string 
      hashArray[hashVal].insertFirst(s); 	// insert s into the linked list stored at hashVal
      }  // end insert()


/**
 * Deletes the given string into the hash table.
 * 
 * @param s is the String which needs to be deleted from the hash table
 */
  public void delete(String s) {
      int hashVal = hash(s);   	// computes the hash value of the given string
      hashArray[hashVal].delete(s); 	// delete s from the linked list stored at hashVal
  }  // end delete()


/**
 * Finds the given string into the hash table.
 * 
 * @param s is the String which needs to be found in the hash table
 * @return the StringLink object that contains s is returned if
 *         s is in the table; otherwise null is returned
 */
   public StringLink search(String s) {
      int hashVal = hash(s);   		// computes the hash value of the given string
      return hashArray[hashVal].find(s);  	// looks for s in the linked list at hashVal
   }
}  // end class ChainingHashTable