CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    May 2013
    Posts
    11

    How to search for an object that has been hashed

    Ran into a logic issue with my hashing program that stores a state object. It's storing the object just fine now but I need to be able to search for it.
    The user enters a state name and I'm supposed to be able to search for it. I am at a complete loss on how to handle hashing objects. Does anybody have a link with an example for me to look at?

    here is the main
    Code:
    #include <iostream>
    #include <fstream>
    #include <string>
    #include "hashT.h"
    #include "stateData.h"
    
    using namespace std;
    
    int hashFunc(string name, int size);
    
    int main()
    {
    	hashT<StateData> HashTable(50);
    	int size = 15;
    
    	ifstream infile;
    
    	infile.open("states.txt");
    	if(!infile)
    	{
    		cout << "Error reading states file.\n";
    		exit(1);
    	}
    
    	char ch;
    	int year, order, key;
    	string state, capitol;
    	bool found;
    
    	getline(infile, state);
    
    	while(infile)
    	{
    		getline(infile, capitol);
    		infile >> year;
    		infile >> order;
    		StateData temp;
    		temp.setStateInfo(state, capitol, year, order);
    		infile.get(ch);
    		key = hashFunc(state, size);
    		HashTable.insert(key, temp);
    
    		getline(infile, state);
    	}
    
    	HashTable.print();
    
    	cout<<"Enter item to be deleted: ";
    	getline(cin, state);
    	cout<<endl;
    	key = hashFunc(state, size);        
    
    	HashTable.remove(key, dtemp);       //here is where I am lost. how do I get the StateData object dtemp?  Do I need to completely
    
    	HashTable.print();                          // replace my search function? It requires a StateData object.
    
    
    	infile.close();
    	system("pause");
    	return 0;
    
    }
    
    int hashFunc(string name, int size)
    {
    	int i, sum, len;
    	i= 0;
    	sum = 0;
    	len = name.length();
    	for (int k=0; k < 15 - len; k++)
    		name = name + ' ';
    	for (int k = 0; k < 5; k++)
    	{
    		sum = sum + static_cast<int>(name[i]) * 128 * 128
    			+ static_cast<int>(name[i+1]) * 128
    			+ static_cast<int>(name[i+2]);
    		i = i+3;
    	}
    	return sum % size;
    }
    hashT class
    Code:
    private:
        elemType *HTable;		//pointer to the hash table
        int *indexStatusList;	//pointer to the array indicating
    							//the status of a position in the
    							//hash table
        int length;				//number of items in the hash table
        int HTSize;				//maximum size of the hash table
    };
    
    
    template <class elemType>
    void hashT<elemType>::insert(int hashIndex, elemType& rec)
    {
    	int pCount;
    	int inc;
    
    	pCount = 0;
    	inc = 1;
    
    	while(indexStatusList[hashIndex] == 1
    		  && HTable[hashIndex] != rec
    		  && pCount < HTSize / 2)
    	{
    		cout <<"inc = " << inc << endl;
    		pCount++;
    		hashIndex = (hashIndex + inc ) % HTSize;
    //		cout << "new hashIndex = " << hashIndex << endl;
    		inc = inc + 2;
    	}
    
    
    	if(indexStatusList[hashIndex] != 1)
    	{
    		HTable[hashIndex] = rec;
    		cout << "HTable["<< hashIndex <<"]" <<" = " << rec << endl;
    		indexStatusList[hashIndex] = 1;
    		length++;
    	}
    	else
    		if(HTable[hashIndex] == rec)
    			cerr<<"Error: No duplicates are allowed"<<endl;
    		else
    			cerr<<"Error: The table is full. "
    			    <<"Unable to resolve the collision"<<endl;
    }
    
    template <class elemType>
    void hashT<elemType>::search(int& hashIndex, const elemType& rec, bool& found)
    {
    	int pCount;
    	int inc;
    
    	pCount = 0;
    	inc = 1;
    
    	while(indexStatusList[hashIndex] != 0
    		  && HTable[hashIndex] != rec 
    		  && pCount < HTSize / 2)
    	{
    		pCount++;
    		hashIndex = (hashIndex + inc ) % HTSize;
    		inc = inc + 2;
    	}
    
    	if(indexStatusList[hashIndex] == 1 && HTable[hashIndex] == rec )
    	{
    		hashIndex = hashIndex;
    		found = true;
    	}
    	else
    		found = false;
    }
    
    template <class elemType>
    bool hashT<elemType>::isItemAtEqual(int hashIndex, const elemType& rec)
    { 
    	return(HTable[hashIndex] == rec);
    }
    
    template <class elemType>
    void hashT<elemType>::retrieve(int hashIndex, elemType& rec)
    {	
    	if(indexStatusList[hashIndex] == 1)
    		rec = HTable[hashIndex];
    }
    
    template <class elemType>
    void hashT<elemType>::remove(int hashIndex, const elemType& rec)
    {
    	bool found;
    
    	search(hashIndex,rec,found);
    
    	if(found)
    	{
    		indexStatusList[hashIndex] = -1;
    		length--;
    	}
    	else
    		cerr<<"The item to be deleted is not in the list."<<endl;
    }
    StateData class
    Code:
    private:
    	string name;
    	string capitol;
    	int yearAdmit;
    	int order;
    
    };
    #endif
    
    	StateData StateData::getStateData(string n)      //once I've figured out the main, I think I can do this
    		{ 
    			if (name == n)
    				return this;
    	}
    
    
    	bool StateData::operator==(StateData &left)
    	{          return (this->name == left.name);		  }
    
    
    	bool StateData::operator!=(StateData &left)
    	{          return (this->name != left.name);     }

  2. #2
    Join Date
    May 2013
    Posts
    11

    Re: How to search for an object that has been hashed

    Made some major changes to my code. I've got my searching function rewritten now but it won't find my StateData object. I felt like I've gotten a handle on it but I must be missing something. If anybody can point it out to me, I'd appreciate it.

    Code that calls the search
    Code:
    	cout<<"Enter item to be deleted: ";
    	getline(cin, state);
    	cout<<endl;
    	key = hashFunc(state, size);
    	HashTable.search(key, state, found);
    HashT search
    Code:
    //search function
    void hashT<elemType>::search(int& hashIndex, string n, bool& found)
    {
    	int pCount;
    	int inc;
    	//elemType& rec;
    	pCount = 0;
    	inc = 1;
    	bool sfound = false;
    	StateData temp = HTable[hashIndex];
    	elemType& rec = temp.getStateData(n, sfound);
    	
    	while(indexStatusList[hashIndex] != 0
    		&& (!sfound)
    		  && HTable[hashIndex] != rec 
    		  && pCount < HTSize / 2)
    	{
    		pCount++;
    		hashIndex = (hashIndex + inc ) % HTSize;
    		temp = HTable[hashIndex];
    		rec = temp.getStateData(n, sfound);
    		inc = inc + 2;
    	}
    
    	if(indexStatusList[hashIndex] == 1 && HTable[hashIndex] == rec )
    	{
    		cout << "Found state: " << rec.getName() << endl;
    		hashIndex = hashIndex;
    		found = true;
    	}
    	else
    		found = false;
    }
    
    
    //insert function which is working
    template <class elemType>
    void hashT<elemType>::insert(int hashIndex, elemType& rec)
    {
    	int pCount;
    	int inc;
    
    	pCount = 0;
    	inc = 1;
    
    	while(indexStatusList[hashIndex] == 1
    		  && HTable[hashIndex] != rec
    		  && pCount < HTSize / 2)
    	{
    		cout <<"inc = " << inc << endl;
    		pCount++;
    		hashIndex = (hashIndex + inc ) % HTSize;
    //		cout << "new hashIndex = " << hashIndex << endl;
    		inc = inc + 2;
    	}
    
    
    	if(indexStatusList[hashIndex] != 1)
    	{
    		HTable[hashIndex] = rec;
    		cout << "HTable["<< hashIndex <<"]" <<" = " << rec << endl;
    		indexStatusList[hashIndex] = 1;
    		length++;
    	}
    	else
    		if(HTable[hashIndex] == rec)
    			cerr<<"Error: No duplicates are allowed"<<endl;
    		else
    			cerr<<"Error: The table is full. "
    			    <<"Unable to resolve the collision"<<endl;
    }
    StateData
    Code:
    //copy constructor
    	StateData::StateData(StateData &temp)
    	{
    		name = this->name;
    		capitol = this->capitol;
    		yearAdmit = this->yearAdmit;
    		order = this->order;
    	}
    
    	StateData StateData::getStateData(string n, bool &found)
    	{ 
    			if (name == n)
    				found = true;
    			return *this;
    	}
    
    
    	bool StateData::operator==(StateData &left)
    	{          return (this->name == left.name);		  }
    
    
    	bool StateData::operator!=(StateData &left)
    	{          return (this->name != left.name);     }

  3. #3
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626

    Re: How to search for an object that has been hashed

    The thing to keep in mind is that a hash is not guaranteed to return a unique value. It is a goal to reduce collisions as much as possible but you need to account for the fact that 2 different keys will result in the same hash value, so you need to have a fallback of some sort when this happens. This implies that you will always also need to have your key stored in the hash item to make sure that the item you found by hashcode is actually the item you were looking for.

    There are various solutions with various degrees of efficiency. A simple solution is taking the next higher (or lower) item in the table. Other solutions involve Secondary tables, having the hash table result in linked lists (this is what MFC's CMap does), rehashing, ...

    A simple way of avoiding colisions at the cost of more memory is increasing the table size.

    So essentially when you want to store an item in a hash table:
    hash the key, check if the table item is taken, if no then store, if yes, then do whatever your fallback method is.

    and to find an item
    hash the key, if the table item is not taken, then the item is not in the table, if it is, then check the key, if the key matches then you've found the item, otherwise, do whatever your fallback method is and recheck the key until your fallback is empty or you found a matching key.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured