Question

Implement a software program in C++ t stores and searches the Student records using double-hashing algorithm.  Double hashing uses the idea of applying a second hash function to key when a collision occurs.  

The software program will be based on the following requirements:

Development Environment:

• If the software program is written in C++, its project must be created using Microsoft Visual Studio 2017.
• If the software program is written in Java, its project must be created using NetBeans v8.2.

Algorithm:

• If Nis the maximum number of Student records to be inserted, then maximum number of slots for the hash table (TABLE_SIZE) will be N.
• The first hash function is defined as:
  • hashValue1 = (Key % TABLE_SIZE) – Where Key is the ID of the Student record (Refer to the Student class definition below)
• The second hash function is defined as:
  • hashValue2 = PRIME– (Key % PRIME) – Where PRIMEis a prime number smaller than the TABLE_SIZEand Key is the ID of the Student record (Refer to the Student class definition below)
  • For example, if TABLE_SIZEis 12, then PRIMEwill be 11.
• When the new Student record is to be inserted, the following steps will occur:
  1. A hash value (hashValue1) is computed using the first hash function.
  2. Using the computed hash value (hashValue1) as an index in the hash table, determine if there is a Student record previously inserted in this slot.
  3. If the slot is empty, insert the Student record into this slot.
  4. Otherwise, there is a collision.  Compute the new hash value (hashValue2) using the second hash function.  The new index will then be determined as:
     • (hashValue1 + (C * hasValue2)) % TABLE_SIZE

Where:

• C is the collision counter.  
• Cis initialized to 0.
• Each time there is a collision, Cis incremented by 1.
  5. Determine if there is a Student record previously inserted in the slot based on the new index.
  6. If the slot is empty, insert the Student record into this slot.
  7. Otherwise, go back to step (4) again until the Student record is inserted.  Stop executing step (4) when Cis equal to TABLE_SIZE.
• To search for a Student record by the Student ID, apply the similar steps as described in the insertion steps.

Classes:

• The software program will have three classes.  The requirements for each class are define as followings:
  • Class Student– This class must at least include the following properties:
    • Student first name (required/non-null)
    • Student last name (required/non-null)
    • Student middle name (optional)
    • Student ID (required)
  • Class StudentHash– This class will have the following methods with their signatures as listed below:
    • StudentHash (Constructor)
      • The constructor has one parameter.  This parameter will be the maximum number of Student records that can be store in the hash table.
      • It will create and initialize the hash table.
    • Add()
      • This method will receive a Student record.  It will try to insert the given Student record in the hash table that belongs to this class.
      • If the Student record is inserted successfully, it will return the collision index (C) as described in the insertion steps.
      • If the Student record cannot be inserted in the hash table, it will return (C* -1).
    • Search()
      • This method will receive the Student ID used to look up for a Student record previously inserted into the hash table.
      • If found, it will return the Student record.
      • Otherwise, it will return null.
    • PrintRecords()
      • This method has no input parameters.
      • It will display the Student record data that have been inserted in the hash table.
      • No return value from this function is needed.
  • Class StudentHashDriver– This class will contain the implementation of the main()method of the program.  The following tasks will need to be implemented:
    • There will be 3options:
      • Option 1– Allow the user to enter Student records and add them in the hash table of the StudentHash class.
      • Option 2– Allow the user to search for a Student record by the Student ID.
      • Option 3– Print out the contents of the hash table.
    • Option 1:
      • Prompt the user for the number of Student records to be entered.  
      • Create an instance of the StudentHashclass, passing the number of Student records through the constructor of the StudentHashclass.
      • Prompt the user to enter Student data.
      • Add the Student data to the hash table of the StudentHash class.
      • Whether or not the Student data can be added successfully, print out the collision number.
        • If the collision number is not negative, print out “Successfully inserted Student with ID (x)”.
        • If the collision number is negative, print out “Unsuccessfully inserted Student with ID (x)”.
    • Option 2:
      • Prompt the user for the Student ID.
      • Search for the Student record in the hash table using this ID.
      • If found, display the Student data.
      • Otherwise, report to the user that no Student record can be found using this ID.
    • Option 3:
      • Print the contents of the hash table.

Answer 1

Here is the program for above specifications.Followed the specifications given in the question.

Running Instructions:

1. In any IDE like Eclipse,NetBeans etc. create class file called StudentHashDriver.java copy and paste the below code and press run
2.In Linux open Terminal $gedit StudentHashDriver.java

copy and paste the below code save and then exit.

$javac StudentHashDriver.java

$java StudentHashDriver

Note : This is edited program.Tested and found no errors in search method.search method is working as expected.

import java.util.Scanner;

class Student{
   /*
   * Student structure hold the students data
   * */
   String firstName;
   String lastName;
   String middleName;
   int id;
   public Student(){
       /*
       * default constructor
       * */
   }
   public Student(String firstName,String lastName,String middleName,int id){
       /*
       * parameterized constructor to initialize student with it's properties
       * as parameters
       * */
       this.setFirstName(firstName);
       this.setLastName(lastName);
       this.setMiddleName(middleName);
       this.setId(id);
   }
   public String getFirstName() {
       /*
       * @return - first name of the student
       * */
       return firstName;
   }
   public void setFirstName(String firstName) {
       /*
       * method to set the first name of the student
       * */
       this.firstName = firstName;
   }
   public String getLastName() {
       /*
       * @return - last name of the student
       * */
       return lastName;
   }
   public void setLastName(String lastName) {
       /*
       * method to set the last name of the student
       * */
       this.lastName = lastName;
   }
   public String getMiddleName() {
       /*
       * @return - middle name of the student
       * */
       return middleName;
   }
   public void setMiddleName(String middleName) {
       /*
       * method to set the middle name of the student
       * */
       this.middleName = middleName;
   }
   public int getId() {
       /*
       * @return - id of the student
       * */
       return id;
   }
   public void setId(int id) {
       /*
       * method to set the id of the student
       * */
       this.id = id;
   }
}

class StudentHash{
   /*
   * class that represent hash table of students
   * operations include add, search and print the
   * students data in the hash table
   * */
   int tableSize;//max length of hash table
   Student[] hash;//array of students
   boolean[] inserted;//location on hash table which is free
   //location on inserted are set to false by default
   public StudentHash(int tableSize){
       /*
       * constructor that creates student hash table with
       * given size
       * */
       this.tableSize=tableSize;
       hash=new Student[tableSize];
       inserted=new boolean[tableSize];
   }
   int getLastPrime(int n){
       /*
       * @return greatest prime number less than
       * given number n
       * */
       int max=1;
       for(int i=n-1;i>0;i++){
           int j;
           for(j=2;j<n;j++){
               if((i%j)==0)
                   break;
           }
           if(j==n){
               return j;
           }
       }
       return max;
   }
   public int firstHash(int key){
       /*
       * returns first hash value
       * according to the formula
       * given in specifications
       * */
       return (key%tableSize);
   }
   public int secondHash(int key){
       /*
       * returns second hash value
       * according to the formula
       * given in specifications
       * */
       int prime=this.getLastPrime(tableSize);
       return (prime-(key%prime));
   }
   public int add(Student student){
       /*
       * adds the @student to hash table
       * with the strategy of double hashing
       * @return - hashed value if location is free
       * in the hash table else returns (-1*C)
       * where C is the collision counter
       * */
       int hashValue1=this.firstHash(student.getId());
       if(!inserted[hashValue1]){
           //if first hashed location is free then insert
           //the data and return index
           //where it was inserted
           hash[hashValue1]=new Student(student.getFirstName(),student.getLastName(),student.getMiddleName(),student.getId());
           inserted[hashValue1]=true;
           return hashValue1;
       }
       else{
           //first hashed index is not free
           //so get the second hash value
           //initialize the collision counter
           //recalculate the index until
           //hashed index is free or collision counter
           //reaches to max length of hash table
           int C=0;
           int hashValue2=this.secondHash(student.getId());
           int index;
           while(C<tableSize){
               //formula for recalculating the index
               index=(hashValue1 + (C * hashValue2))%tableSize;
               if(!inserted[index]){
                   //if hashed location is free then insert
                   //the data and return index
                   //where it was inserted
                   hash[index]=new Student(student.getFirstName(),student.getLastName(),student.getMiddleName(),student.getId());
                   inserted[index]=true;
                   return index;
               }
               C++;
           }
           if(C==tableSize){
               return -C;
           }
          
       }
       return -tableSize;
      
   }
   public Student search(int id){
       /*
       * searches the @id in hash table
       * @return - student's record if found with given @id
       * otherwise null
       * */
       int hashValue1=this.firstHash(id);
       if(inserted[hashValue1]&&hash[hashValue1].getId()==id){
           //if location on the hash table contains student data
           //with given id then return student's record
           return hash[hashValue1];
       }
       else{
           //first hash failed to get student's data so
           //go for double hashing mechanism to search the
           //hash table
           int C=0;
           int hashValue2=this.secondHash(id);
           int index;
           while(C<tableSize){
               index=(hashValue1 + (C * hashValue2))%tableSize;
               if(inserted[index]&&hash[index].getId()==id){
                   //if location on the hash table contains student data
                   //with given id then return student's record
                   return hash[index];
               }
               C++;
           }
           if(C==tableSize){
               return null;
           }
          
       }
       return null;
   }
   public void printRecords(){
       /*
       * prints entire hash table
       * */
       System.out.println("Student records stored are as follows : ");
       for(int i=0;i<tableSize;i++){
           if(this.inserted[i]){
               System.out.println("****************************************");
               System.out.println(" First Name : "+hash[i].getFirstName());
               System.out.println(" Last Name : "+hash[i].getLastName());
               System.out.println("Middle Name : "+hash[i].getMiddleName());
               System.out.println(" Student ID : "+hash[i].getId());
               System.out.println("****************************************");
           }
       }
   }
}

public class StudentHashDriver {
   /*
   * driver class that contain main method
   * to test the StudentHash Data Structure
   * */

   public static void main(String[] args) {
       // TODO Auto-generated method stub
       StudentHash studenthash = null;
       int option;
       while(true){
           Scanner s=new Scanner(System.in);
           //give menu to user to select the option
           System.out.println("please select an option...");
           System.out.println("1.Add student data to hash table");
           System.out.println("2.Search student data");
           System.out.println("3.Print the hash table");
           System.out.println("4.Exit");
           option=s.nextInt();
           if(option==1){
               System.out.println("Please Enter number of students");
               //get maximum number of students from user
               int size=s.nextInt();
               studenthash=new StudentHash(size);
               s.nextLine();
               //insert the student data until user chooses to quit
               while(true){
                   System.out.println("Please enter student's first name ");
                   String fName=s.nextLine();
                   System.out.println("Please Enter student's last name");
                   String lName=s.nextLine();
                   System.out.println("Please Enter student's middle name");
                   String mName=s.nextLine();
                   System.out.println("Please Enter student's id");
                   int id=s.nextInt();
                   Student tempStudent=new Student(fName,lName,mName,id);
                   int collisionCounter=studenthash.add(tempStudent);
                   System.out.println("Collision counter is "+collisionCounter);
                   if(collisionCounter>=0){
                       System.out.println("Successfully inserted Student with ID "+id);
                   }
                   else{
                       System.out.println("Unsuccessfully inserted Student with ID "+id);
                   }
                   System.out.println("Do you want to continue(Y/N)");
                   s.nextLine();
                   String doInsert=s.nextLine();
                   if((!doInsert.equals("Y")))
                       break;
               }
           }
           else if(option==2){
               if(!(studenthash==null)){
                   System.out.println("Please enter student's id");
                   int searchId=s.nextInt();
                   Student student=studenthash.search(searchId);
                   if(student!=null){
                       System.out.println("Student details are as follows");
                       System.out.println("****************************************");
                       System.out.println(" First Name : "+student.getFirstName());
                       System.out.println(" Last Name : "+student.getLastName());
                       System.out.println("Middle Name : "+student.getMiddleName());
                       System.out.println(" Student ID : "+student.getId());
                       System.out.println("****************************************");
                   }
                   else{
                       System.out.println("No Student record can be found using this ID");
                   }
               }else{
                   System.out.println("hash table is empty please add and then search");
               }
           }
           else if(option==3){
               if(!(studenthash==null)){
                   studenthash.printRecords();
               }else{
                   System.out.println("hash table is empty..");
               }
           }
           else if(option==4){
               s.close();
               break;
              
           }
           else{
               System.out.println("Invalid option try again");
           }
       }
   }

}

Sample Output:

please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
1
Please Enter number of students
5
Please enter student's first name
Jack
Please Enter student's last name
Sparrow
Please Enter student's middle name
J
Please Enter student's id
5622
Collision counter is 2
Successfully inserted Student with ID 5622
Do you want to continue(Y/N)
Y
Please enter student's first name
John
Please Enter student's last name
Snow
Please Enter student's middle name
S
Please Enter student's id
4522
Collision counter is 0
Successfully inserted Student with ID 4522
Do you want to continue(Y/N)
N
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
2
Please enter student's id
4522
Student details are as follows
****************************************
First Name : John
Last Name : Snow
Middle Name : S
Student ID : 4522
****************************************
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
3
Student records stored are as follows :
****************************************
First Name : John
Last Name : Snow
Middle Name : S
Student ID : 4522
****************************************
****************************************
First Name : Jack
Last Name : Sparrow
Middle Name : J
Student ID : 5622
****************************************
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
2
Please enter student's id
5622
Student details are as follows
****************************************
First Name : Jack
Last Name : Sparrow
Middle Name : J
Student ID : 5622
****************************************
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
2
Please enter student's id
1522
No Student record can be found using this ID
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
4

Test 2
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
1
Please Enter number of students
4
Please enter student's first name
john
Please Enter student's last name
snow
Please Enter student's middle name
S
Please Enter student's id
3366
Collision counter is 2
Successfully inserted Student with ID 3366
Do you want to continue(Y/N)
Y
Please enter student's first name
Jack
Please Enter student's last name
Sparrow
Please Enter student's middle name
Sp
Please Enter student's id
53453
Collision counter is 1
Successfully inserted Student with ID 53453
Do you want to continue(Y/N)
Y
Please enter student's first name
Lincoln
Please Enter student's last name
Burrows
Please Enter student's middle name
J
Please Enter student's id
2658
Collision counter is 0
Successfully inserted Student with ID 2658
Do you want to continue(Y/N)
Y
Please enter student's first name
Michael
Please Enter student's last name
Scofield
Please Enter student's middle name
J
Please Enter student's id
1285
Collision counter is 3
Successfully inserted Student with ID 1285
Do you want to continue(Y/N)
Y
Please enter student's first name
Sara
Please Enter student's last name
Williams
Please Enter student's middle name
S
Please Enter student's id
5351
Collision counter is -4
Unsuccessfully inserted Student with ID 5351
Do you want to continue(Y/N)
N
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
3
Student records stored are as follows :
****************************************
First Name : Lincoln
Last Name : Burrows
Middle Name : J
Student ID : 2658
****************************************
****************************************
First Name : Jack
Last Name : Sparrow
Middle Name : Sp
Student ID : 53453
****************************************
****************************************
First Name : john
Last Name : snow
Middle Name : S
Student ID : 3366
****************************************
****************************************
First Name : Michael
Last Name : Scofield
Middle Name : J
Student ID : 1285
****************************************
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
2
Please enter student's id
3326
No Student record can be found using this ID
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
2
Please enter student's id
3366
Student details are as follows
****************************************
First Name : john
Last Name : snow
Middle Name : S
Student ID : 3366
****************************************
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
2
Please enter student's id
1285
Student details are as follows
****************************************
First Name : Michael
Last Name : Scofield
Middle Name : J
Student ID : 1285
****************************************
please select an option...
1.Add student data to hash table
2.Search student data
3.Print the hash table
4.Exit
4

there is small mistake in the search method in StudentHash class.Corrected method is given below.

• public Student search(int id){ int hashValue1=this.firstHash(id); if(inserted[hashValue1]&&hash[hashValue1].getId()==id){ return hash[hashValue1]; } else{ int C=0; int hashValue2=this.secondHash(id); int index; while(C