Assignment description: Implement a Hash Table of strings. The table is stored a

Question

Assignment description: Implement a Hash Table of strings. The table is stored as an array of pointers to list of strings.

Tasks:
A. Write a class that implements a Hash Table of strings. The table is stored as an array of pointers to lists of strings.
Your Hash Table class should include the following functions:
- A function insert(s) that adds the string to the table, if it is not already there.
- A function remove(s) that removes the string from the table if it is there.
- A function find(s) that returns the string if the string s is in the table.
- A function size() that returns the number of words in the dictionary.
- A helper hash function to compute the hash code of a string. The function takes a string as its parameter, and adds up the ASCII values of all the characters in that string to get an integer as the hash value. You can convert the string into lowercases before the hashing just for simplicity.
Here is one possible hashing implementation using the string class in STL:
int hash( const string s )
{

   int value = 0;
   for (int i = 0; i < s.length(); i++ )
value += static_cast(s.[i]);
return (value % table.size);
}
- a constructor that accepts the size of the table as a parameter.

B. Write a test driver program that uses (and tests) your hash table class.
1. Build the dictionary. The program reads strings from a text file that contains the words to be inserted into the dictionary. The file usually contains pairs of (word, definition) but for simplicity, let's ignore the definition part.
- Create an array of appropriate size to store these words. Try to keep load factor below 60% to avoid search inefficiency. Use the separate chaining method to resolve the collision.
- Keep a counter to save the number of collisions that occur during the building process. Print out the number of collisions and number of words at the end of building.
2. Exercise the ADT operations: It prompts the user to enter words for searching or removing. Print messages about the result of operations accordingly.
3. Example text file for testing: aberration, abhor, acquiesce, alacrity, amiable, appease, arcane, avarice, brazen, brusque, cajole, callous, candor, chide, circumspect, clandestine, coerce, coherent, complacency, confidant, connive, cumulative, debase, decry

Explanation / Answer

#include <iostream>
#include <string>
#include <math.h>
#include <array>
#include <vector>
using namespace std;

int stringValue(string tString) {
int val=0;
for (int i = 0; i < tString.length(); i++) {
char c=tString[i];
val+=pow(10,i)*((int)c-97);
}
return val;
}

class hashMap{
public:
vector<string> v[33];

void insert(string s){
int value = stringValue(s);
int key = value%33;
v[key].push_back(s);
}

void remove(string s){
int value = stringValue(s);
int key = value%33;
vector<string> tempList;
while (!v[key].empty()) {
if (v[key].back() != s){
tempList.push_back(v[key].back());
v[key].pop_back();
}
else{
v[key].pop_back();
}
}
v[key]=tempList;
}

bool find(string s){
int value = stringValue(s);
int key = value%33;
vector<string> tempList;
int b=0;
while(!v[key].empty()){
string tempStr=v[key].back();
v[key].pop_back();
if(tempStr==s){
tempList.push_back(s);
b=1;
}
else{
tempList.push_back(tempStr);
}
}
if (b==1) {
return true;
}
else{
return false;
}
}

int size1(){
int count=0;
for (int i = 0; i < 33; i++) {
if(!v[i].empty()){
vector<string> tempStr;
while (!v[i].empty()) {
tempStr.push_back(v[i].back());
v[i].pop_back();
count++;
}
v[i]=tempStr;
}
}
return count;
}
};

int main() {
hashMap dictionary;
dictionary.insert("institute");
dictionary.insert("aberration");
dictionary.insert("abhor");
dictionary.insert("acquiesce");
dictionary.insert("alacrity");
dictionary.insert("amiable");
dictionary.insert("appease");
dictionary.insert("arcane");
dictionary.insert("avarice");
cout<<dictionary.size1()<<endl;
cout<<"If return 1 then true else false: "<<dictionary.find("institute")<<endl;
dictionary.remove("institute");
cout<<dictionary.size1()<<endl;
cout<<"If return 1 then true else false: "<<dictionary.find("institute")<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.