Hashing

/** * @author Jane Programmer * @cwid 123 45 678 * @class COSC 2336, Spring 2019 * @ide Visual Studio Community 2017 * @date April 8, 2019 * @assg Assignment 13 * * @description Assignment 13 Dictionaries and Hash table * implementations. */ #include <cassert> #include <iostream> #include "KeyValuePair.hpp" #include "Employee.hpp" #include "HashDictionary.hpp" using namespace std; /** main * The main entry point for this program. Execution of this program * will begin with this main function. * * @param argc The command line argument count which is the number of * command line arguments provided by user when they started * the program. * @param argv The command line arguments, an array of character * arrays. * * @returns An int value indicating program exit status. Usually 0 * is returned to indicate normal exit and a non-zero value * is returned to indicate an error condition. */ int main(int argc, char** argv) { // ----------------------------------------------------------------------- cout << "----- testing Employee record and KeyValuePair class -----------" << endl; KeyValuePair<int, string> pair(42, "blue"); cout << "test key: " << pair.key() << endl; assert(pair.key() == 42); cout << "test value: " << pair.value() << endl; assert(pair.value() == "blue"); int id = 3; Employee e(id, "Derek Harter", "1234 Main Street, Commerce TX", 12345.67); cout << e << endl; assert(e.getId() == 3); assert(e.getName() == "Derek Harter"); cout << endl; // ----------------------------------------------------------------------- cout << "-------------- testing quadratic probing -----------------------" << endl; const int TABLE_SIZE = 7; HashDictionary<int, Employee> dict(TABLE_SIZE, EMPTY_EMPLOYEE_ID); cout << "Newly created hash dictionary should be empty, size: " << dict.size() << endl; assert(dict.size() == 0); int probeIndex = 0; //cout << "probe index: " << probeIndex // << " returned probe value: " << dict.probe(id, probeIndex) // << endl; //assert(dict.probe(id, probeIndex) == 2); probeIndex = 1; //cout << "probe index: " << probeIndex // << " returned probe value: " << dict.probe(id, probeIndex) // << endl; //assert(dict.probe(id, probeIndex) == 5); probeIndex = 5; //cout << "probe index: " << probeIndex // << " returned probe value: " << dict.probe(id, probeIndex) // << endl; //assert(dict.probe(id, probeIndex) == 37); cout << endl; // ----------------------------------------------------------------------- cout << "-------------- testing mid-square hashing ----------------------" << endl; // the following asserts will only work for 32 bit ints, leave asserts // commented out if you have 64 bit asserts cout << "Assuming 32 bit (4 byte) ints for these tests: " << sizeof(int) << endl; assert(sizeof(int) == 4); //id = 3918; //cout << "hash key: " << id // << " returned hash value: " << dict.hash(id) // << endl; //assert(dict.hash(id) == 1); //id = 48517; //cout << "hash key: " << id // << " returned hash value: " << dict.hash(id) // << endl; //assert(dict.hash(id) == 6); //id = 913478; //cout << "hash key: " << id // << " returned hash value: " << dict.hash(id) // << endl; //assert(dict.hash(id) == 5); //id = 8372915; //cout << "hash key: " << id // << " returned hash value: " << dict.hash(id) // << endl; //assert(dict.hash(id) == 4); // test that the distribution of the hash values // over the possible slots/buckets looks relatively // evenly distributed int counts[TABLE_SIZE] = {0}; //for (id = 0; id < 1000000; id++) //{ // int hash = dict.hash(id); // counts[hash]++; //} // display results int sum = 0; for (int slot = 0; slot < TABLE_SIZE; slot++) { cout << "counts for slot[" << slot << "] = " << counts[slot] << endl; sum = sum + counts[slot]; } // spot check results //assert(sum == 1000000); //assert(counts[0] == 143055); //assert(counts[6] == 142520); cout << endl; // ----------------------------------------------------------------------- cout << "-------------- testing dictionary insertion --------------------" << endl; id = 438901234; //dict.insert(id, Employee(id, "Derek Harter", "123 Main St. Commerce TX", 58.23)); id = 192834192; //dict.insert(id, Employee(id, "Alice White", "384 Bois'darc. Campbell TX", 45.45)); id = 998439281; //dict.insert(id, Employee(id, "Bob Green", "92 Washington Apt. 5 Greenville TX", 16.00)); id = 362817371; //dict.insert(id, Employee(id, "Carol Black", "8913 FM 24 Cooper TX", 28.50)); cout << "After inserting " << dict.size() << " employees:" << endl; cout << dict << endl; // spot check that hash table entries were correctly performed //assert(dict.size() == 4); //assert(dict[3].key() == 192834192); //assert(dict[3].value().getName() == "Alice White"); //assert(dict[1].key() == 438901234); //assert(dict[1].value().getName() == "Derek Harter"); cout << endl; // ----------------------------------------------------------------------- cout << "-------------- testing dictionary search -----------------------" << endl; id = 438901234; //e = dict.find(id); //cout << "Search for id: " << id << endl; //cout << " Found employee: " << e << endl; //assert(e.getId() == id); //assert(e.getName() == "Derek Harter"); id = 362817371; //e = dict.find(id); //cout << "Search for id: " << id << endl; //cout << " Found employee: " << e << endl; //assert(e.getId() == id); //assert(e.getName() == "Carol Black"); id = 239481432; //e = dict.find(id); //cout << "Unsuccessful Search for id: " << id << endl; //cout << " Found employee: " << e << endl; //assert(e.getId() == EMPTY_EMPLOYEE_ID); //assert(e.getName() == ""); cout << endl; // return 0 to indicate successful completion return 0; }