C++

Forum

 
Creating a Hashing program?

jag64 (7)
Writing a C++ program that:

(1) defines and implements a hash class that constructs a 23 element array (may be implemented using a vector, a deque, or a list, if you prefer), storing strings, using the following hash function:

(ascii(first_letter) + ascii (last_letter))%23



So, for example, the word "robby" would be

ascii('r) = 114 + ascii ('y') = 121 = 235%23 = 5

In this example, an attempt would be made to store "robby" in position 5. In the event of a collision, the word would be stored in the first available location, so if there is a collision in location 5, an attempt would be made to store the word in location 6. If there is a collision in location 6, try location 7 and so on.

(2) the driver program should:

a. query the user for fifteen words and store them using the hash technique described above.

b. print out the contents of each position of the array (or vector, deque, or whatever you used), showing vacant as well as filled positions. Remember, only 15 of the 23 positions will be filled.

c. repeatedly query the user for a target word, hash the word, check for its inclusion in the list of stored words, and report the result. Continue doing this task until the user signals to stop (establish a sentinel condition).


My problem is I do not know which would be the easiest to store the data. I was thinking Vectors. The second problem is that I do not know how I would even begin to write this program, I'm at a loss for this hashing idea. Any helpful coding would be appreciated. Thanks!
Last edited on
ResidentBiscuit (4459)
Why would you use a list? Kind of beats the purpose of hashing in the first place.

As far as writing a hash map:

1) Get hash code from key (in this case a string) using whatever hash algorithm you want. Looks like that's provided.
2) Modulus it to the size you need (in this case 23), which also looks to be done in the ascii() function.
3) Go to index retrieved from step 2. If occupied, check to see if occupied by same key. If so, just replace the object. If occupied with some other key, move on to next index and repeat.
jag64 (7)
Rather unsure of where I'm getting this ascii function from. or how to use it, what do I need to include in the driver?
cire (8284)
There is no ascii function.

ascii('r) = 114 simply means that the ascii value of 'r' is 114.

1
2
3
4
5
6
 
#include <iostream>

int main()
{
    std::cout << (('r' + 'y') % 23) << '\n' ;
}
 
5
jag64 (7)
Alright, that makes a lot more sense now. I wasn't sure if there was something I was missing, because our notes didn't show ascii as a specific function.

I plan on using Vector, would that make more sense for this? A list and Queue seem rather more involved than necessary for this program.
cire (8284)
You definitely want a vector as the bucket container. Probably as the buckets as well. (So, a vector of vectors.)
jag64 (7)
I'm stuck..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXARRAYSIZE = 23;
class hasher
{
	public:
		hasher::hasher(string word)
		{
			hashword = word;
			firstlet = 0;
			lastlet = 0;
			fill (elementarray.begin(),elementarray.begin()+23,0);
		}
		
	void hashthis(char firstlet, char lastlet, string hashword)
		{
			sum = (firstlet+lastlet)%23;
			if (elementarray.at(sum) == 0)
			elementarray.at(sum) = hashword;
		}
			
						
	protected:
		vector<string> elementarray[MAXARRAYSIZE];
		int sum;
		string hashword;
		char firstlet, lastlet;
};



These are the errors I'm getting. I have no idea what I'm doing wrong with this.

ghp7.cpp: In constructor `hasher::hasher(std::string)':
ghp7.cpp:26: error: request for member `begin' in `((hasher*)this)->hasher::elementarray', which is of non-class type `std::vector<std::string, std::allocator<std::string> >[23]'
ghp7.cpp:26: error: request for member `begin' in `((hasher*)this)->hasher::elementarray', which is of non-class type `std::vector<std::string, std::allocator<std::string> >[23]'
ghp7.cpp: In member function `void hasher::hashthis(char, char, std::string)':
ghp7.cpp:32: error: request for member `at' in `((hasher*)this)->hasher::elementarray', which is of non-class type `std::vector<std::string, std::allocator<std::string> >[23]'
ghp7.cpp:33: error: request for member `at' in `((hasher*)this)->hasher::elementarray', which is of non-class type `std::vector<std::string, std::allocator<std::string> >[23]'
cire (8284)
elementArray is an array of vectors. It doesn't have a member function named begin.

[Edit: And you can ignore the mention of buckets, previously. It isn't really relevant for what your assignment requires.]
Last edited on
jag64 (7)
I've got a new problem. Been trying to at least get most of this working by commenting out the non compiling parts...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXARRAYSIZE = 23;
class Hasher
{
	public:
		Hasher::Hasher()
		{
			hashword = "";
			firstlet = 0;
			lastlet = 0;
			elementarray[MAXARRAYSIZE];
		}
		
	void hashthis(char firstlet, char lastlet, string hashword)
		{
			//sum = (firstlet+lastlet)%23;
			//if (elementarray.at(sum) < 1)
			elementarray.at(1) = hashword;
		}
		
	void display()
		{
		//for(i=0;i<23;i++)
		 cout<<elementarray.at(1);
		}
						
	protected:
		vector<string> elementarray;
		int sum, i;
		string hashword;
		char firstlet, lastlet;
};



int main()
{
 Hasher hash;
 char firstletter,lastletter;
 int leng;
 string word;
 cout<<"Input a word for the Vector: ";
 cin>>word;
 firstletter = word.at(0);
 leng=word.length();
 lastletter = word.at(leng-1);
  
 hash.hashthis(firstletter,lastletter,word);
 hash.display();
}


This is what I get..

Input a word for the Vector: Dog
Aborted (core dumped)
Last edited on
cire (8284)
1
2
3
4
5
6
7
 
		Hasher::Hasher()
		{
			hashword = "";
			firstlet = 0;
			lastlet = 0;
			elementarray[MAXARRAYSIZE];
		}


elementarray is empty. elementarray[MAXARRAYSIZE] tries to access an element of elementarray that doesn't exist.

Neither sum, nor i, nor hashword, nor firstlet, nor lastlet should be members of your Hasher class. The hash function probably shouldn't be a member either, but that's a design choice.

1
2
3
 
		Hasher::Hasher() : elementarray(MAXARRAYSIZE)
		{
		}
Last edited on
jag64 (7)
Awesome! Thanks, I was thinking of the constructor for this as my class, but this fixes everything. Now to continue plugging in the rest of the code.
jag64 (7)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MAXARRAYSIZE = 23;
class Hasher
{
	public:
	
		Hasher::Hasher() : elementarray(MAXARRAYSIZE)
		{
			for(i=0;i<23;i++)
				elementarray.at(i) = "0";
		}
		
	void hashthis(char firstlet, char lastlet, string hashword)
	{
		sum = (firstlet+lastlet)%23;
		if (elementarray.at(sum) == "0")
			elementarray.at(sum) = hashword;
		else if (elementarray.at(sum) != "0")
		{
			do{			
				i = 0;
				if (sum > 21)
					sum = 0;
				else
					sum++;
				if (elementarray.at(sum) == "0")
				{
					elementarray.at(sum) = hashword;
					i++;
				}
			}while (i != 1) ;
		}
	}
	void hashcheck(char firstlet, char lastlet, string hashword)
	{
		sum = (firstlet+lastlet)%23;
		if (elementarray.at(sum) == "0")
			cout<<hashword<<" is not in this list."<<endl;
		else if (elementarray.at(sum) != "0")
			if (elementarray.at(sum) == hashword)
				cout<<hashword<<" was found at position #"<<sum+1<<" on list."<<endl;
			else
			{
				check = 0;
				do{			
					i = 0;
				if (sum > 21 && check == 0)
				{
					sum = 0;
					check = 1;
				}
				else 
					sum++;
				if (sum > 21 && check == 1)
				{
				cout<<hashword<<" is not in this list."<<endl;
				sum = 0;
				i++;
				}
				if (elementarray.at(sum) == hashword)
				{
					cout<<hashword<<" was found at position #"<<sum+1<<" on list."<<endl;
					i++;
				}
			}while (i != 1) ;
			}
	}
	
	void display()
	{
		for(i=0;i<23;i++)
		if (elementarray.at(i) == "0")
			cout<<i+1<<". "<<"empty"<< endl;
		else
			cout<<i+1<<". "<<elementarray.at(i)<< endl;
	}
						
	protected:
		vector<string> elementarray;
		int sum, i, check;
		string hashword;
		char firstlet, lastlet;
};




int main()
{
 Hasher hash;
 char firstletter,lastletter;
 int leng, i;
 string word;
 
 cout<<"Input 15 different words for the hashing program. ";
 for (i=0;i<15;i++)
	{
	cout<<"#"<<i+1<<" ";
	cin>>word;
	firstletter = word.at(0);
	leng=word.length();
	lastletter = word.at(leng-1);
	hash.hashthis(firstletter,lastletter,word);
	}
	
	hash.display();
	
	cout<<endl;
	cout<<"Enter a word to see if it is stored in the program."<<endl;
	cout<<"When you are done enter '0'."<<endl;
	
do{

	i =0;
	cout<<"Enter word: ";
	cin>>word;
	if (word != "0")
	{
		firstletter = word.at(0);
		leng=word.length();
		lastletter = word.at(leng-1);
		hash.hashcheck(firstletter,lastletter,word);
	}
	else
		i++;
	
 }while (i != 1);


 }


This is what I wrote, seems to work perfectly to what was asked above. If you guys see anyone wrong with it please let me know.
cire (8284)
cire wrote:
Neither sum, nor i, nor hashword, nor firstlet, nor lastlet should be members of your Hasher class.


I would expect the hash function and the function to check if a string is stored to take only a std::string.

Topic archived. No new replies allowed.