Hash Table

A. First Edition
This is the first edition of my hash-table class with template. I want to make it as generic as possible. However,
it is not so easy as for hash table user needs some specific functions which has to be passed by template.
B.The problem
How to implement a hash table with data type stored inside independently? Or in other words, can you make a 
generic hash table? My conflict resolution is separate chaining.
C.The idea of program
 
This class is for comp442 compiler design and our symbol table needs a hash table. I force user to pass in
his method of initialization, remove, assignment, comparison method all by a template parameter which is a class:
"hashFun".
D.The major functions
E.Further improvement
The most important part of hash-table is hash function. You can see my hash table is only about 35% full of 
total space and there has been quite a few conflict. This simply means that my hash function is not good enough.
F.File listing
1. hash.h
2. main.cpp (main)

 

file name: hash.h

const int SHIFT=8;
const int TableLength=211;

struct Node
{
	char* data;
	Node* next;
};




class HashFun
{
public:
	static int fun(char* in);
	static Node* empty;
	static Node* conflictFun(Node* oldNode, Node* newNode);
	static Node* remove(Node* ptr);
	static bool eq(Node* l, Node* r);
	static void assign(Node*& target, Node* source);

};


template<class inElem, class outElem, class hashFun, int tableLength>
class Hash
{
protected:
	outElem table[tableLength];
	int count;
public:
	Hash();
	bool search(inElem& in, outElem& out);
	outElem  insert(inElem& in, outElem& out);
	bool purge(inElem& in);
	void print();
	int loadFactor(){ return count*100/tableLength;}
};


template<class inElem, class outElem, class hashFun, int tableLength>
Hash<inElem, outElem, hashFun, tableLength>::Hash()
{
	count=0;
	for (int i=0; i<tableLength; i++)
	{
		hashFun::assign(table[i], hashFun::empty);//even pointer can be 0
	}
}

template<class inElem, class outElem, class hashFun, int tableLength>
bool Hash<inElem, outElem, hashFun, tableLength>
	::search(inElem& in, outElem& out)
{
	int index=hashFun::fun(in);
	if (!hashFun::eq(table[index], hashFun::empty))
	{
		//outElem must overload "=" operator!!
		hashFun::assign(out, table[index]);
		return true;
	}
	return false;
}

template<class inElem, class outElem, class hashFun, int tableLength>
outElem Hash<inElem, outElem, hashFun, tableLength>
	::insert(inElem& in, outElem& out)
{
	int index=hashFun::fun(in);
	outElem temp;
	if (hashFun::eq(table[index], hashFun::empty))
	{
		hashFun::assign(table[index], out);
		count++;
		return hashFun::empty;
	}
	else
	{
		hashFun::assign(temp, table[index]);
		hashFun::assign(table[index], hashFun::conflictFun(table[index], out));	
		return temp;
	}
}


template<class inElem, class outElem, class hashFun, int tableLength>
bool Hash<inElem, outElem, hashFun, tableLength>
	::purge(inElem& in)
{
	int index=hashFun::fun(in);
	
	if (!(hashFun::eq(table[index], hashFun::empty)))
	{
		hashFun::remove(table[index]);
		hashFun::assign(table[index], hashFun::empty);
		return true;
	}
	else
	{
		return false;
	}
}

template<class inElem, class outElem, class hashFun, int tableLength>
void Hash<inElem, outElem, hashFun, tableLength>::print()
{
	for (int i=0; i<tableLength; i++)
	{
		if (!(hashFun::eq(table[i], hashFun::empty)))
		{
			cout<<"No. "<<i<<" is: "<<table[i]<<endl;
		}
	}
}


Node* HashFun::empty=NULL;

int HashFun::fun(char* in)
{
	char* ptr=in;
	int result=0;
	while (*ptr!='\0')
	{
		result = ((result<<SHIFT) + *ptr)%TableLength;
		//result+= *ptr;
		ptr++;
	}
	return result;
}

Node* HashFun::conflictFun(Node* oldNode, Node* newNode)
{
	newNode->next=oldNode;
	return newNode;
}

Node* HashFun::remove(Node* ptr)
{
	Node* temp;
	while (ptr!=NULL)
	{
		temp=ptr;
		ptr=ptr->next;
		delete[]temp->data;
		delete temp;
	}
	return NULL;
}

bool HashFun::eq(Node* l, Node* r)
{
	return l==r;//maybe wrong!!!
}

void HashFun::assign(Node*& target, Node* source)
{
	target=source;
}




file name: main.cpp (main)

#include <iostream>
#include <fstream>
#include "hash.h"

using namespace std;

char* myStr[5]={"first", "second", "third", "fourth", "fifth"};

ostream& operator<<(ostream& out, Node*ptr);

Node* createNode(char* str);

int main()
{
	Hash<char*, Node*, HashFun, TableLength> H;
	char buffer[20];
	char* pStr=buffer;
	Node* ptr;
	ifstream f("c:\\myinputFile.txt");
	while (!f.eof())
	{
		f>>buffer;
		ptr=createNode(buffer);
		if ((ptr=H.insert(pStr, ptr))!=NULL)
		{
			cout<<" conflict for: "<<buffer<<"  and "<<ptr->data<<endl;
		}
	}
	H.print();
	//cout<<"now remove "<<myStr[3]<<endl;
	//H.purge(myStr[3]);
	//H.print();
	cout<<"load factor is "<<H.loadFactor()<<"%"<<endl;

	return 0;
}


Node* createNode(char* str)
{
	Node* ptr=new Node;
	ptr->data=new  char[strlen(str)+1];
	strcpy(ptr->data, str);
	ptr->next=NULL;
	return ptr;
}


ostream& operator<<(ostream& out, Node* ptr)
{
	Node* temp=ptr;
	while (temp!=NULL)
	{
		out<<temp->data<<",";
		temp=temp->next;
	}
	return out;
}

 







The input is something like following:

a A the1 following templatef iss provided for use with the rational unified process. text enclosed in square brackets and displayed in blue italics style=infoBlue) isn't included to provide guidance to the author and should be deleted before publishing the document. a paragraph entered following this style will automatically be set to normal

this template is directly inspired by the templates provided in the Rational Unified Process, and are all available for free on the Rational Software web site. All credit go to Rational Software, except for the edition that we made, for which Rational Software is not responsible for


ialog, automatic fields may be updated throughout the document by selecting Edit>Select All (or Ctrl-A) and pressing F9, or simply

between displaying the field names and the

A paragraph entered following this style a

 
Here is the result:
 
 conflict for: rational  and the
 conflict for: in  and in
 conflict for: guidance  and provide
 conflict for: to  and to
 conflict for: the  and rational
 conflict for: and  and and
 conflict for: publishing  and brackets
 conflict for: the  and the
 conflict for: a  and a
 conflict for: paragraph  and for
 conflict for: following  and following
 conflict for: style  and unified
 conflict for: be  and be
 conflict for: to  and to
 conflict for: this  and this
 conflict for: by  and included
 conflict for: the  and the
 conflict for: provided  and provided
 conflict for: in  and in
 conflict for: the  and the
 conflict for: Rational  and set
 conflict for: Process,  and deleted
 conflict for: and  and and
 conflict for: available  and style=infoBlue)
 conflict for: for  and paragraph
 conflict for: free  and following
 conflict for: on  and publishing
 conflict for: the  and the
 conflict for: Rational  and Rational
 conflict for: All  and before
 conflict for: to  and to
 conflict for: Rational  and Rational
 conflict for: except  and templates
 conflict for: for  and for
 conflict for: the  and the
 conflict for: we  and and
 conflict for: for  and for
 conflict for: which  and Rational
 conflict for: Rational  and which
 conflict for: Software  and Software
 conflict for: is  and is
 conflict for: for  and for
 conflict for: ialog,  and guidance
 conflict for: be  and be
 conflict for: updated  and by
 conflict for: the  and the
 conflict for: document  and may
 conflict for: by  and updated
 conflict for: All  and All
 conflict for: and  and we
 conflict for: the  and the
 conflict for: field  and Software,
 conflict for: names  and document
 conflict for: and  and and
 conflict for: the  and the
 conflict for: A  and A
 conflict for: paragraph  and for
 conflict for: entered  and entered
 conflict for: following  and free
 conflict for: this  and this
 conflict for: style  and style
 conflict for: a  and a
No. 0 is: document.,
No. 4 is: will,
No. 7 is: the1,
No. 8 is: field,Software,,
No. 9 is: following,free,following,following,
No. 13 is: edition,
No. 14 is: web,
No. 18 is: provided,provided,
No. 19 is: credit,
No. 21 is: (or,
No. 26 is: paragraph,for,for,for,for,paragraph,for,
No. 29 is: should,
No. 31 is: ialog,,guidance,provide,
No. 34 is: Unified,
No. 35 is: F9,,
No. 41 is: on,publishing,brackets,
No. 42 is: this,this,this,
No. 45 is: or,
No. 46 is: isn't,
No. 49 is: pressing,
No. 53 is: fields,
No. 56 is: to,to,to,to,
No. 64 is: enclosed,
No. 65 is: A,A,
No. 69 is: between,
No. 71 is: automatic,
No. 74 is: names,document,may,
No. 76 is: All,All,before,
No. 77 is: inspired,
No. 80 is: be,be,be,
No. 81 is: blue,
No. 82 is: site.,
No. 84 is: made,,
No. 97 is: a,a,a,
No. 98 is: italics,
No. 99 is: all,
No. 100 is: by,updated,by,included,
No. 103 is: Edit>Select,
No. 104 is: go,
No. 105 is: that,
No. 108 is: throughout,
No. 109 is: Process,,deleted,
No. 114 is: responsible,
No. 119 is: available,style=infoBlue),
No. 122 is: templatef,
No. 127 is: entered,entered,
No. 129 is: text,
No. 135 is: except,templates,
No. 140 is: displaying,
No. 146 is: process.,
No. 149 is: with,
No. 151 is: are,
No. 152 is: style,style,unified,
No. 156 is: directly,
No. 158 is: simply,
No. 161 is: Rational,which,Rational,Rational,Rational,set,
No. 163 is: iss,
No. 168 is: Software,Software,
No. 169 is: author,
No. 179 is: automatically,
No. 180 is: Ctrl-A),
No. 181 is: and,and,we,and,and,and,
No. 184 is: use,
No. 187 is: square,
No. 188 is: template,
No. 190 is: selecting,
No. 192 is: not,
No. 193 is: in,in,in,
No. 196 is: the,the,the,the,the,the,the,the,the,rational,the,
No. 198 is: is,is,
No. 200 is: displayed,
No. 206 is: normal,
load factor is 34%
Press any key to continue
 

 





                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)