I am writing a program for a class assignment that tests 3 hashing functions with 3 different double hash functions (so 1/1, 1/2, 1/3, 2/1, 2/2, etc.), and the end goal is to output the test results of each pairing to a file via console command "exename > Results.txt" as per my professors instructions. I'm reaching final testing but my program will go into main, complete the nested for loop once, output the test results of the first hash function pairing, then the program ends with no error. I have messed with Visual Studio 12's debugger for hours and am no closer to finding a solution than I was when I started. When I run the program via console, it outputs "Unable to open data file. Program terminating", even though when stepping through the program it never once enters that for loop. Any ideas? Thanks!
P.S. I'm aware that some methods used in this program may be unconventional or not necessarily the easiest/best way to implement this, but I'm required to confine to my professor's standards.
UPDATE: I added a cout line in the getline for loop and can now see that the test completes once, then the next time around it repeats that for loop 41 times and exits instead of finishing all 50. Looks like we're getting somewhere.
Here is my output:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950ERROR1 Testing hash function 1 using double hash 1. Total collisions = 360. |||||||-------------------------------------|||||||||||||||-----|||||||||||||||--------|||||||||||||
1234567891011121314151617181920212223242526272829303132333435363738394041
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
#define TABLESIZE 100
#define KEYSIZE 4
#define EMPTYKEY "----"
#define DATAFILE "P4DATA.txt"
using namespace std;
struct HashStruct
{
char key[5];
int data;
};
void InitTable(HashStruct hashT[], int TableSize);
int Hash_1(char *key);
int Hash_2(char *key);
int Hash_3(char *key);
int ProbeDec_1(char *key);
int ProbeDec_2(char *key);
int ProbeDec_3(char *key);
int HashInsert(HashStruct T[], char *key, int data, int hNum, int dhNum);
int main(void){
int hashNum, dHashNum, count;
ifstream *inFile;
HashStruct T[100]; // Hash table srray of 100 data structures
char line[64];// Array to hold lines read from file
char key[5]; // Array to hold 4-character keys
int data; // Integer data
char filename[15];
strcpy(filename, DATAFILE);
for(hashNum = 0; hashNum < 3; hashNum++){
for(dHashNum = 0; dHashNum < 3; dHashNum++){
InitTable(T, TABLESIZE);
inFile = new ifstream();
inFile->open(filename, ifstream::in);
if(!inFile->is_open()){
cout << "Unable to open data file. Program terminating\n";
return 0;
}
count = 0;
for(int i = 0; i < 50; i++){
inFile->getline(line, 64, '\n');
sscanf(line, "%s %d", key, &data);
count += HashInsert(T, key, data, hashNum, dHashNum);
}
cout << "Testing hash function " << hashNum + 1 << " using double hash " << dHashNum + 1 << ".\n";
cout << "Total collisions = " << count << ".\n";
for(int i=0; i < 100; i++){
if(strcmp(T[i].key, EMPTYKEY))
cout << "|";
else
cout << "-";
}
cout << "\n\n";
inFile->close();
delete inFile;
}
}
return 1;
}
int HashInsert(HashStruct T[], char *key, int data, int hNum, int dhNum){
int testNum = (hNum * 3) + dhNum;
int colCount = 0;
int hashIndex, probeDec;
switch(testNum){
case 0 : // Hash function 1 -- Double hash 1 (linear probing)
hashIndex = Hash_1(key);
probeDec = ProbeDec_1(key); // Function just returns 1
break;
case 1 : // Hash function 1 -- Double hash 2
hashIndex = Hash_1(key);
probeDec = ProbeDec_2(key);
break;
case 2 : // Hash function 1 -- Double hash 3
hashIndex = Hash_1(key);
probeDec = ProbeDec_3(key);
break;
case 3 : // Hash function 2 -- Double hash 1 (linear probing)
hashIndex = Hash_2(key);
probeDec = ProbeDec_1(key); // Function just returns 1
break;
case 4 : // Hash function 2 -- Double hash 2
hashIndex = Hash_2(key);
probeDec = ProbeDec_2(key);
break;
case 5 : // Hash function 2 -- Double hash 3
hashIndex = Hash_2(key);
probeDec = ProbeDec_3(key);
break;
case 6 : // Hash function 3 -- Double hash 1 (linear probing)
hashIndex = Hash_3(key);
probeDec = ProbeDec_1(key); // Function just returns 1
break;
case 7 : // Hash function 3 -- Double hash 2
hashIndex = Hash_3(key);
probeDec = ProbeDec_2(key);
break;
case 8 : // Hash function 3 -- Double hash 3
hashIndex = Hash_3(key);
probeDec = ProbeDec_3(key);
break;
}
while(strcmp(T[hashIndex].key, EMPTYKEY) != 0){
colCount++;
hashIndex -= probeDec; // Decrementing was chosen you could also choose to
if(hashIndex < 0) // increment and wrap back to the beginning of the table.
hashIndex = hashIndex + TABLESIZE;
}
strcpy(T[hashIndex].key, key);
T[hashIndex].data = data;
return colCount;
}
void InitTable(HashStruct hashT[], int TableSize){
int i;
for(i=0; i<TableSize; i++){
strcpy(hashT[i].key, EMPTYKEY);
hashT[i].data = 0;
}
}
int Hash_1(char *key){
int hash = 0;
int prime = 29;
int index = 0;
for(int i = 0; i < 4; i++){
hash = (key[i]-'0')*prime;
for(int j = (3-i); j > 0; j--){
hash *= prime;
}
}
index = hash % TABLESIZE;
return index;
}
int Hash_2(char *key){ // Folding
int hash = 0;
int index = 0;
hash = (((key[0]-'0')+(key[1]-'0'))*37) +
(((key[1]-'0')+(key[2]-'0'))*47) +
(((key[2]-'0')+(key[3]-'0'))*67);
index = hash % TABLESIZE;
return index;
}
int Hash_3(char *key){ //Middle Squaring
int hash = 0;
int index = 0;
hash = ((key[1]-'0') + (key[2]-'0'));
hash *= hash;
index = hash % TABLESIZE;
return index;
}
int ProbeDec_1(char *key){
return 1;
}
int ProbeDec_2(char *key){
int dhash = 0;
int index = 0;
dhash = ((key[0]-'0')*97) + ((key[1]-'0')*83);
index = dhash % TABLESIZE;
return index;
}
int ProbeDec_3(char *key){
int dhash = 0;
int index = 0;
dhash = (((key[0]-'0')*29) + ((key[1]-'0')*59) +
((key[2]-'0')*79) + ((key[3]-'0')*89));
index = dhash % TABLESIZE;
return index;
}
