From ba837332565a2b4a667bd1350a062e1007d4a5c4 Mon Sep 17 00:00:00 2001 From: Adam Carpenter <53hornet@gmail.com> Date: Sat, 3 Dec 2016 10:47:17 -0500 Subject: Uploading programming assignments -- typeset assignments may come later --- Assign5/hash.cpp | 78 ++++++++++++++++ Assign5/keys.txt | 9 ++ Assign5/keys2.txt | 9 ++ Assign5/keys3.txt | 12 +++ Assign5/keys4.txt | 11 +++ Assign5/run.sh | 8 ++ Assign5/table.cpp | 267 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ Assign5/table.hpp | 27 ++++++ 8 files changed, 421 insertions(+) create mode 100644 Assign5/hash.cpp create mode 100644 Assign5/keys.txt create mode 100644 Assign5/keys2.txt create mode 100644 Assign5/keys3.txt create mode 100644 Assign5/keys4.txt create mode 100644 Assign5/run.sh create mode 100644 Assign5/table.cpp create mode 100644 Assign5/table.hpp diff --git a/Assign5/hash.cpp b/Assign5/hash.cpp new file mode 100644 index 0000000..2e63984 --- /dev/null +++ b/Assign5/hash.cpp @@ -0,0 +1,78 @@ +#include +#include"table.hpp" + +/* hash.cpp by Adam Carpenter - acarpent - acarpenter@email.wm.edu + +This program is a driver that utilizes the table.cpp hash table. It +reads in input from the command line (or fed in from file) and creates +an array containing the given items. It then creates hash table objects +and hashes the items into each of these objects using the four different +methods described in class: linear probing, quadratic probing, double +hashing, and separate chaining. It then calls for printing out all of +the hash tables. + +*/ + +void readInput(int inputArray[]) { + /* Reads input from command line or from a given file of keys + into an array of size 10 (the maximum number of input items. + */ + std::cout << "\nHash Tables!\n\n"; + std::cout << "Enter up to 10 positive integers to be hashed one at a time.\nWhen you are done, enter -1\n"; + int tmp = 0; + int count = 0; + + while (tmp != EMPTY && count < 10) { + std::cin >> tmp; + inputArray[count] = tmp; + count++; + } + + // Print entered list + std::cout << "\nEntered integers: "; + + for (int i = 0; i < 10; i++) { + + if (inputArray[i] != EMPTY) { + std::cout << inputArray[i] << " "; + } + + } + + std::cout << "\n"; +} + +int main() { + /* main is the primary driver of the hash table demonstration. + It is the caller of all of the subsequent functions and hash + table methods. + */ + int integerList[10] = {EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY}; + readInput(integerList); + + // Linear Probing + Table linearTable(false); + linearTable.hashLinear(integerList); + std::cout << "\nLinear Probing Hash Table: \n"; + linearTable.printTable(false); + + // Quadratic Probing + Table quadraticTable(false); + quadraticTable.hashQuad(integerList); + std::cout << "\nQuadratic Probing Hash Table: \n"; + quadraticTable.printTable(false); + + // Double Hashing + Table doubleTable(false); + doubleTable.hashDouble(integerList); + std::cout << "\nExtra Credit: Double Hashing Hash Table: \n"; + doubleTable.printTable(false); + + // Separate Chaining + Table chainTable(true); + chainTable.hashChaining(integerList); + std::cout << "\nExtra Credit: Separate Chaining Hash Table: \n"; + chainTable.printTable(true); + + return 0; +} diff --git a/Assign5/keys.txt b/Assign5/keys.txt new file mode 100644 index 0000000..9699b3a --- /dev/null +++ b/Assign5/keys.txt @@ -0,0 +1,9 @@ +4371 +1323 +6173 +4199 +4344 +9679 +1989 +-1 + diff --git a/Assign5/keys2.txt b/Assign5/keys2.txt new file mode 100644 index 0000000..8ab3f83 --- /dev/null +++ b/Assign5/keys2.txt @@ -0,0 +1,9 @@ +4379 +1329 +6179 +4199 +4349 +9679 +1989 +-1 + diff --git a/Assign5/keys3.txt b/Assign5/keys3.txt new file mode 100644 index 0000000..245f188 --- /dev/null +++ b/Assign5/keys3.txt @@ -0,0 +1,12 @@ +4371 +1323 +6173 +4199 +4344 +9679 +1989 +1788 +2001 +9000 +-1 + diff --git a/Assign5/keys4.txt b/Assign5/keys4.txt new file mode 100644 index 0000000..c6ea24d --- /dev/null +++ b/Assign5/keys4.txt @@ -0,0 +1,11 @@ +4379 +1329 +6179 +4199 +4349 +9679 +1989 +9 +2009 +-1 + diff --git a/Assign5/run.sh b/Assign5/run.sh new file mode 100644 index 0000000..312e3a1 --- /dev/null +++ b/Assign5/run.sh @@ -0,0 +1,8 @@ +clear +g++ *.cpp -lm -o hash +./hash < keys.txt +./hash < keys.txt > myout.txt +./hash < keys2.txt > myout2.txt +./hash < keys3.txt > myout3.txt +./hash < keys4.txt > myout4.txt + diff --git a/Assign5/table.cpp b/Assign5/table.cpp new file mode 100644 index 0000000..33a44de --- /dev/null +++ b/Assign5/table.cpp @@ -0,0 +1,267 @@ +#include +#include"table.hpp" + +Table::Table(bool useChaining = false) { + /* This constructor takes in a boolean value as a parameter. + The boolean value useChaining represents + whether or not the user intends on using separate chaining + as their hashing method. When set to true, the constructor + will create a table object represented by an array of pointers + to the heads of linked lists, a structure more appropriate + for separate chaining. When useChaining is false, the + constructor defaults to a simple array-based hash table. + */ + + if (useChaining) { + + // initialize array of linked list heads + for (int i = 0; i < 10; i++) { + tableHeads[i] = NULL; + } + + } + else { + unhashable = false; + + // initialize array with 'empty' values + for (int i = 0; i < 10; i++) { + tableArray[i] = EMPTY; + unhashableList[i] = EMPTY; + } + + } + +} + +void Table::hashLinear(int intList[]) { + /* Implementation of hash table insertion using linear probing. + This method takes in an array of integers (10 items max) and hashes + them into a table object using linear probing for conflict resolution. + This means that the probe distance is equal to the number of probing + attempts, or, f(i) = i. An item cannot be hashed into the table if the probing + results in cycling around to the original insertion location again. + */ + int count = 0; + int slotIndex = 0; + int originalSlotIndex; + bool probeFinished; + + while (intList[count] != EMPTY && count < 10) { + slotIndex = intList[count] % 10; + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + } + else { // slot taken; must probe + originalSlotIndex = slotIndex; + probeFinished = false; + + while (!probeFinished) { + slotIndex++; // f(i) = i + + if (slotIndex > 9) { // wrap around array + slotIndex = slotIndex - 10; + } + + if (slotIndex == originalSlotIndex) { // gone over whole array; end probing + unhashable = true; + unhashableList[count] = intList[count]; + probeFinished = true; + } + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + probeFinished = true; + } + + } + + } + + count++; + } + +} + +void Table::hashQuad(int intList[]) { + /* Implementation of hash table insertion using quadratic probing. + This method takes in an array of integers (10 items max) and hashes + them into a table object using quadratic probing for conflict resolution. + This means that the probe distance is equal to the number of probing + attempts squared, or, f(i) = i^2. An item cannot be hashed into the table if the probing + results in cycling around to the original insertion location again. + */ + int count = 0; + int probeCount = 0; + int slotIndex = 0; + int originalSlotIndex; + bool probeFinished; + + while (intList[count] != EMPTY && count < 10) { + slotIndex = intList[count] % 10; + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + } + else { // slot taken; must probe + originalSlotIndex = slotIndex; + probeCount = 0; + probeFinished = false; + + while (!probeFinished) { + probeCount++; + slotIndex = originalSlotIndex + (probeCount * probeCount); // f(i) = i^2 + + while (slotIndex > 9) { // wrap around array multiple times + slotIndex = slotIndex - 10; + } + + if (probeCount > 5) { + unhashable = true; + unhashableList[count] = intList[count]; + probeFinished = true; + } + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + probeFinished = true; + } + + } + + } + + count++; + } + +} + +void Table::hashDouble(int intList[]) { + /* Implementation of hash table insertion using double hashing. + This method takes in an array of integers (10 items max) and hashes + them into a table object using a second hash function for conflict resolution. + The second hash function is equivalent to f(x) = 7 - x % 7. An item cannot be + hashed into the table if the probing results in cycling around to the original + insertion location again. + */ + int count = 0; + int probeCount = 0; + int slotIndex = 0; + int originalSlotIndex; + bool probeFinished; + + while (intList[count] != EMPTY && count < 10) { + slotIndex = intList[count] % 10; + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + } + else { // slot taken; must probe + originalSlotIndex = slotIndex; + probeCount = 0; + probeFinished = false; + + while (!probeFinished) { + probeCount++; + slotIndex = originalSlotIndex + (probeCount * (7 - intList[count] % 7)); // f(x) = 7 - x % 7 + + while (slotIndex > 9) { // wrap around array + slotIndex = slotIndex - 10; + } + + if (slotIndex == originalSlotIndex) { // gone over whole array; end probing + unhashable = true; + unhashableList[count] = intList[count]; + probeFinished = true; + } + + if (tableArray[slotIndex] == EMPTY) { // slot empty; insert item + tableArray[slotIndex] = intList[count]; + probeFinished = true; + } + + } + + } + + count++; + } + +} + +void Table::hashChaining(int intList[]) { + /* Implementation of hash table insertion using separate chaining. + This method takes in an array of integers (10 items max) and hashes + the items into a table object using separate chaining for conflict + resolution. This means for each insertion index, a linked list exists + where all of the values that hash to that index are inserted at the head + of the linked list. + */ + int count = 0; + int slotIndex = 0; + NODE *newHead; + + while (intList[count] != EMPTY && count < 10) { + newHead = new NODE(); + slotIndex = intList[count] % 10; + newHead->key = intList[count]; + newHead->next = tableHeads[slotIndex]; + tableHeads[slotIndex] = newHead; + count++; + } + +} + +void Table::printTable(bool useChaining = false) { + /* A method for printing out the contents of a hash table object + that creates a visual representation of the hash table and its + contents and prints them to the console (or a file if directed). + This method takes in a boolean value letting the method know + whether or not to print a separately-chained linked hash table + with a linke list or a hash table based on an array (ex. linear + probing). + */ + if (useChaining) { + NODE *node = new NODE(); + + // print visual hash table of items from linked lists + for (int i = 0; i < 10; i++) { + std::cout << "[" << i << "]" << "-> "; + + for (node = tableHeads[i]; node != NULL; node = node->next) { + std::cout << node->key << " -> "; + delete node; // have to clean up nodes from memory + } + + std::cout << "_\n"; + } + + } + else { + // print visual hash table of items from array + for (int i = 0; i < 10; i++) { + std::cout << "[" << i << "]" << " "; + + if (tableArray[i] != EMPTY) { + std::cout << tableArray[i]; + } + + std::cout << "\n"; + } + + // print items that could not be inserted + if (unhashable) { + std::cout << "The following item(s) could not be inserted: "; + + for (int i = 0; i < 10; i++) { + + if (unhashableList[i] != EMPTY) { + std::cout << unhashableList[i] << " "; + } + + } + + std::cout << "\n"; + } + } +} diff --git a/Assign5/table.hpp b/Assign5/table.hpp new file mode 100644 index 0000000..e8c6336 --- /dev/null +++ b/Assign5/table.hpp @@ -0,0 +1,27 @@ +/* Header file containing definitions for the table object class. +Also contains the NODE structure for the linked list used for +separate chaining. NODE objects contain a key and a pointer to +another NODE representing the next node. I created a constant +called EMPTY that uses the int -1 to represent an empty slot in a table. +*/ +static const int EMPTY = -1; + +struct NODE { + int key; + NODE *next; +}; + +class Table { + private: + int tableArray[10]; + int unhashableList[10]; + bool unhashable; + NODE *tableHeads[10]; + public: + Table(bool); + void hashLinear(int[]); + void hashQuad(int[]); + void hashDouble(int[]); + void hashChaining(int[]); + void printTable(bool); +}; -- cgit v1.2.3