-
Hash Table
I'm accepting an input file with names in it. It looks like:
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:
and how it is being used with the hash function:
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.
-
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?
-
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:
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
-
Nevermind. I figured it out.