Hash Table Indexing Learning Objectives 

• Implement a data structure to meet given specifications
• Design, implement, and use a closed hash table data structure
• Use a hash table as an index into a separate data store

Overview

Your task for this assignment is to implement a database of student records. Your database will consist of two parts: an unsorted vector of student records, and an index of student IDs implemented as a closed hash table.

The Record Store

Student records will be stored in an unsorted vector of class Record. The definition of class Record will be provided for you in the fileRecord.h.

The HashTable class

Your hash table should be implemented as an array ofMAXHASHobjects of class Slot. A Slot contains an integer key, and an integer index. The definition of class Slot will be provided for you in the fileSlot.h. In order to more easily test collision resolution, and error handling for full HashTables we will use a very small table for testing. The value ofMAXHASHshould initially be#definedto 20.

To implement the hash table, you should create a class called HashTable, implemented in the files HashTable.h and HashTable.cpp. Your class should support the following operations:

HashTable contents: HashTable Slot 9: Key = 112233, Index = 2 HashTable Slot 4: Key = 223344, Index = 0 HashTable Slot 2: Key = 334455, Index = 1

Note:operator

• bool HashTable::insert(int key, int index, int& collisions) Insert a new key/index pair into the table. Duplicate keys are not allowed. This function should returntrueif the key/index pair is successfully inserted into the hash table, andfalseif the pair could not be inserted (for example, due to a duplicate key already found in the table, or if the HashTable is full). If the insertion is successful, the number of collisions occuring during the insert operation should be stored incollisions.
• bool HashTable::remove(int key) If there is a record with the given key in the hash table, it is deleted (changing the slot type toemptyAfterRemovaland the function returnstrue; otherwise the function returnsfalse.
• bool HashTable::find(int key, int& index) If a record with the given key is found in the hash table, the function returnstrueand a copy of the index is returned inindex. Otherwise the function returnsfalse.
• float HashTable::alpha()- returns the current loading factor, a, of the hash table.
• Your HashTable class should also overloadoperatorsuch thatcout prints all the information in the table in the following format:

The hash and probe functions

Because this is a closed hash, you will need both a hash function and a probe function. A hash function will be provided for you in the filehashfunction.h. Your hash must usepseudo-random probingto resolve collisions.

The Database class

Your database consists of two parts, the record store and the hash table. In other words, the private data members of your Database class should include the following:

class Database { private: HashTable indexTable; vector recordStore; }

Your Database class should support the following operations:

Database contents: HashTable Slot: 9, recordStore slot 2 -- Gates, Bill (U00112233): Senior HashTable Slot: 4, recordStore slot 0 -- Cook, Tim (U00223344): Sopohomore HashTable Slot: 2, recordStore slot 1 -- Zuckerberg, Mark (U00334455): Freshman

Note:operator

• bool Database::insert(const Record& newRecord, int& collisions) Insert a new student record into the database. This function should:
  • Check to make sure the UID is not already in the HashTable.
  • If not, insert the Record into the recordStore, and
  • Insert the UID and the slot the Record occupies in the recordStore into the HashTable.
• This function should returntrueif the record is successfully inserted into the database, andfalseif the record could not be inserted (for example, due to a duplicate key already found in the HashTable, or if the HashTable is full). If the insertion is successful, the number of collisions occuring during the HashTable::insert() operation should be returned incollisions.
• bool Database::remove(int key) If there is a record with the given key in the Database, it is deleted and the function returnstrue; otherwise the function returnsfalse. Deleting from the database removes both the hash table (index) entry, and the record store (vector) entry.You must delete records from the recordStore in a way that does not waste memory, and does not break the index. One way to do this is to copy the last record in the vector into the position holding the record to be deleted, and then use pop_back() to remove the last element of the vector.
• bool Database::find(int uid, Record& foundRecord) If a record with the given uid is found in the Database, the function returnstrueand a copy of the record infoundRecord. Otherwise the function returnsfalse.
• float Database::alpha()- returns the current loading factor, a, of the Database\'s hash table (This function can simply callHashTable::alpha().
• Your Database should also overloadoperatorsuch thatcout prints all the information in the database in the following format:

Main program

You should use your student database in a main program that allows a user to insert, search, and delete from the database. Searching the database by UID should be done using the hash table, and should report the number of collisions encountered during the search.

Example program operation

Would you like to (I)nsert or (D)elete a record, or (S)earch for a record, or (Q)uit? Enter action: I Inserting a new record. Last name: Doe First name: Jane UID: 1234 Year: Junior Record inserted. Would you like to (I)nsert or (D)elete a record, or (S)earch for a record, or (Q)uit? Enter action: S Enter UID to search for: 1234 Searching... record found (3 collisions during search) ---------------------------- Last name: Doe First name: Jane UID: 1234 Year: Junior ---------------------------- Would you like to (I)nsert or (D)elete a record, or (S)earch for a record, or (Q)uit? Enter action: S Enter UID to search for: 2345 Searching... record not found Would you like to (I)nsert or (D)elete a record, or (S)earch for a record, or (Q)uit? Enter action: Q Exiting. Turn in and Grading

Please zip your entire project directory into a single file called Project4.zip.

This project is worth 50 points, distributed as follows:

Task	Points
HashTable::insertstores key/index pairs in the hash table using appropriate hashing and collision resolution, and correctly rejects duplicate keys and reports correct collision counts. Insert correctly re-uses space from previously-deleted records.	5
Database::insertstores records in the recordStore and hashes the UID and recordStore slot in the HashTable. Insert correctly rejects duplicate keys and reports correct collision counts. Insert correctly re-uses space from previously-deleted records. Insert correctly returns false when the index (hash table) is full.	5
HashTable::findcorrectly finds records in the hash table using appropriate hashing and collision resolution, and returns true and places the index associated with the search key intoindexif the key is found, or returnsfalsewhen the requested key is not present in the hash table.	5
Database::finduses HashTable::find to find UIDs in the hash table. Returns true and places the appropriate record in foundRecord if the UID is found, or returnsfalsewhen the requested UID is not present in the Database.	5
HashTable::removecorrectly finds and deletes records from the table, without interfering with subsequent search or insert operations.	5
Database::removecorrectly finds and deletes records from the database, without interfering with subsequent search or insert operations. Also, removing records does not waste memory in the record store.	5
Database::alphacorrectly calculates and returns the load factor of the database\'s hashTable.	5
operatoris correctly overloaded for class HashTable and class Database as described above.	5
Code is well organized, well documented, and properly formatted. Variable names are clear, and readable. Classes are declared and implemented in seperate (.cpp and .h) files.	5
Appropriate use of public and private class member data. No global variables or unnecessary member variables. Efficient and well-designed code. No memory leaks when creating and deleting hashTables or databases.	5

Attachments:

hashfunction.h

Slot.h

Record.h

Project6.html