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.
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.
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".
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