# Double Hashing

• 03-28-2003
carrja99
Double Hashing
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; }```
• 03-28-2003
kermi3
you forgot the [/code] at the end...added if for you.