C Program To Implement Dictionary Using Hashing Functions

C Program To Implement Dictionary Using Hashing Functions
C Program To Implement Dictionary Using Hashing Functions Pdf
C Program To Implement Dictionary Using Hashing Functions Based

#include<iostream>
#include<string.h>
//////////////////////////////////////////////////////////////
////
// Name : Vivek S. Sharma //
// Title : Hashing with probing//
////
////
//////////////////////////////////////////////////////////////
using namespace std;
class HashFunction
{
typedef struct hash
{
long key;
char name[10];
}hash;
hash h[10];
public:
HashFunction();
void insert();
void display();
int find(long);
void Delete(long);
};
HashFunction::HashFunction()
{
int i;
for(i=0;i<10;i++)
{
h[i].key=-1;
strcpy(h[i].name,'NULL');
}
}
void HashFunction::Delete(long k)
{
int index=find(k);
if(index-1)
{
cout<<'ntKey Not Found';
}
else
{
h[index].key=-1;
strcpy(h[index].name,'NULL');
cout<<'ntKey is Deleted';
}
}
int HashFunction::find(long k)
{
int i;
for(i=0;i<10;i++)
{
if(h[i].keyk)
{
cout<<'nt'<<h[i].key<<' is Found at '<<i<<' Location With Name '<<h[i].name;
return i;
}
}
if(i10)
{
return -1;
}
}
void HashFunction::display()
{
int i;
cout<<'nttKeyttName';
for(i=0;i<10;i++)
{
cout<<'nth['<<i<<']t'<<h[i].key<<'tt'<<h[i].name;
}
}
void HashFunction::insert()
{
char ans,n[10],ntemp[10];
long k,temp;
int v,hi,cnt=0,flag=0,i;
do
{
if(cnt>=10)
{
cout<<'ntHash Table is FULL';
break;
}
cout<<'ntEnter a Telephone No: ';
cin>>k;
cout<<'ntEnter a Client Name: ';
cin>>n;
hi=k%10;// hash function
if(h[hi].key-1)
{
h[hi].key=k;
strcpy(h[hi].name,n);
}
else
{
if(h[hi].key%10!=hi)
{
temp=h[hi].key;
strcpy(ntemp,h[hi].name);
h[hi].key=k;
strcpy(h[hi].name,n);
for(i=hi+1;i<10;i++)
{
if(h[i].key-1)
{
h[i].key=temp;
strcpy(h[i].name,ntemp);
flag=1;
break;
}
}
for(i=0;i<hi && flag0;i++)
{
if(h[i].key-1)
{
h[i].key=temp;
strcpy(h[i].name,ntemp);
break;
}
}
}
else
{
for(i=hi+1;i<10;i++)
{
if(h[i].key-1)
{
h[i].key=k;
strcpy(h[i].name,n);
flag=1;
break;
}
}
for(i=0;i<hi && flag0;i++)
{
if(h[i].key-1)
{
h[i].key=k;
strcpy(h[i].name,n);
break;
}
}
}
}
flag=0;
cnt++;
cout<<'nt..... Do You Want to Insert More Key: y/n';
cin>>ans;
}while(ans'y'||ans'Y');
}
int main()
{
long k;
int ch,index;
char ans;
HashFunction obj;
do
{
cout<<'nt***** Telephone (ADT) *****';
cout<<'nt1. Insertnt2. Displaynt3. Findnt4. Deletent5. Exit';
cout<<'nt..... Enter Your Choice: ';
cin>>ch;
switch(ch)
{
case 1: obj.insert();
break;
case 2:obj.display();
break;
case 3:cout<<'ntEnter a Key Which You Want to Search: ';
cin>>k;
index=obj.find(k);
if(index-1)
{
cout<<'ntKey Not Found';
}
break;
case 4:cout<<'ntEnter a Key Which You Want to Delete: ';
cin>>k;
obj.Delete(k);
break;
case 5:
break;
}
cout<<'nt..... Do You Want to Continue in Main Menu:y/n ';
cin>>ans;
}while(ans'y'||ans'Y');
}

Hashing is an efficient method to store and retrieve elements.

It’s exactly same as index page of a book. In index page, every topic is associated with a page number. If we want to look some topic, we can directly get the page number from the index.

Likewise, in hashing every value will be associated with a key. Using this key, we can point out the element directly.

Let’s discuss hashing with modulo method.

We will implement the Dictionary ADT using a hash table data structure. All of the operations should be performed in O(1) average case (O(n) worst case) time. Conveniently, the hash table has the same operations, so we will not actually have a Dictionary class. . Implements a dictionary's functionality. Functions/definitions in this program are used in speller.c to help create a. spellchecker. Functions include load, unload, check, and size. Load runs. through a text file full of words and loads them into memory as a hash table. (dictionary). Unload frees the memory the hash table is using.

How to calculate the hash key?

Let's take hash table size as 7.

size = 7

arr[size];

Formula to calculate key is,

key = element % size

If we take modulo of number with N, the remainder will always be 0 to N - 1.

Exactly array index also starts from 0 and ends with index N -1. So we can easily store elements in array index.

Initialize the Hash Bucket

Before inserting elements into array. Let’s make array default value as -1.

-1 indicates element not present or the particular index is available to insert.

Inserting elements in the hash table

i)insert 24

ii)insert 8

iii)insert 14

Searching elements from the hash table

i)search 8

ii)search 19

Deleting an element from the hash table

Here, we are not going to remove the element.

We just mark the index as -1. It is indirectly delete the element from array.

Example

Delete: 24