Thread: Double Hashing

  1. #1
    Registered User carrja99's Avatar
    Join Date
    Oct 2002
    Posts
    56

    Talking 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;
    }

  2. #2
    Lead Moderator kermi3's Avatar
    Join Date
    Aug 1998
    Posts
    2,595
    you forgot the [/code] at the end...added if for you.
    Kermi3

    If you're new to the boards, welcome and reading this will help you get started.
    Information on code tags may be found here

    - Sandlot is the highest form of sport.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Copying 2-d arrays
    By Holtzy in forum C++ Programming
    Replies: 11
    Last Post: 03-14-2008, 03:44 PM
  2. Conversion From C++ To C
    By dicon in forum C++ Programming
    Replies: 2
    Last Post: 06-10-2007, 02:54 PM
  3. need some help with last part of arrays
    By Lince in forum C Programming
    Replies: 3
    Last Post: 11-18-2006, 09:13 AM
  4. newbie needs help with code
    By compudude86 in forum C Programming
    Replies: 6
    Last Post: 07-23-2006, 08:54 PM
  5. Unknown Math Issues.
    By Sir Andus in forum C++ Programming
    Replies: 1
    Last Post: 03-06-2006, 06:54 PM