0

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);
}

Edited by dmr9215: n/a

3
Contributors
3
Replies
4
Views
6 Years
Discussion Span
Last Post by Radical Edward
0

did you put cout and tried to confirm if the insert was happening correctly? Once the insert happens it makes no difference if the input was file or array.

0

so I would think as well (i've tried it) but for whatever reason it doesn't recognize it. i've gone as far as printing out all the values in the hash table (say- 80 hello) then doing a search and printing out what it is searching (80 hello it prints out) but then it says it could not find the value in the table

0

If array input works and file input does not, the strings you are getting from file are not the same as expected, or you are not searching for a string that was in the file. Verify your data before troubleshooting the hash table.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.