dynamically allocated Hash Table

[pfunk35]

Hey guys I am trying to wrap my head around implementing this. I have an abstract based class and three derived classes. I also have a templated hash table class(using chaining as my collision resolution method, an array of stl lists), and a class to parse commands from a file, this also holds the instantiation of the hash table. My question is that since my command parsing class's constructor instantiates the hash table in the main driver(unable to modify) how can I make this dynamically allocated using data from the file? thanks guys let me know if I didnt explain clearly or if you need more code.

template<class T>
class hashTable{

public:
	hashTable(int size);
	~hashTable();

	void toInsert(T* newItem);
	void toDelete(std::string name);
	T* find(int index, std::string name);
	int hashFunc(std::string name);
	void dump();
	friend ostream& operator<<(ostream& os, const T& RHS);
	
private:

	int tableSize;		//hash table size 
	person* table;		// array-based hashTable
};

template<class T>
hashTable::hashTable(int size){
	
	tableSize = size;
	table = new list<T*>[tableSize];

}

int main(){ //int argc, char* argv[]){
    //string commandsFileName( "lab4-commands-short.tab");
    string commandsFileName( "lab4-commands.tab");
    //string commandsFileName( "lab4-commands-test.tab");

    RecordsOffice records;														
    cout << "Importing " << commandsFileName << endl;
    records.importRecords(commandsFileName);
    
    return 0;
}

inputDataFile.open(commandsFileName.c_str());									 //open File Stream
    assert(inputDataFile);															//if not found print error                  
    
	inputDataFile>>size;

	
		//Main Control Loop
    while(inputDataFile.peek() != EOF && inputDataFile>>command)
    {
        
		
		//Delete Student, Administrator, Faculty
        if(command == 'D'){
            
            inputDataFile>>name;
            
			
			people.toDelete(name);

            cout<<"Note: Removing "<<name<<"..."<<endl<<endl;
			
									 
		}.........

class RecordsOffice{

public:
	RecordsOffice(){};		//constructor
	~RecordsOffice(){};		//destructor
	void importRecords(std::string fileName);
private:

		hashTable<person*> people;		//hash table instantiation

};

[rodiongork]

Many implementations simply allocate some initial size (for example 16) and then if while adding more and more data the number of elements exceeds some threshold (for example 0.75 * curSize), the table is reallocated (i.e. new internal table twice as large is created, data are copied into it, old table is forgotten).

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java

See, here is implementation from java standard API - I think you will be able to understand all necessary details though it is not C++.

[cire]

template<class T>
class hashTable{

public:
    hashTable(std::size_t size);
    ~hashTable();

    void toInsert(T* newItem);
    void toDelete(std::string name);
    T* find(int index, std::string name);
    int hashFunc(std::string name);
    void dump();
    friend ostream& operator<<(ostream& os, const T& RHS);
	
private:

    std::vector<std::list<T>> table ;   
};

template<class T>
hashTable::hashTable(std::size_t size)
    : table(size)
{
}

Save yourself some trouble.

If you've determined too many collisions are happening (via the heuristic of your choice) then make a new vector, insert the elements into that vector, and swap the new vector with the old vector (or use move assignment.)

[pfunk35]

Thanks for the advice i decided to go with a vector (of stl lists), and I just allocate after I parse that info.