Well, I had to make a program which used 2 hashing functions on keys that it gets from a file and stores them on a table.
The first function should let the user define M (uisng function h(k) = k mod M) and then applies a second hashing function which is predefined (in this case, h2(k) = 8 - k mod 8).
The following code that I whipped up seems to work fine, but this is however a kind of "rough draft" that I made. Hashing is a completely new concept to me and I am curious if I am doing it right (the first hash function gives me the same results as examples given in my book, but the book doesnt have any double hashing examples).
Also, I am just looking for areas where I could improve. I am considering changing the arrays to linked lists, or perhaps even binary trees, but only if that alternative would prove more efficient.
Any other ideas are welcomed.
Code:
#include<iostream>
#include<cmath>
#include<cctype>
#include<fstream>
using namespace std;
int first_hash(int a[], int i, int x, int M)
{
if (i > -1)
return x = (a[i] + 32 * first_hash(a, i-1, x, M)) % M;
else
return (0);
}
int second_hash(int a[], int i, int x)
{
if (i > -1)
{
x = (a[i] + 32 * second_hash(a, i-1, x)) % 8;
return 8 - x;
}
else
return (0);
}
int do_thehash(char a[], int c, int M)
{
char d;
int h = 0, tmp[20];
for (int i = 0; a[i]; i++, h++) // reads each char and converts to a corresponding int (A = 1, B = 2, etc)
{
d = a[i];
if(isupper(d))
tmp[h] = int(d) - 64;
else
tmp[h] = int(d) - 96;
}
h = h - 1;
c = first_hash(tmp, h, c, M) + second_hash(tmp, h, c);
return c;
}
void table(int a[], int c, int i)
{
a[i] = c;
i++;
}
void sort_table(int a[], int x)
{
int j = 0, tmp = 0;
for (int i = 1; i < x; i++)
{
tmp = a[i]; j = i;
while(a[j-1] > tmp)
{
a[j] = a[j -1]; j--;
}
a[j] = tmp;
}
}
int main(void)
{
char input[20];
int c= 0, M, x = 0, hash_table[100];
/**** File stuf(will move later) ****/
char ofilename[16], ifilename[16];
ofstream write;
ifstream read;
cout << "Enter an input file: ";
cin >> ifilename;
read.open(ifilename);
if(read.fail())
{
cout << "That file does not exist!" << endl;
exit(1);
}
cout << "Enter a value for M: ";
cin >> M;
while (read >> input)
{
c = do_thehash(input, c, M);
table(hash_table, c, x);
cout << c << endl;
x++;
}
sort_table(hash_table, x);
cout << "Enter an output file to write to: ";
cin >> ofilename;
write.open(ofilename);
int j = 0;
for(int i = 0; j < x; i++)
{
if (i == (hash_table[j]) - 1)
{
cout << 'x' << " -- " << x << " -- "<< hash_table[j] << endl;
write <<'x'<< endl;
j++;
}
else
write << endl;
}
write.close();
cout << "File written" << endl;
return 0;
}