summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Assign5/hash.cpp78
-rw-r--r--Assign5/keys.txt9
-rw-r--r--Assign5/keys2.txt9
-rw-r--r--Assign5/keys3.txt12
-rw-r--r--Assign5/keys4.txt11
-rw-r--r--Assign5/run.sh8
-rw-r--r--Assign5/table.cpp267
-rw-r--r--Assign5/table.hpp27
8 files changed, 421 insertions, 0 deletions
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<iostream>
+#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<iostream>
+#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);
+};
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 08:42:24 +0000