blob: 33a44de5a73a920bca526cc859f0f25e23efdb09 (
plain) (
tree)
|
|
#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";
}
}
}
|
