The assignment is to implement a simple hash table using linear probing for collision resolution, with an external file system (RandomAccessFile) as the underlying storage. The system should allow users to insert, delete, and search records. The program should be able to handle block fullness and redundancy checks.
Contribute Materials
Your contribution can guide someoneβs learning journey. Share your
documents today.
Assignment 4 (Hash table and external storage): Problem to be solved: Implement theexternal hashingstructure to store the studentsβ information for a department. Provide basic operations:insert, search and deleteto the system. Assumptions: ο·The data structure is implemented by an in-memory hash table and a random access file as an external-memory. The file is for simulating the external storage of a disc. Assume the file consists ofndisc blocks and each block containsr records maximally. ο·The number of total records need to be stored is not more than (n * r) / 2. ο·Each record is defined as follow: ο§It consists of anameand anid, both are String type.The id is a key which uniquelyrepresents a record. ο§Thereadoperation reads the record from a file ο§Thewriteoperation 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 the fig. 11.15 inp. 572in the textbook. ο·Once the external block is identified, 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. ο·Do not forget the special consideration of deleting on the effect of other operations. ο·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 namedIndexHashTable. 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. For example, if one block size is 300 bytes and the index is 6, the offset (the relative address to the beginning of the file) of theblock 6begin address should be 6*300=1800 byte in the file. In another word, theblock 6starts 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 IndexHashTableclass). The block numbers should beuniquein 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 areinsert, deleteandsearch. To guide your implementation, here is an algorithm and some discussions on programming issues for theoperationβInsertβ:
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
ο·The signature of theinsertmethod is: public int insert (RandomAccessFile file, Record rec) It returns0for successful,-1for block full and1for redundancy (more details follow)ο·The possible steps forinsert: (to describe the algorithm conveniently, assume the table is hashTbl [ ]) 1)For a given record (input by user), use the id of the record as the original key. Note that the key is an integer converted from the string id. 2)Apply the hash function (p.536) to the original key to obtain an indexi, which is used to locate a cell in the in-memory Hash TablehashTbl. The table sizenis decided by the number of blocksnwhich should be obtained from the end user (do not multiply n by 2 in your hash function because our strategy is more like separate chaining). 3)Retrieve theblock indexfromhashTbl [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 isrecSize*r * 2. Theris the maximum number of records allowed in one block provided by the user 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 theseek()method which can be found in the API of the RandomAccessFile.java. The usage is also shown in the sample code given by the instructor.) 6)Use thelinear probeapproach 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. ο§-1β The block is full. If the number of probes reachesrand 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 methods for read/write the file are provided by the instructor. See 5. 5.The classes provided by instructor: 1)Recordclass 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: oidβ It is String type and limited to4 chars. The range of id is 1 to500. (Giving4digitsidis for extending purpose) onameβ It is String type and limited to16 chars
[Note: Each char in Unicode is two bytes. When you work with the object of theRandomAccessFilein which the operations apply on bytes,youshould 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. This 40 will be used by linear probing when you want to move to the next record.] Constructor: public record (String name, String id)β create a new record PublicMethods: 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)RandomFileclass 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 theRecordclass, how to locate a block byseek()in the file, and how to close the file. It is an application class containingmain(). You may run this class withRecordclass to see what happens to the created external file. The file is created under the same directory with the classes you run. 6.Write an application class namedExternalHashingto provide an interface for users to use the system. In the operation menu, there are following items,Insert, Delete, SearchandQuit.. 7.Your program should be general to accept any values forn(the size of the in- memory hash table and also the number of blocks in the file) andr(number of record allowed in each block and will be doubled internally)from the end user. You may test your program by entering5fornand7forr(use primes). 8.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