C++

Forum

 
C++ HashTable

needhelp101 (19)
I'm new to C++ and this is my first time dealing with hash tables. I am doing this for a homework assignment. I believe that my insert function is not working properly. Here is my class HTable, and insert() function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
class HTable
{
public:
	HTable(int size);
	void insert(  const string &s);
	void remove(const string &key);
	void print() const;

	
private:
	vector<list<string>> List;
	int currSize;
	int tableSize;
	int hash(string &key)const;
	int hash_string( const string &s );
	int hashFunction(string key);
	int HTableSize;
	//int *status_arr;
	ostream &   operator <<( ostream &);
	static int const TABLE_SIZE = 97;				//The hash table size
	HTable *hashTable[TABLE_SIZE];
	bool getKey(string searchKey) const;
};


here is my insert()
1
2
3
4
5
6
7
8
9
10
11
 
inline void HTable::insert(  const string &s )
{
	vector<list<string> > ::iterator it;
	for (it = List.begin(); it != List.end(); it++)
	{
		if( find( (*it).begin(), (*it).end(), s ) == (*it).end() )
		{
			(*it).push_back(s);
		}
	}
}


also this is the sample output in which my teacher provided
 size of the Hash Table? 33
HTable::HTable( 33 )
read strings from a file
name of file to read from? strings.txt
read commands from a file
name of file to read from? cmds.txt
  0:    the
  1:
  2:
  3:
  4:
  5:    is      test
  6:
  7:
  8:    number
  9:
 10:
 11:    This    fair
 12:
 13:    strings
 14:
 15:
 16:
 17:
 18:    of
 19:    appear
 20:
 21:
 22:
 23:    that
 24:
 25:
 26:
 27:    paragraph
 28:    in
 29:    beginning
 30:    second
 31:    a
 32:

a       xyz
  0:    the
  1:
  2:    xyz
  3:
  4:
  5:    is      test
  6:
  7:
  8:    number
  9:
 10:
 11:    This    fair
 12:
 13:    strings
 14:
 15:
 16:
 17:
 18:    of
 19:    appear
 20:
 21:
 22:
 23:    that
 24:
 25:
 26:
 27:    paragraph
 28:    in
 29:    beginning
 30:    second
 31:    a
 32:
unknown command: 'x'

d       test
  0:    the
  1:
  2:    xyz
  3:
  4:
  5:    is
  6:
  7:
  8:    number
  9:
 10:
 11:    This    fair
 12:
 13:    strings
 14:
 15:
 16:
 17:
 18:    of
 19:    appear
 20:
 21:
 22:
 23:    that
 24:
 25:
 26:
 27:    paragraph
 28:    in
 29:    beginning
 30:    second
 31:    a
 32:

a       test
  0:    the
  1:
  2:    xyz
  3:
  4:
  5:    is      test
  6:
  7:
  8:    number
  9:
 10:
 11:    This    fair
 12:
 13:    strings
 14:
 15:
 16:
 17:
 18:    of
 19:    appear
 20:
 21:
 22:
 23:    that
 24:
 25:
 26:
 27:    paragraph
 28:    in
 29:    beginning
 30:    second
 31:    a
 32:

d       paragraph
  0:    the
  1:
  2:    xyz
  3:
  4:
  5:    is      test
  6:
  7:
  8:    number
  9:
 10:
 11:    This    fair
 12:
 13:    strings
 14:
 15:
 16:
 17:
 18:    of
 19:    appear
 20:
 21:
 22:
 23:    that
 24:
 25:
 26:
 27:
 28:    in
 29:    beginning
 30:    second
 31:    a
 32:

d       second
  0:    the
  1:
  2:    xyz
  3:
  4:
  5:    is      test
  6:
  7:
  8:    number
  9:
 10:
 11:    This    fair
 12:
 13:    strings
 14:
 15:
 16:
 17:
 18:    of
 19:    appear
 20:
 21:
 22:
 23:    that
 24:
 25:
 26:
 27:
 28:    in
 29:    beginning
 30:
 31:    a
 32:
Press any key to continue . . .


Also, this is the output I am receiving. 

size of the Hash Table? 33
read strings from a file
name of file to read from? strings.txt
read commands from a file
name of file to read from? cmds.txt

a       xyz
unknown command: 'x'

d       test

a       test

d       paragraph

d       second
Press any key to continue . . .


as you can see, mine is completely off from my teachers output. I believe it's involving my insert(), or maybe could be my print function which I am having trouble coding. cannot seem to figure out how to code the print function.
debil123 (3)
you are not close to implement the insert function, to what I understand should be your hash table specification.
1. vector<list<string> > ::iterator it;
it- is now iterator on the vector type, not on the list type.
it is pointless to compare it with the list iterators which returned when you do List.begin() or List.end().
2. I understand you should have vector of lists of strings. did you try to iterate on the vector, or on the list? because you should doing it on both, to find the correct place to insert the new element.
3. (*it).begin() may be legal, but I think it is not what you wanted to do.
needhelp101 (19)
I can see it visually on what I am supposed to do, but I cannot seem to translate it into coding. This is what I can see on what to do. first push strings into the list, then push back theses lists into vector of lists. But cannot seem to translate this into code
cire (8284)
An insert should involve hashing the string to determine which bucket (list element) the string should be stored in.

If it is required not to insert multiple copies of the same key that should be enforced in your insert function.
needhelp101 (19)
I'm not sure how to really code that. I'm still very new to C++. My knowledge is very limited.
cire (8284)
I'm not sure how to really code that. I'm still very new to C++. My knowledge is very limited.


Write down what you need to do. Write code to accomplish it.

To insert a unique key into a hash table I need to:

hash the key to determine which bucket the key would be stored in.
search the bucket to see if the key is already in the bucket.
if it's not in the bucket, store it in the bucket.

Hashing the key will involve one of the three member functions with 'hash' in the name that take a string as an argument. (You might also want to pare down the number of functions. You only need one: unsigned hash(const std::string& key) const. I use unsigned because it doesn't seem likely you'll want it to return a negative number with which to index the vector.)

By the way, you should be using the hash function to determine the bucket to search in your previously posted remove function as well.
Last edited on
needhelp101 (19)
to be honest with you, I am not sure how to translate what you are saying into code.
cire (8284)
to be honest with you, I am not sure how to translate what you are saying into code.


hash the key to determine which bucket the key would be stored in.
search the bucket to see if the key is already in the bucket.
if it's not in the bucket, store it in the bucket.

It's pretty straightforward.

1
2
3
4
5
6
7
8
9
10
11
 
void HTable::insert(  const string &s )
{
    // hash the key to determine which bucket the key would be stored in.
    int bucketNum = hash(s) ;

    list<string>& bucket = List[bucketNum] ;
    
    // search the bucket to see if the key is already in the bucket.
    if ( bucket.empty() || bucket.end() == find(bucket.begin(), bucket.end(), s) )
        bucket.push_back(s) ;           // if it's not in the bucket, store it in the bucket.
}
Last edited on
needhelp101 (19)
ok, awesome. Thanks. When I test this out, and call my hash(), i am receiving an error saying that my vector subscript it is out of range. is my hash() correct?


1
2
3
4
5
6
7
8
9
10
11
12
13
 
inline unsigned HTable::hash(const std::string& key) const
{
	int hashVal = 0;
	for(int i = 0; i < key.length(); i++)
	{
		hashVal = 37 * hashVal + key[i];
	}
	hashVal %= tableSize;

	if(hashVal < 0)
		hashVal += HTableSize;
	return hashVal;
}


actually, nevermind with this code here. I see the problem. In the line
hashVal %= tableSize
should be this instead
hashVal %=HTableSize
Last edited on
needhelp101 (19)
but I do need help with the print function though. if you don't mind. im thinking traversing through List, and printing out the contents.
needhelp101 (19)
would some like this be along the lines of how print() should be?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
inline void HTable::print()
{
	list<string>::iterator itr;
	for(int i = 0; i < List[i].size(); i++ )
	{
		int print = 0;
		for(itr = List[i].begin(); itr != List[i].end(); itr++)
		{
			cout << (*itr) << " ";
			print = 1;
		}
		if(print)
		{
			cout << " in bucket: " << i << endl;
		}
	}
}


Last edited on
Topic archived. No new replies allowed.