Computer Programming: C++ programs

The example code hashes integers using modulo the array size. It throws an exception when the array is nearly full.

1. Replace throwing an exception when the array is full with calling a rehash() method that is called by the addItem() method whenever at least half of the slots in the array are occupied by elements (load factor greater than 0.5). You do not need to make the new array size a prime number, but it should be at least twice the size of the original array. Remember that this code deletes items by marking them with the flag DELETED, so you need to make sure that you do not move deleted items into the new array.

2. Create a hash class that hashes variable names using linear probing. To keep the problem simple, only consider names containing lower case letters. You will want to initialize the array to nullptr instead of EMPTY and define a string for DELETED.

3. Change your hash table to use separate chaining instead of open addressing. Change the display method to properly display your table with the items at a given index on the same line of the output.

Example Code:

#include  #include  #include  // uncomment the test you want to run //#define INT_HASH //#define STRING_HASH //#define CHAIN_TEST #ifdef INT_HASH #include "HashTable.h" #endif #ifdef STRING_HASH #include "StringHash.h" #endif #ifdef CHAIN_HASH #include "ChainHash.h" #endif using namespace std; int main(int argc, const char * argv[]) { const int NUM_VALUES = 10; int values[NUM_VALUES] = {10, 5, 30, 15, 20, 40, 60, 25, 50, 35}; #ifdef INT_HASH // this tests the starting hashing code, it will fail with // an overflow_error until you implement the re-hash method HashTable intHash(6); // place 10 items in a 6 item array, after rehashing // the array should expand and not throw an error try { for(int i = 0; i < NUM_VALUES; i++) intHash.addValue(values[i]); } catch (std::length_error & ex) { cout << "Inserting failed with exception: " << ex.what() << endl; exit(1); } // dump the array cout << "Displaying the array before find and delete" << endl; cout << intHash.displayTable() << endl; // now see if find works cout << "Looking for 4, should not find -- " << (intHash.findValue(4)?"found":"not found") << endl; cout << "Looking for 5, should find -- " << (intHash.findValue(5)?"found":"not found") << endl; // now delete 5 and see if still found cout << "Deleting 5, should work -- " << (intHash.removeValue(5)?"found":"not found") << endl; // now looking again cout << "Looking for 5 again, should not find -- " << (intHash.findValue(5)?"found":"not found") << endl; // dump the array cout << endl << "Displaying the array after deleting 5, s/b replaced with \"dele\"" << endl; cout << intHash.displayTable() << endl; #endif //INT_HASH string string_values[NUM_VALUES] = {"dog", "god", "cat", "act", "horse", "cow", "elephant", "otter", "seal", "ales"}; #ifdef STRING_HASH // this tests the string hashing code // change this to your class name StrHashTable stringHash; // place 10 items in a hash table try { for(int i = 0; i < NUM_VALUES; i++) stringHash.addValue(string_values[i]); } catch (std::length_error & ex) { cout << "Inserting failed with exception: " << ex.what() << endl; exit(1); } // dump the array cout << "Displaying the array before find and delete" << endl; cout << stringHash.displayTable() << endl; // now see if find works cout << "Looking for pig, should not find -- " << (stringHash.findValue("pig")?"found":"not found") << endl; cout << "Looking for otter, should find -- " << (stringHash.findValue("otter")?"found":"not found") << endl; // now delete 5 and see if still found cout << "Deleting otter, should work -- " << (stringHash.removeValue("otter")?"found":"not found") << endl; // now looking again cout << "Looking for otter again, should not find -- " << (stringHash.findValue("otter")?"found":"not found") << endl; // dump the array cout << endl << "Displaying the array after deleting otter, s/b replaced with \"dele\"" << endl; cout << stringHash.displayTable() << endl; #endif //STRING_HASH #ifdef CHAIN_TEST // this tests the chained string hashing code // change this to your class name ChainHashTable chainHash; // place 10 items in a hash table try { for(int i = 0; i < NUM_VALUES; i++) chainHash.addValue(string_values[i]); } catch (std::length_error & ex) { cout << "Inserting failed with exception: " << ex.what() << endl; exit(1); } // dump the array cout << "Displaying the array before find and delete" << endl; cout << chainHash.displayTable() << endl; // now see if find works cout << "Looking for pig, should not find -- " << (chainHash.findValue("pig")?"found":"not found") << endl; cout << "Looking for otter, should find -- " << (chainHash.findValue("otter")?"found":"not found") << endl; // now delete 5 and see if still found cout << "Deleting otter, should work -- " << (chainHash.removeValue("otter")?"found":"not found") << endl; // now looking again cout << "Looking for otter again, should not find -- " << (chainHash.findValue("otter")?"found":"not found") << endl; // dump the array cout << endl << "Displaying the array after deleting otter, should no longer be there"" << endl; cout << chainHash.displayTable() << endl; #endif // CHAIN_TEST return 0; }