Thread: Hash Table

  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
    28,413
    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?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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, 07: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