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 6 Years Ago by dmr9215: n/a

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.

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

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 article has been dead for over six months. Start a new discussion instead.