Hash Table

This is a discussion on Hash Table within the C++ Programming forums, part of the General Programming Boards category; I'm accepting an input file with names in it. It looks like: Code: Steve Spark Notes I'm trying to put ...

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    Hash Table

    I'm accepting an input file with names in it. It looks like:
    Code:
    Steve
    Spark
    Notes
    I'm trying to put the names into a hash table. Here is my code:
    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    using namespace std;
    
    int hash(char *str, int table_size);
    
    int main(int argc, char* argv[])
    {
    	string array1[12];
    	char name[20];
    	
    	
    	ifstream inFile ( argv[1] );
    
    	if ( !inFile.is_open() )
    	{
    		cout << "Could not open file." << endl;
    	}
    	else
    	{
    		inFile.get(name, 20) >> array1[hash(name, 12)];
    		
    
    		for(int i = 0; i < 12 ; i++)
    		{
    			cout << endl;
    			cout << i << ": " << array1[i];
    			cout << endl;
    		}
    	}
    	
    
    	cin.get();
    	return 0;
    
    }
    int hash(char *str, int table_size)
    {
    	int sum = 0;
    
    	/* Make sure a valid string passed in */
    	if (str == NULL)
    	{
    		return -1;
    	}
    
    	/* Sum up all the characters in the string */
    	for( ; *str; str++)
    	{
    		sum += *str;
    	}
    
    	/* Return the sum mod the table size */
    	return sum % table_size;
    }
    The program compiles fine. But, when i run it (using windows command prompt) it crashes.
    I think the problem is how i'm declaring name:
    Code:
    char name[20];
    and how it is being used with the hash function:
    Code:
    hash(name, 12)
    I can't figure out how to fix this.

    I also have two other smaller issues.
    1) When i read the names in from the file, it skips the first name.
    Code:
    inFile.get(name, 20) >> array1[0];
    This will read Sparks into the first position instead of Steve.
    2) The names aren't being hashed in the same spot that the example from this site gives:
    http://www.sparknotes.com/cs/searchi.../section1.html

    Any help would be appreciated.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    I think you should change:
    Code:
    inFile.get(name, 20) >> array1[hash(name, 12)];
    to:
    Code:
    inFile.get(name, 20);
    array1[hash(name, 12)] = name;
    That said, have you considered using std::tr1::unordered_set?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Thanks, that fixed it.
    *Note: i meant for .get to be .getline.

    I've ran into another problem.
    I have to store the persons name and the number of votes they have (the number of time their names appear in the input file) in the table. So, i thought i would create a struct to do this.
    Code:
    struct Candidate
    {
    	string firstName;
    	int votes;
    };
    So, this would allow me to hash a candidate entry into the table, allowing me to store the name and the number of votes. So, i need to read a name in from the file, create a new Candidate (if one does not already exist), and set their name. Here is how i tried to do that:
    Code:
    Candidate array1[12];
    
    //Read names in from file and hash them into table.
    while(!inFile.eof())
    {
    	inFile.getline(name, 20);
    	Candidate name;
    	name.firstName = name;
    	name.votes = 1;
    	array1[hash(name,12)] = name;	
    	
    }
    So, i create a new Candidate with:
    Code:
    Candidate name;
    Then, i try to set the name to the name read in from the file with:
    Code:
    name.firstName = name;
    This gives me the first error.
    Then i set the votes to 1. Then i try put the entry into the table with:
    Code:
    array1[hash(name,12)] = name;
    This gives me the second error.
    If i change the name of the Candidate to a random lettter/word like:
    Code:
    Candidate a;
    a.firstName = name;
    a.votes = 1;
    array1[hash(name,12)] = a;
    It will work. However, i believe it is just overwriting a everytime, so when i need to refer back to the entry to increase the number of votes, i won't be able to (i could be wrong here).
    These are the errors i receive:

    Error 1 error C2679: binary '=' : no operator found which takes a right-hand operand of type 'Candidate' (or there is no acceptable conversion)
    Error 2 error C2664: 'hash' : cannot convert parameter 1 from 'Candidate' to 'char *'

    "That said, have you considered using std::tr1::unordered_set?"
    I'm not sure what that is.

    Thanks
    IDE - Visual Studio 2005
    Windows XP Pro

  4. #4
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Nevermind. I figured it out.
    IDE - Visual Studio 2005
    Windows XP Pro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Dictionary in C# to hash table in C?
    By dinoman in forum C Programming
    Replies: 2
    Last Post: 04-12-2009, 09:23 PM
  2. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 05:06 PM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  4. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 06:54 PM
  5. Not sure on hash table memory allocations
    By Thumper333 in forum C Programming
    Replies: 3
    Last Post: 09-27-2004, 09:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21