Hash Table and External Storage: Assignment

Added on - 18 Sep 2019

  • 3


  • 1557


  • 221


  • 0


Trusted by +2 million users,
1000+ happy students everyday
Showing pages 1 to 1 of 3 pages
Assignment 4 (Hash table and external storage):Problem to be solved:Implement theexternal hashingstructure to store the students’ information for adepartment. Provide basic operations:insert, search and deleteto the system.Assumptions:The data structure is implemented by an in-memory hash table and a randomaccess file as an external-memory. The file is for simulating the external storageof a disc. Assume the file consists ofndisc blocks and each block containsrrecords 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 whichuniquelyrepresents a record.Thereadoperation reads the record from a fileThewriteoperation writes the record into the fileEach element of the in-memory hash table contains a block number which is anindex 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 elementlocation inside of the external blocks (for all operations). The linear probing heremeans a sequential search record-by-record within a block.Do not forget the special consideration of deleting on the effect of otheroperations.When user chooses to quit from the program, display the number of records ineach block at the time.Detail guides:1.Implement an Index Hash Table by a class namedIndexHashTable. Each elementof the table contains a block number (int) in the range of 0 to n-1. Each blocknumber is an index of the block in the external file. For example, if one block size is300 bytes and the index is 6, the offset (the relative address to the beginning of thefile) of theblock 6begin address should be 6*300=1800 byte in the file. In anotherword, 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-1indexes should be randomly distributed in the hash table. These numbers should beinserted in to the table when the table is initialized (in the constructor ofIndexHashTableclass). 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 yourimplementation, here is an algorithm and some discussions on programming issuesfor theoperation“Insert”:
You’re reading a preview
Preview Documents

To View Complete Document

Click the button to download
Subscribe to our plans

Download This Document