My professor gave us an assignment that I am not entirely sure how to start correctly. She gave us 2 java classes as well to use. Any assistance would be greatly appreciated...
So basically, two things need to be done. I need to create two more classes, ExternalHashing and IndexHashTable...and I have some work so far but I am not sure how to edit it to make it work for this assignment.
I already have some of it...but I had done a previous assignment and used basically that, but I am not sure how to edit it to make it work here.
I also for whatever reason, am unable to post the source code on here and I am not sure why.
Problem to be solved:
Simulate the external hashing structure for a department to store the students’ information by using Java RandomAccessFile class.
The data structure is implemented by an in-memory hash table and an external file. Assume the file consists of n disc blocks and each block contains r records maximally.
The number of total records is not more than (n * r ) / 2. (The load factor is ½)
Each record is defined as follow:
It consists of one string name and one string id. The id is a key which uniquely represents a record. The mapping integer of an id is in the range of 1 to 200. (the digits given to an id is 4 for extending purpose)
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 an index of a block in the external file. See fig. 11.15 in p. 572.
Once the external block is identified, use the linear probing to find the location for the record (for all operations) in the external blocks. The linear probing here means a sequential search record by record within a block.
1. Implement an Index Hash Table by a class named IndexHashTable. Each element of the table contains a block number in the range of 0 to n-1. Each block number is an index of the block in the external file. For example, if one block size is 300 bytes and the index is 6, the offset for the block 6 should be 6*300=1800 byte in the file. In another word, the block 6 starts from 1800 byte and ends at 2099 byte in the file.
2. To simulate the randomly distributed block numbers in the hash table, the block number in each cell of the hash table should be a random number. The range of the random numbers is 0 to n-1. The block numbers should be unique in the table. The hash table should be created in the constructor of the IndexHashTable class.
3. The operations in the hash table are insert, delete, and search. You may define a noData record to help for clearing the storage or representing the deleted elements in the external file.
Here is an algorithm for the operation “Insert”:
The possible steps for insert
1) For a given record (input by user), use the id of the record to be the original key. Note that the key is an integer converted from the string id.
2) Apply the hash function (p.536) to the key to obtain an index of the in-memory Index Hash Table.
3) Use the index to retrieve the block index in the table.
4) Calculate the start address of the block in the file: block-index * blockSize. The blockSize is recSize * r.
5) Use the address obtained in 4) to locate the position of the block in the file (use the seek() method showing in RandomFile.java, the sample code given by the instructor.)
6) Use the linear probe approach to insert the record in the block.
During the probing, make sure that there is no redundant key found (no key maps the key of the record for inserting). If find redundancy, stop insertion.
If the number of probes reaches r and the available space is not found in the block, the operation fails and stop (the block is full. This situation indicates that the hash function itself has a poor performance.)
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
Start from step 5), the operations of the random access file will be involved.
The students should figure out the algorithms for delete and search.
4. 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.
name – It is String type and limited to 16 chars
id – It is String type and limited to 4 chars
[Note: Each char in Unicode is two bytes. When you search in the object of RandomAccessFile in which the operations are in bytes, counting offset for each record should double the size of the chars in a record. In another word, a record consists of 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 works as an external disk file, how to use the write and read operations defined in 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 can use it as the base skeleton of your application class.
5. Write an application class named ExternalHashing to supply a menu for users to use the hash table to store the records. The menu should include the Insert, Remove, Search and Quit operations. You should also display a title to this system.
6. Your program should be general to accept any values for n and r. You may test your program by using n = 5 (the size of the in-memory hash table and also the number of blocks in the file) and r = 7 (the maximum number of records in a block)
7. The following classes should be included in your submission (in one zip file):
Record.java – represents one record (from the constructor)
IndexHashTable.java – represents the hash table including the operations of insert, search and delete
ExternalHashing.java – the client class displaying the menu to the user and do all user interactions
8. Write a good documentation to your program.