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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
|
#include <iostream>
#include <cstddef>
#include <string>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
void print_menu();
template <typename KEY, typename VALUE> //Defining template values
class Entry //Defining Entry Class
{
template<typename K, typename V> friend class HashTable; //Including HashTable function as friend
private:
KEY key;
VALUE value;
Entry * next_entry;
public:
/*** Constructors ***/
Entry(void) : key(KEY()), value(VALUE()), next_entry(NULL) {}
//If you would like you can convert constructors to have this look
Entry(KEY key, VALUE value)
{
this->template key = key;
this->template value = value;
this->template next_entry = NULL;
}
Entry(KEY key, VALUE value, Entry * next) : key(key), value(value), next_entry(next) {}
//accessors
KEY get_key() { return key; }
VALUE get_value() { return value; }
Entry * get_next_entry() { return next_entry; }
//mutators
void set_key(KEY key) { this.key = key; }
void set_value(VALUE value) { this.value = value; }
void set_next_entry(Entry * entry) { this.next_entry = entry; }
};
template<typename K, typename V>
class HashTable
{
private:
int N;
Entry<K,V> **hash_table; //Make sure you understand this line
public:
HashTable()
{
this->N = 10000;
hash_table = new Entry<K, V> * [this->N];
for (int i = 0; i < this->N; i++)
hash_table[i] = NULL;
}
HashTable(int N)
{
this->N = N;
hash_table = new Entry<K, V> * [this->N];
for (int i = 0; i < this->N; i++)
hash_table[i] = NULL;
}
/* hashcose string to int */
int hashcode(string s);
/* hashcode int to int */
int hashcode(int i);
/* hascode char to int */
int hashcode(char c);
/* hascode long to int */
int hashcode(unsigned long ul);
/* basic compression function */
int compression(int hc);
/* insert e into hash table */
void insert(Entry<K, V> * e);
/* replace e1 with e2 */
void replace(Entry<K, V> * e1, Entry<K, V> * e2);
/* find e and return */
Entry<K, V> * find(Entry<K, V> * e);
/* remove e from the table */
void remove(Entry<K, V> * e);
/* if grow = 1 increase the table
* otherwise decrease the table
*/
void resize(bool grow);
double compute_load_factor();
int longest_chain_length();
};
template<typename K, typename V>
int HashTable<K, V>::hashcode(string s)
{
unsigned long hash = 5381;
for (size_t i = 0; i < s.size(); ++i)
{
hash = 33 * hash + (unsigned char)s[i];
}
return hash;
}
template<typename K, typename V>
int HashTable<K, V>::hashcode(int i)
{
}
template<typename K, typename V>
int HashTable<K, V>::hashcode(char c)
{
}
template<typename K, typename V>
int HashTable<K, V>::hashcode(unsigned long u1)
{
}
template<typename K, typename V>
int HashTable<K, V>::compression(int hc)
{
}
template<typename K, typename V>
void HashTable<K, V>::insert(Entry<K, V> * e)
{
}
template<typename K, typename V>
void HashTable<K, V>::replace(Entry<K, V> * e1, Entry<K, V> * e2)
{
}
template<typename K, typename V>
void HashTable<K, V>::remove(Entry<K, V> * e)
{
}
template<typename K, typename V>
void HashTable<K, V>::resize(bool grow)
{
}
template<typename K, typename V>
double HashTable<K, V>::compute_load_factor()
{
}
template<typename K, typename V>
int HashTable<K, V>::longest_chain_length()
{
}
/* I recommend you make a temp main for testing all of your boundary
* cases. I reserve the right to change the main function. I promise
* it will only call the function prototypes provided; which means, you
* cannot change the prototypes.
*/
int main()
{
//seed the random number generator
srand(42);
int menu_choice;
do
{
HashTable<unsigned long, string> table_01(10000);
unsigned long key;
string value;
Entry<unsigned long, string> * e;
// Fill the table with random entries
for (int i = 0; i < 10000; i++)
{
/* create a random entry */
key = (sizeof(int) < sizeof(long)) ? (static_cast<int>(((unsigned long)rand()) << (sizeof(int) * 8)) | rand()) : rand();
value = "";
for (int j = 0; j < (rand() % 45 + 1); j++)
value += 'a' + rand() % 26;
cout << "Value " << i << " has been created. " << endl;
e = new Entry<unsigned long, string>(key, value);
cout << value << endl;
//table_01.insert(e);
}
print_menu();
cin >> menu_choice;
while (menu_choice < 0 && menu_choice > 1)
{
cout << "Error: invalid input, try again: ";
cin >> menu_choice;
}
if (menu_choice == 1)
{
template<typename K, typename V>
HashTable<K, V>.hashcode(s);
}
//cout << "Longest Chain: " << table_01.longest_chain_length() << endl;
//cout << "Load Factor: " << table_01.compute_load_factor() << endl;
} while (menu_choice != 0);
return 0;
}
void print_menu()
{
cout << "1. View hash codes of converted strings " << endl;
cout << "2. View hash codes of converted ints " << endl;
cout << "3. View hash codes of converted characters " << endl;
cout << "4. View hash codes of converted longs " << endl;
cout << "5. Insert element into hash table" << endl;
cout << "6. Replace element 1 with element 2" << endl;
cout << "7. Search for an element and return it" << endl;
cout << "8. Remove an element from the table" << endl;
cout << "9. Compute the load factor" << endl;
cout << "10. Returns the value of the longest chain in the table" << endl;
cout << "11." << endl;
cout << "12." << endl;
cout << "0. Exit the program " << endl;
}
|
