❼ A properly documented program that can be tested by the teaching assistants in running new test queries beyond those available to you. Your program should compile correctly with no errors and be able to run using the data supplied by the teaching assistants.

❼ A VeriGuide report on your submission.

Project Specifications

1. You are given 100K data records in a text file, each line containing two fields of a fixed length. The records are not given in any particular order, and the keys were generated randomly using a uniform distribution over its space.

2.  The first field in each record contains a search key with 256 bits.  The range of the search key (U = 2256 − 1) is much larger than the number of records (n ≈ 100000) in the text file and those added by the queries.

3.  Create an empty hash table and a database to store the records.  Read the text file, one line at a time to insert the record into the database and the corresponding pointer and other information in the hash table. Each database record is identified by its starting address (or index) of the record.

4. You are given a sequence of queries on the database (in files test hash table .py, test hash table .java, test hash table . cpp) of the following types:

❼ Inserting new records into the database or deleting existing records from the database, one at a time, each using the given search key;

❼ Finding the pointer to the record with the  k-th smallest value of the search key (and a set of pointers to multiple records if there are duplicates), where k can range from  1 to the number of database records;

❼ Returning the pointers of all database records who key values are in a given range of the search key; examples of ranges are the 1000 records with the smallest keys, records whose keys are the 200 largest, and records whose keys are in in a given range of key values (say 105  to 5 × 105 ).

5. We will provide you with the following program files that can be down- loaded from Blackboard (as a zip file)

❼ Record.py, Record. cpp, Record.java: for reading data from the input file and classes to store the data records,

❼ example .py,  example . cpp,  example .java: the class of HashTable that annotate what you will implement,

❼ test hash table .py, test hash table . cpp, test hash table .java: tests that you run to test your program.

6. Your design should not be hard-coded for a given database.

❼ Your solution should be able to adapt to the dynamic growth and shrinking of the database.

❼ Your solution should be based on hashing only; all the queries should be run using the hash tables maintained; you should not maintain any sorted list of the keys.  However, auxiliary information derived from the hash table can be maintained.

❼ If you used a linear search, a binary search, or any sorted list in your solution, you will get a very low score.

Suggested Solution Approach

1. You should create an initially empty hash table of m entries; each entry of the hash table should include fields for the forward and backward pointers of the linked list maintained by this table entry, the range of key values hashed into this location (b1 ,b2 ), the number of elements in the linked list pointed to by this table entry, and other fields if necessary.  An example of a hash table entry is as follows:

Each node in the linked list of the hash table entry should include a pointer (or index) to the database containing the record.  It would also include forward and backward pointers to other nodes in the linked list, if any. An example of a node in the linked list is as follows:

2. You should populate the hash table and your database by inserting the 100K records from the text file, one at a time.

3. You will then process the queries, one at a time.   As database records with new keys may be inserted or existing records deleted, you will need to dynamically update the hash table as the queries are processed.

4. You will report the result of each query, the times taken, and the number of logical steps (you need to decide how to measure the number of logical steps).

5.  Since you need to search for keys in a specific range, you should be dividing the keys into ranges and use hashing on a range of keys into a unique hash table location. Each hash table entry should contain a range of keys that can be hashed into, and a pointer to a linked list of the records in this list.

6.  To find the k-th smallest record, you will hash into the specific range and search all the records in a linear fashion. A better solution (not required) is to do second-level hashing on those keys in the list or to maintain an auxiliary table of sorted keys (as done in the tutorial).

7. You should report the following summary results over all the queries pro- cessed:

(a)  amortized time of inserting a key into the hash table (and the database)