Hashing With Chaining - BunksAllowed

BunksAllowed is an effort to facilitate Self Learning process through the provision of quality tutorials.

Community

demo-image

Hashing With Chaining

Share This

This method maintains a chain of elements that have the same hash address. We can take the hash table as an array of pointers. The size of the hash table can be the number of records. Here each pointer will point to one linked list and the elements which have the same hash address will be maintained in the linked list. We can maintain the linked list in sorted order and each element of the linked list will contain the whole record with a key.

  • For inserting one element, first, we have to get the hash value through the hash function which will map in the hash table, then that element will be inserted in the linked list which is shown in the following Figure as an example.

hash_chain

  • Searching for a key is also the same, first, we will get the hash key value in a hash table through the hash function, then we will search for the element in the corresponding linked list.
  • Deletion of a key contains the first search operation then the same as the delete operation in the linked list.

The main advantage of this hashing is saving memory space and perfect collision resolution. Here hash table contains only pointers that point to the linked list, containing records. So there is no wastage of memory space because of an empty hash table and the hash table size can be taken as a number of records. Hash table space is also minimized because records are stored in the linked list. The elements which have the same hash address will be in the same linked list. So we should use a good hash function that distributes elements on different hash addresses. Basically linked lists will be small, so searching will be fast.

The main disadvantage is also a waste of memory space. In cases where records are very small or contain only a key then the link part for every element in the linked list and pointer space in the hash table will be a waste of memory space.

Source code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <stdio.h>
#include <stdlib.h>
#define MAX 11
struct Record
{
int data;
struct Record *link;
};
void insert(struct Record *hash_table[],int);
int search_element(int key, struct Record *hash_table[]);
void remove_record(int key, struct Record *hash_table[]);
void show(struct Record *hash_table[]);
int hash_function(int key);
int main()
{
struct Record *hash_table[MAX];
int count, key, option,value;
for(count = 0; count <= MAX - 1; count++)
{
hash_table[count] = NULL;
}
while(1)
{
printf("1. Insert a Record in Hash Table\n");
printf("2. Search for a Record\n");
printf("3. Delete a Record\n");
printf("4. Show Hash Table\n");
printf("5. Quit\n");
printf("Enter your option\n");
scanf("%d",&option);
switch(option)
{
case 1:
printf("\nEnter the number:");
scanf("%d", &value);
insert(hash_table,value);
break;
case 2:
printf("Enter the element to search:\t");
scanf("%d", &key);
count = search_element(key, hash_table);
if(count == -1)
{
printf("Element Not Found\n");
}
else
{
printf("Element Found in Chain:\t%d\n", count);
}
break;
case 3:
printf("Enter the element to delete:\t");
scanf("%d", &key);
remove_record(key, hash_table);
break;
case 4:
show(hash_table);
break;
case 5:
return 0;
}
}
return 0;
}
void insert(struct Record *hash_table[],int value)
{
int key, h;
struct Record *temp;
key = value;
if(search_element(key, hash_table) != -1)
{
printf("Duplicate Key\n");
return;
}
h = hash_function(key);
temp = malloc(sizeof(struct Record));
temp->data = value;
temp->link = hash_table[h];
hash_table[h] = temp;
}
void show(struct Record *hash_table[])
{
int count;
struct Record *ptr;
for(count = 0; count < MAX; count++)
{
printf("\n[%3d]", count);
if(hash_table[count] != NULL)
{
ptr = hash_table[count];
while(ptr != NULL)
{
printf("%d-->", ptr->data);
ptr=ptr->link;
}
}
}
printf("\n");
}
int search_element(int key, struct Record *hash_table[])
{
int h;
struct Record *ptr;
h = hash_function(key);
ptr = hash_table[h];
while(ptr != NULL)
{
if(ptr->data == key)
{
return h;
}
ptr = ptr->link;
}
return -1;
}
void remove_record(int key, struct Record *hash_table[])
{
int h;
struct Record *temp, *ptr;
h = hash_function(key);
if(hash_table[h]==NULL)
{
printf("Key %d Not Found\n", key);
return;
}
if(hash_table[h]->data == key)
{
temp = hash_table[h];
hash_table[h] = hash_table[h]->link;
free(temp);
return;
}
ptr = hash_table[h];
while(ptr->link != NULL)
{
if(ptr->link->data == key)
{
temp = ptr->link;
ptr->link = temp->link;
free(temp);
return;
}
ptr = ptr->link;
}
printf("Key %d Not Found\n", key);
}
int hash_function(int key)
{
return (key % MAX);
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Happy Exploring!

Comment Using!!

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.