CFGReader

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

    ¡¡

¡¡