Assignment 4: Hash Table and External Storage
3 Pages1557 Words446 Views
Added on 2019-09-18
Assignment 4: Hash Table and External Storage
Added on 2019-09-18
ShareRelated Documents
Assignment 4 (Hash table and external storage):Problem to be solved:Implement the external hashing structure to store the students’ information for a department. Provide basic operations: insert, search and delete to 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 of n disc 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 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 fileThe write operation writes the record into the fileEach 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 in p. 572 in 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 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. For example, if one block size is300 bytes and the index is 6, the offset (the relative address to the beginning of the file) of the block 6 begin address 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, delete and search. To guide your implementation, here is an algorithm and some discussions on programming issues for theoperation “Insert”:
End of preview
Want to access all the pages? Upload your documents or become a member.
Related Documents
How to Create a Test File in C++ PDFlg...
|8
|1260
|40