1. Engineering
  2. Computer Science
  3. doublehashing java program implement a software program in java that...

Question: doublehashing java program implement a software program in java that...

Question details

Double-Hashing Java program

Implement a software program in Java that 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. Please use ARRAY to implement the hash table and store student information.

Algorithm:

  • 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 PRIME is a prime number smaller than the TABLE_SIZE and Key is the ID of the Student record (Refer to the Student class definition below)

    • For example, if TABLE_SIZE is 12, then PRIME will 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.

  • C is initialized to 0.

  • Each time there is a collision, C is incremented by 1.

    1. Determine if there is a Student record previously inserted in the slot based on the new index.

    2. If the slot is empty, insert the Student record into this slot.

    3. Otherwise, go back to step (4) again until the Student record is inserted. Stop executing step (4) when C is 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 3 options:

        • 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 StudentHash class, passing the number of Student records through the constructor of the StudentHash class.

        • 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.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution