CODED IN JAVA. USE HORNER\'S HASHING RULE AS NOTED BELOW. 1 Objective Build a ha

Question

CODED IN JAVA. USE HORNER'S HASHING RULE AS NOTED BELOW.

1 Objective Build a hash table that supports searching, insertion, deletion, printing, and integer hash key creation based on text or string input data. In the event of collisions, this separate chaining hash table will use a singly linked list to store duplicate keys 2 Requirements 1. Read the input file formatted as follows. The input file will contain at least one command per line, either insert, delete, search, print, or quit. These are defined in detail below. And if appropriate, a second parameter may be required. This string would contain a name, typically, less than seven characters. This name will be the data used to generate the hash. For example, one of the input files, named 5inserts.txt contains the following: i homer i marge i nelson i gloria i duffman 2. The specific commands are i for insert, d for delete s for search p for print, and q for quit (a) Insert The insert command uses the single character i as the command token. The com mand token will be followed by a single space, then the name which will be the characters used to calculate the hash key as defined below. The program will then insert the key and the data in the hash table. In the event that there is a duplicate key, the new key (and data) would be added to the appropriate slot's linked list. This command's success can be verified by using the print command (b) Delete The delete command uses the single character d as the command token. The command token will be followed by a single space, then the name which will

Explanation / Answer

I have coded the problem in Java, generating the output as shown in the example. There are necessary comments in the code for you to clarify.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

class Node{
   public String data;   //stores the string data for a particular node
   public Node next;   //stores a reference/pointer to the next node in the list
  
   public Node(String x){   //constructor to initialize defaults
       data=x;
       next=null;
   }
}

class LinkedList{
  
   private Node head;   //pointer to the head of the linked list
  
   public LinkedList(){
       head=null;
   }
  
   public void insert(String x){   //function to insert string into a linked list
       if(head==null){
           head = new Node(x);
           return;
       }
      
       /*
       * Travel to end of the list and append the new list node
       */
       Node temp=head;
       while(temp.next!=null)
           temp=temp.next;
       temp.next = new Node(x);
   }
  
   public int delete(String x){   //function to delete string from a linked list
       /*
       * If string is found and deleted, the function returns 1
       * Else -1.
       */
       if(head==null){
           return -1;
       }
       int found=0;
       Node temp = head,prev=null;
      
       while(temp!=null){
           if(temp.data.equals(x)){
               found=1;
               break;
           }
           prev=temp;
           temp=temp.next;
       }
      
       if(found==1){
           if(prev==null){
               temp = head;
               head=head.next;
               temp=null;
           }else{
               prev.next=temp.next;
               temp=null;
           }
           return 1;
       }
       return -1;
   }
  
   public int search(String x){   //function to search string in a linked list
       /*
       * If string is found and deleted, the function returns 1
       * Else -1.
       */
       if(head==null){
           return -1;
       }
      
       Node temp = head;
      
       while(temp!=null){
           if(temp.data.equals(x)){
               return 1;
           }
           temp=temp.next;
       }
      
       return -1;
   }
  
   public void print(int slot){       //print the whole contents of a linked list
       if(head==null)
           return;
       Node temp = head;
       while(temp!=null){
           System.out.print(Integer.toString(slot) + "/" + temp.data + ";");
           temp=temp.next;
       }
   }
  
}

class HashHandler{
  
   LinkedList list[];
   public int size;
  
   public HashHandler(int n){
       list = new LinkedList[n];
       size = n;
       for(int i=0;i<size;i++){
           list[i] = new LinkedList();
       }
   }
  
   public int getKeyIndex(String x){   //HashCode using Horner's Rule
       int h=0,C=27;
       for(int i=0;i<x.length();i++){
           h=( (h * C)%size + (x.charAt(i)-96)%size )%size;
       }
       return h;
   }
  
   public void insert(String x){
       int idx = getKeyIndex(x);
       list[idx].insert(x);
   }
  
   public void delete(String x){
       int idx = getKeyIndex(x);
       if(list[idx].delete(x)==-1){
           //couldn't find the node to delete
           System.out.println("Couldn't delete the specified node.");
       }
   }
  
   public void search(String x){
       int idx = getKeyIndex(x);
       if(list[idx].search(x)==1){
           //successfully located
           System.out.println(Integer.toString(idx) + "/" + x);
       }else{
           System.out.println("Couldn't find the specified node.");
       }
   }
  
   public void print(){
      
       System.out.println("The Hash Table contains:");
       for(int i=0;i<size;i++){
           System.out.print(Integer.toString(i) + ". List (first->last): ");
           list[i].print(i);
           System.out.println();
       }
      
   }  
}

public class Solution {
  
   public static void main(String args[]){
       String fileName = args[1];
       int size=Integer.parseInt(args[0]);
       HashHandler hash = new HashHandler(5);
      
       Scanner sc=null;
       try {
           sc = new Scanner(new File(fileName));
       } catch (FileNotFoundException e) {
           e.printStackTrace();
       }
   while(sc.hasNext()){
   String s = sc.next();
  
   switch (s){
       case "i":{
           String data = sc.next();
           hash.insert(data);
           break;
       }
       case "d":{
           String data = sc.next();
           hash.delete(data);
           break;
       }
       case "s":{
           String data = sc.next();
           hash.search(data);
           break;
       }
       case "p":{
           hash.print();
           break;
       }
       case "q":{
           return;
       }
   }
   }
      
   }
  
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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