need help to implement a closed hash table data structure, and to use this hash as the index for rapid searching of a database of student records in c++

Your hash table should be implemented as an array of MAXHASH objects of class Slot. A Slot contains an integer key (the student's UID), and a value, which can be of any type. The implementaiton of class Slot will be provided for you in the file Slot.h. The value of MAXHASH should initially be #defined to 1000.

Your hash table should accept integer keys, and any type of value. To implement the hash table, you should create a class template called HashTable, implemented inline in the file HashTable.h. Your class should support the following operations (for any class T):

bool HashTable::insert(int key, T value, int& collisions) Insert a new key/value pair into the table. Duplicate keys are not allowed. This function should return true if the key/value pair is successfully inserted into the hash table, and false if the pair could not be inserted (for example, due to a duplicate key already found in the table). If the insertion is successful, the number of collisions occuring during the insert operation should be returned in collisions.

bool HashTable::remove(int key) If there is a record with the given key in the hash table, it is deleted and the function returns true; otherwise the function returns false.

bool HashTable::find(int key, T& value) If a record with the given key is found in the hash table, the function returns true and a copy of the value is returned in value. Otherwise the function returns false.

float HashTable::alpha() returns the current loading factor, , of the hash table.

Because this is a closed hash, you will need both a hash function and a probe function. You are free to implement any hash function you like. For example, you may choose to implement some form of the ELFhash, given in Chapter 9 of your textbook, or any other hash function that will work on integer keys. Remember to cite your source if you use code written by anyone other than yourself!

Your hash should use pseudo-random probing to resolve collisions.

Your hash table should also overload operator<< such that cout << myHashTable prints all the key/value pairs in the table, along with their hash table slot, to cout.

Your hash table should be used as an index for a database of student records. Each student record should contain the student's last name, first name, UID, major, and year (freshman, sophomore, etc.). Student records should be stored outside the hash table. You may use any data structure you wish for these records. For example, students could be stored in a simple unordered array, with the index of the location of each record stored in the hash table with the student's UID. (If you use this approach, you will need to come up with a mechanism to re-use empty array slots when records are deleted.) Alternately, student records could be stored as a linked list, in which case the hash table would include a pointer to the record in the list along with each UID.

example of output:

********

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 ---------------------------- 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. 

*****************

here is the slot.h file to start

#pragma once

#include

#include

#include

using namespace std;

// There are three types of slots in a closed hash:

// Normal (full) slots, empty slots, and tombstones

enum SlotType {normalSlot, emptySlot, tombstone};

// Each record holds an integer key and a value of any type

// (hence the need for a template). The value type must be

// printable using << or this code will fail.

//

// In this implementation, the value is stored directly in

// the record. If the value is large, it would be more

// efficient to have the records hold pointers to the values.

// In this case, care would need to be taken to ensure

// that deep copies are made upon assignment, and that

// any values allocated are properly deleted in the Record

// destructor.

template class Slot

{

private:

int key;

T value;

SlotType type;

public:

// The default constructor produces an empty record.

// A possibly better way to keep track of tombstones and emtpy

// records would be to use inheritance, similar to the way we

// avoided having null pointers in leaf nodes for binary trees.

Slot()

{

key = 0;

type = emptySlot;

}

// This constructor uses an initialization list

// See "member initialization" at: http://www.cplusplus.com/doc/tutorial/classes/

Slot(int newkey, T newvalue)

: key(newkey), value(newvalue)

{

type = normalSlot;

}

// Convert a record to a tombstone

void kill() {

type = tombstone;

}

// Get the integer key of a record

int getKey() const {

return key;

}

// Get the value of a record

T getValue() const {

return value;

}

// Check if a record is empty

bool isEmpty() const {

return(type == emptySlot);

}

// Check if a record is a normal record

bool isNormal() const {

return(type == normalSlot);

}

// Check if a record is a tombstone

bool isTombstone() const {

return (type == tombstone);

}

// Overload the << operator for printing records

friend ostream& operator<<(ostream& os, const Slot& me) {

if (me.isTombstone())

os << "<>";

else if (me.isEmpty())

os << "<>";

else

os << "Key: " << me.key << ", Value: " << me.value;

return os;

}

~Slot()

{

}

};