Task: Implementation of the ProbeHashTable class with linear probing. The templa

Question

Task: Implementation of the ProbeHashTable class with linear probing.
The template of ProbeHashTable class and relevant classes are given below:

Requirements:

Implement the ProbeHashMap class as we discussed in the lectures.

Your implementation has to follow the specification given. Any other implementation (there are tons of HashTable code on the Internet) will not receive any credit.

Test: write a test program to create a hash table with the default size. Insert 100 data items (random strings) and then remove 10 of them. Finally, please print out the remaining items in the hash table. Note that your implementation will be evaluated by a specific test program while being graded.

Bonus: 10 point bonus will be given for those implementation that prints out the number collisions while the 100 data items are inserted into the hash table. Hint: to do that, you may want to change the return type of the put() method to int type, which is the number of collisions. Your README file must state the bonus option you are taking to earn the bonus.

Explanation / Answer

SOLUTION:

According to the given data the below code follows

àJAVA HASHTABLE:

import java.io.*;
class StringDataItem
{
   private String sData;
   public StringDataItem(String ss)
       {
sData = ss;
       }   
   public String getKey()
       { return sData; }
}

class StringHashTable

{
   private StringDataItem[] hashArray;
   private int arraySize;
   private StringDataItem nonItem;
  
   public StringHashTable(int size)
   {
       arraySize = size;
       hashArray = new StringDataItem[arraySize];
       nonItem = new StringDataItem("-"); //dash IS deleted
       for(int i = 0; i < size; i++)
           hashArray[i] = new StringDataItem(nonItem.getKey());
   }
  
   public void displayTable()
   {
       System.out.print("Table: ");
       for(int j = 0; j < arraySize; j++)
       {
           if(hashArray[j] != null)
               System.out.print(hashArray[j].getKey() + " ");
           else
               System.out.print("** ");
       }
       System.out.println("");
   }
  
  
   public int hashFunc(String key)
   {
       int hashVal = 0;
       for(int j = 0; j<key.length(); j++)
       {
           int letter = key.charAt(j);
           hashVal = (hashVal * 27 + letter) % arraySize;
       }
       return hashVal;
   }
  
   public void insert(StringDataItem item)
   {
       //assumes table not full
       String key = item.getKey();
       int hashVal = hashFunc(key);
       while(hashArray[hashVal].getKey() != "-")
       {
           ++hashVal;
           hashVal %= arraySize;
       }
       hashArray[hashVal] = item;
   }
  
   public StringDataItem delete(String key)
   {
       int hashVal = hashFunc(key);
      
       while(hashArray[hashVal].getKey() != "-" && hashArray[hashVal].getKey() != null)
       {
           if(hashArray[hashVal].getKey().equals(key))
           {
               StringDataItem temp = hashArray[hashVal];
               hashArray[hashVal] = nonItem;
               return temp;
           }
           ++hashVal;
           hashVal %= arraySize;
       }
       return null;
   }
  
   public StringDataItem find(String key)
   {
       int hashVal = hashFunc(key);
       while(hashArray[hashVal].getKey() != "-" && hashArray[hashVal].getKey() != null)
       {
           if(hashArray[hashVal].getKey().equals(key))
               return hashArray[hashVal];
           ++hashVal;
           hashVal %= arraySize;
       }
       return null;
   }
} //end class HashTable

class StringHashTableApp
{
   public static void main(String[] args) throws IOException
   {
       StringDataItem aDataItem;
       int size, n, keysPerCell;
       String aKey;
      
       System.out.print("Enter size of hash table: ");
       size = getInt();
       System.out.print("Enter initial number of items: ");
       n = getInt();
       keysPerCell = 10;
      
       StringHashTable theHashTable = new StringHashTable(size);
      
       for(int j=0; j<n; j++)
       {
           aKey = Double.toString((java.lang.Math.random() * keysPerCell * size));
           aDataItem = new StringDataItem(aKey);
           theHashTable.insert(aDataItem);
       }
      
       while(true)
       {
           System.out.print("Enter first letter of show, insert, delete, or find: ");
           char choice = getChar();
           switch(choice)
           {
           case 's':
               theHashTable.displayTable();
               break;
           case 'i':
               System.out.print("Enter string to insert: ");
               aKey = getString();
               aDataItem = new StringDataItem(aKey);
               theHashTable.insert(aDataItem);
               break;
           case 'd':
               System.out.print("Enter string to delete: ");
               aKey = getString();
               theHashTable.delete(aKey);
               break;
           case 'f':
               System.out.print("Enter string to find: ");
               aKey = getString();
               aDataItem = theHashTable.find(aKey);
               if(aDataItem != null)
                   System.out.println("Found " + aKey);
               else
                   System.out.println("Could not find " + aKey);
               break;
           default:
               System.out.println("Invalid entry!");
           }
       }
   }//end main
  
   public static String getString() throws IOException
   {
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader br = new BufferedReader(isr);
       String s = br.readLine();
       return s;
   }
  
   public static char getChar() throws IOException
   {
       String s = getString();
       return s.charAt(0);
   }
  
   public static int getInt() throws IOException
   {
       String s = getString();
       return Integer.parseInt(s);
   }
} //end HashTable

Therefore by using the above code we can get our required output

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.