I'm implementing my own hashtable class as practice, but I'm having trouble retrieving values from the table that were inserted from a file. When I do so from an array however, the program finds the values without a problem... I've tried modifying my hash function to adapt for any potential additional characters that might be added of which I'm not aware, but to no avail... here's the code
#include <fstream>
#include <vector>
#include <string>
#include <iostream>
using namespace std;
int primes [21] = {1,3, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169};
class hashTable {
public:
hashTable(int size = 100)
{
data.resize(getPrime(size));
capacity = data.size();
hashItem *x = new hashItem();
for(int i=0; i<capacity; i++)
data[i] = *x;
filled = 0;
}
bool contains(const string &key)
{
if(findPos(strToLow(key)) != -1)
return true;
else return false;
}
void *getPointer(const string &key, bool *b = NULL);
int insert(const string &key)//, void *pv = NULL)
{
if(contains(strToLow(key)))
return 1;
// string g = key;
// if(&pv != NULL)
// pv = &g;
//string *r = static_cast<string*>(pv);
int val = hash(strToLow(key));
hashItem *x = new hashItem(strToLow(key));
while(data[val].occupied())// && data[val].getKey() != key) not necessary because of contains(key)
{
val++;
if(val >= capacity)
val-=capacity;
}
data[val] = *x;
//cout<<val<<endl;
data[val].setOcc(true);
filled++;
//cout<<"capacity\t"<<capacity<<"\tfilled\t"<<filled<<endl;
if(filled >= capacity/2)
{
if(rehash())
return 0;
else
return 2;
}
else
return 0;
}
bool remove(const string &key)
{
if(!contains(strToLow(key)))
return false;
else
{
int x = findPos(strToLow(key));
data[x].setDel(true);
data[x].setOcc(false);
filled--;
}
}
void print()
{
/*
string txt ("");
for(int i =0; i<capacity; i++)
if(data[i].occupied())
//file<<i<<"\t"<<data[i].getKey()<<endl;
txt+= i+"\t"+data[i].getKey()+"\n";
//file<<"there are "<<filled<<" entries"<<endl;
return txt;*/
cout<<"the capacity is\t"<<capacity<<endl;
for(int i =0; i<capacity; i++)
if(data[i].occupied())
cout<<i<<"\t"<<data[i].getKey()<<endl;
cout<<"there are "<<filled<<" entries"<<endl;
}
string strToLow(string str)
{
for(int i =0; i<str.size(); i++)
if((int)str[i] >=65 && (int)str[i]<=90)
str[i]+=32;
return str;
}
private:
class hashItem {
public:
string key;
bool isOccupied;
bool isDeleted;
// void *pv;
hashItem(const string &k = "")//, string *pt = NULL)
{
key = k;
isOccupied = false;
isDeleted = false;
//pv = pt;
}
string getKey(){
// cout<<key<<endl;
return key;
}
bool occupied(){
return isOccupied;
}
bool deleted(){
return isDeleted;
}
// void* getPt(){
// return pv;
// }
void setKey(const string &k){
key =k;
}
void setDel(bool x){
isDeleted = x;
}
void setOcc(bool x){
isOccupied = x;
}
// void setPt(void *r){
// pv =r;
// }
};
vector<hashItem> data; // The actual entries are here.
int capacity; // The current capacity of the hash table.
int filled; // Number of occupied items in the table.
int hash(const string &key)
{
//cout<<capacity<<endl;
int val = 0;
for(int i =0; i+1<key.size(); i++)
{
// cout<<"hi"<<endl;
//cout<<key[i]<<endl;
val =37 * val + key[i];
//cout<<val<<"\n"<<endl;
}
val %= capacity;
if(val < 0)
val+=capacity;
//cout<<val<<endl;
return val;
}
int findPos(const string &key)
{
string str = key.substr(0,key.size()-1);
cout<<str<<endl;
int val = hash(key);
//cout<<"val "<<val<<endl;
//cout<<data.at(val).getKey()<<endl;
while(data[val].occupied() && data[val].getKey() != str)
{
//cout<<key<<endl;
val++;
if(val >= capacity)
val-=capacity;
}
if(data[val].getKey() == str && !(data[val].deleted()))
return val;
else
return -1;
}
bool rehash()
{
int oldCap = capacity;
vector<hashItem> oldArr = data;
data.resize(getPrime(2*oldCap));
capacity = data.size();
int r;
for(int i =0; i<capacity; i++)
{
data.at(i).setOcc(false);
data.at(i).setKey("");
}
filled = 0;
for(int j =0;j<oldCap; j++)
if(oldArr[j].occupied())
{
r = insert(oldArr.at(j).getKey());
//cout<<r<<endl;
if(r != 0)
return false;
}
//cout<<"rehash done\t"<<capacity<<endl;
return true;
}
static unsigned int getPrime(int size)
{
int pow = 2;
int ind = 0;
while(size > pow)
{
pow*=2;
ind++;
}
if(ind>21)
return NULL;
return primes[ind];
}
/*
vector<hashItem> getArr(){
return data;
}*/
};
int main()
{
//for one reason or another to get it working out of the array the loop in hash function goes all the way to size
//whereas to get it to work correctly out of a file you need to go from 0 to size-1
hashTable *table = new hashTable();
int k;
int cap=0;
// string arr[15] = {"aaa","l","m","flotsy","hello","kaka","kalabrotski","kalakaasje","pipi","shnotsy","toodles","zizi","dutch","something","headache"};
// for(int i=0; i<15; i++)
// {
// k = (*table).insert(arr[i]);
// if(k==0)
// cap++;
// else break;
// }
// (*table).print();
string line;
string word;
string temp;
char file[50];
char file2[50];
char ofile[50];
cout << "Enter name of input file: ";
cin >> file;
fstream myfile;
myfile.open(file);
//read files into hashtable
if (myfile.is_open())
{
while (! myfile.eof() )
{
getline (myfile,line);
k = (*table).insert(line);
if(k!=0)
continue;
}
myfile.close();
}
else
cout<<"unable to open file"<<endl;
(*table).print();
if((*table).contains("HELLOf"))
cout<<"kaka"<<endl;
else
cout<<"aint ther"<<endl;
/*
cout<<"Enter name of output file: ";
cin>> file_op;
ofstream ofile(file_op);
ofile.close();
if((*table).contains("something"))
cout<<"kaka"<<endl;
*/
//(*table).print();
// cout << "Enter name of input file: ";
// cin >> file2;
// ifstream myfile2 (file2);
// if (myfile2.is_open())
// {
// while (! myfile2.eof() )
// {
// getline (myfile2,word, ' ');
// temp = strToLow(word);
// if(!(*table).contains("precocious"))
// cout<<temp<<"\n\tthis word does not exist"<<endl;
// else
// cout<<temp<<"\texists!!"<<endl;
// }
// }
// file_op<<(*table).print();
// file_op.close();
// kak.print();
// if(kak.contains("zizi"))
// cout<<"success"<<endl;
// if(kak.remove("kaka"))
// cout<<"deleted successfully"<<endl;
// cout<<"Enter name of output file: ";
// cin>> ofile;
// ofstream file_op(ofile);
}
