Implement the external hashing structure to store the students information for a department. Provide partial basic operations: insert, display and search to the system. Assumptions: To implement the external hashing, an in-memory hash table and a random access file will be used. The file is for simulating the external storage of a disc. Assume the file consists of n disc blocks and each block contains r records maximally. The total number of records to be stored in the data structure is not more than (n * r) / 2. Each student record is defined as follow: It consists of a name and an id, both are String type. The id is a key which uniquely represents a record. The read operation reads the record from a file The write operation writes the record into the file Each element of the in-memory hash table contains a block number which is an index of a block in the external file. Refer to the fig. 11.15 in p. 572 in the textbook. Once the external block is obtained, use the linear probing to find the element location inside of the external blocks (for all operations). The linear probing here means a sequential search record-by-record within a block. Since the id is unique for each record, test redundancy when insert. When user chooses to quit from the program, display the number of records in each block at the time. Detail guides: 1. Implement an Index Hash Table by a class named IndexHashTable. Each element of the table contains a block number (int) in the range of 0 to n-1. Each block number is an index of the block in the external file (called block index also). We also define that the offset of a block is the relative address of the beginning of the block to the beginning of the file, in byte. For example, if one block size is 300 bytes and the block number is 6, the offset of the block 6 should be 6*300=1800 byte in the file. In another word, the block 6 starts from byte 1800 and ends at byte 2099 in the file. 2. To simulate the randomly distributed block numbers in the hash table, 0 to n-1 indexes should be randomly distributed in the hash table. These numbers should be inserted in to the table when the table is initialized (in the constructor of IndexHashTable class). The block numbers should be unique in the table. 3. Create a file to store the data (The instructor will provide a sample code. See 5.2. below) 4. The operations in the hash table are insert, search and display. To guide your implementation, here is an algorithm and some discussions on programming issues for the operation Insert: The signature of the insert method is: public int insert (RandomAccessFile file, Record rec) It returns 0 for successful, -1 for block full and 1 for redundancy (more details follow) The possible steps for insert: (to describe the algorithm conveniently, assume the table is hashTbl [ ]) 1) For a given record (both id and name are input data from user), use the id of the record as the original key. Note that the original key is a string and you have to convert it to an integer. 2) Apply the hash function (p.536) to the key to obtain an index i, which is used to locate a cell in the in-memory Hash Table hashTbl. The table size n is decided by the number of blocks n which should be obtained from the end user at the beginning of your program (do not multiply n by 2 in your hash function because our strategy is more like separate chaining). 3) Retrieve the block index from hashTbl [i]. 4) Calculate the start address (the offset) of the block in the external file: block-index * blockSize (e.g. I * 300 in previous example). The blockSize is recSize * r * 2. The r is the maximum number of records allowed in one block provided by the user also and 2 is for enlarging the capacity in each block to avoid the full of block. 5) Use the address obtained in 4) to locate the position of the block in the file (use the seek() method of RandomAccessFile class. Refer to the API of the RandomAccessFile.java online. An example of the usage is also shown in the sample code given by the instructor.) 6) Use the linear probe approach to insert the record in the block. 7) There are three possible return values: 0 normal exit. The record has been inserted 1 ID redundancy. During the probing, make sure that there is no redundant key found (there is no any existing record with the same key as the key of the record for inserting). If find redundancy, do not do the insertion. The search() may be invoked to do the job. -1 The block is full. If the number of probes reaches r and the available space is not found in the block, the operation fails (the block is full. This situation should be rear which indicates that the hash function itself has a poor performance). Start from step 5), the operations of the random access file will be involved. The class with the methods for read/write the file is provided by the instructor. See 5. 5. The classes provided by instructor: 1) Record class This class defines a record required in the problem, includes methods to write the record into a specified random access file and read a record from the file. Class field: o id It is String type and limited to 4 chars. The range of id is 1 to 500. (Giving 4 digits id is for extending purpose) o name It is String type and limited to 16 chars [Note: Each char in Unicode is two bytes. When you work with the object of the RandomAccessFile in which the operations apply on bytes, you should count the offset for each record by doubling the size of the chars in a record. In another word, the record defined here consists of 16 + 4 = 20 chars which are 40 bytes.] Constructor: public record (String name, String id) create a new record Public Methods: public void read (RandomAccessFile file) to retrieve the name and id from the file at the current file pointer position public void write (RandomAccessFile file) to write name and id in the file at the current position public String getId( ) to return the id of a record public String getName( ) to return the name in a record public String toString( ) to display the name and id in the record 2) RandomFile class This is a demo program. It shows how to create a random access file (which may work as an external disk file in your project), how to use the write and read operations defined in the Record class, how to locate a block by seek() in the file, and how to close the file. It is an application class containing main(). You may run this class with Record class to see what happens to the created external file. The file is created under the same directory with the classes you run. 6. About Display: This operation can be used by administrators (also helps you debug the program). It displays all records info in one block. Ask the user to provide a block number. Test the qualification of the block number. Then display the contents in that block. Watch the format of the display. Prompt user for the empty block (do not display any null). 7. Write an application class named ExternalHashing to provide an interface for users to use the system. In the operation menu, there are following items, Insert, Search, Display and Quit. 8. Your program should be general to accept any values for n (the size of the in-memory hash table and also the number of blocks in the file) and r (number of record allowed in each block and will be doubled internally) from the end user. You may test your program by entering 5 for n and 3 for r (use primes). 9. The following classes should be included in your submission (in one zip file only): Record.java represents one record (from the instructor) IndexHashTable.java represents the hash table including the operations and other help methods if there are any ExternalHashing.java the client class displaying the screen title and operations menu to the user and do all user/system interactions