using C++ Implement a software program in either C++ 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 N is 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 theTABLE_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.