Experiment No:
|
1
|
Name of the Experiment:
|
Implement
functions of dictionary using hashing
|
Aim: To
implement functions of Dictionary using Hashing
Hardware
Software Requirements:
Ø Intel
based desktop PC
Ø Minimum
of 166 MHZ or Faster processor
Ø At
least 256 MB Ram
Ø At
least 512 MB hard-disk with at least 100 MB free of disk place
Ø C
Compiler (Turbo-c) or C++ Compiler (Turbo-C++)
Description:
Hashing is the process
of mapping large amount of data item to a smaller table with the help of a
hashing function. Means we can place the dictionary entries (key, value) in the
hash table using hash function.
Hash table (also hash map)
is a Data Structure used to store & retrieve data very quickly. Insertion
of the data in the hash table is based on the key value. Every entry in the
hash table is associated with some key.
Example: Storing the
voter record in hash table voter id will work as key.
Hash function: The fixed process
to convert a key to a hash key is
known as a hash function, which
is used to put the data in the hash table, same hash function is used for
retrieve the data from the hash function is used for retrieve the data from the
hash table.
Hash function is used to implement the
hash table.
The integer returned by the hash
function is called Hash Key.
On common method for determining hash
key is the division method of hashing.
The formula that will be used is:
|
Hash key = key % number of slots in the table
|
Example:
Ø Consider that we want to place some voter’s records in the hash table
Ø The voter’s record is placed with help
of the key.
Ø Here voter id is the key.
Ø Note that, if the voter id is large
digit (ex: 7 digit number) then consider last 3 digits of the voter id as key.
No
matter what the hash function, there is the possibility that two keys could
resolve to the same hash key. This situation is known as a collision.
When this occurs, there
are two simple solutions:
PROGRAM:
#include
<stdio.h>
#include <string.h>
#include <stdlib.h>
struct hash *hashTable = NULL;
int eleCount = 0;
struct node {
int key, age;
char name[100];
struct node *next;
};
struct hash {
struct node *head;
int count;
};
struct node * createNode(int key, char *name,
int age) {
struct node *newnode;
newnode = (struct node
*)malloc(sizeof(struct node));
newnode->key = key;
newnode->age = age;
strcpy(newnode->name, name);
newnode->next = NULL;
return newnode;
}
void insertToHash(int key, char *name, int
age) {
int hashIndex = key % eleCount;
struct node *newnode = createNode(key, name, age);
/* head of list for the bucket with
index "hashIndex" */
if (!hashTable[hashIndex].head) {
hashTable[hashIndex].head =
newnode;
hashTable[hashIndex].count = 1;
return;
}
/* adding new node to the list */
newnode->next =
(hashTable[hashIndex].head);
/*
* update the head of the list and no
of
* nodes in the current bucket
*/
hashTable[hashIndex].head = newnode;
hashTable[hashIndex].count++;
return;
}
void deleteFromHash(int key) {
/* find the bucket using hash index */
int hashIndex = key % eleCount, flag =
0;
struct node *temp, *myNode;
/* get the list head from current
bucket */
myNode = hashTable[hashIndex].head;
if (!myNode) {
printf("Given data is not
present in hash Table!!\n");
return;
}
temp = myNode;
while (myNode != NULL) {
/* delete the node with given
key */
if (myNode->key == key) {
flag = 1;
if (myNode ==
hashTable[hashIndex].head)
hashTable[hashIndex].head =
myNode->next;
else
temp->next =
myNode->next;
hashTable[hashIndex].count--;
free(myNode);
break;
}
temp = myNode;
myNode = myNode->next;
}
if (flag)
printf("Data deleted
successfully from Hash Table\n");
else
printf("Given data is not
present in hash Table!!!!\n");
return;
}
void searchInHash(int key) {
int hashIndex = key % eleCount, flag =
0;
struct node *myNode;
myNode = hashTable[hashIndex].head;
if (!myNode) {
printf("Search element unavailable
in hash table\n");
return;
}
while (myNode != NULL) {
if (myNode->key == key) {
printf("VoterID :
%d\n", myNode->key);
printf("Name : %s\n", myNode->name);
printf("Age : %d\n", myNode->age);
flag = 1;
break;
}
myNode = myNode->next;
}
if (!flag)
printf("Search element
unavailable in hash table\n");
return;
}
void display() {
struct node *myNode;
int i;
for (i = 0; i < eleCount; i++) {
if (hashTable[i].count == 0)
continue;
myNode = hashTable[i].head;
if (!myNode)
continue;
printf("\nData at index %d
in Hash Table:\n", i);
printf("VoterID Name Age
\n");
printf("--------------------------------\n");
while (myNode != NULL) {
printf("%-12d", myNode->key);
printf("%-15s", myNode->name);
printf("%d\n", myNode->age);
myNode =
myNode->next;
}
}
return;
}
int main() {
int n, ch, key, age;
char name[100];
printf("Enter the number of
elements:");
scanf("%d", &n);
eleCount = n;
/* create hash table with "n"
no of buckets */
hashTable = (struct hash *)calloc(n,
sizeof (struct hash));
while (1) {
printf("\n1. Insertion\t2.
Deletion\n");
printf("3. Searching\t4.
Display\n5. Exit\n");
printf("Enter your
choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter the key value:");
scanf("%d", &key);
getchar();
printf("Enter
the name");
scanf(“%s”,
name);
printf("Age:");
scanf("%d", &age);
/*inserting new
node to hash table */
insertToHash(key, name, age);
break;
case 2:
printf("Enter the key to perform deletion:");
scanf("%d", &key);
/* delete node
with "key" from hash table */
deleteFromHash(key);
break;
case 3:
printf("Enter the key to search:");
scanf("%d", &key);
searchInHash(key);
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("U have
entered wrong option!!\n");
break;
}
}
return 0;
}
OUTPUT:
Enter
the number of elements:2
1.
Insertion 2. Deletion
3.
Searching 4. Display
5.
Exit
Enter
your choice:1
Enter
the key value:5
Name:krishna
Age:24
1.
Insertion 2. Deletion
3.
Searching 4. Display
5.
Exit
Enter
your choice:1
Enter
the key value:10
Name:prasad
Age:24
1.
Insertion 2. Deletion
3.
Searching 4. Display
5. Exit
Enter
your choice:4
Data
at index 0 in Hash Table:
VoterID Name Age
--------------------------------
10 prasad 24
Data
at index 1 in Hash Table:
VoterID Name Age
--------------------------------
5 krishna 24
|
1.
Insertion 2. Deletion
3.
Searching 4. Display
5.
Exit
Enter
your choice:3
Enter
the key to search:5
VoterID : 5
Name : krishna
Age : 24
1.
Insertion 2. Deletion
3.
Searching 4. Display
5.
Exit
Enter
your choice:1
Enter
the key value:4
Name:rajesh
Age:26
1.
Insertion 2. Deletion
3.
Searching 4. Display
5.
Exit
Enter
your choice:4
Data
at index 0 in Hash Table:
VoterID Name Age
--------------------------------
4 rajesh 26
10 prasad 24
Data
at index 1 in Hash Table:
VoterID Name Age
--------------------------------
5 krishna 24
|
1.
Insertion 2. Deletion
3.
Searching 4. Display
5.
Exit
Enter
your choice:2
Enter
the key to perform deletion:10
Data
deleted successfully from Hash Table
1.
Insertion 2. Deletion
3.
Searching 4. Display
5.
Exit
Enter
your choice:4
Data
at index 0 in Hash Table:
VoterID Name Age
--------------------------------
4 rajesh 26
Data
at index 1 in Hash Table:
VoterID Name Age
--------------------------------
5 krishna 24
1.
Insertion 2. Deletion
3.
Searching 4. Display
5.
Exit
Enter
your choice:5
|
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment