PROGRAM – 12
12. Given a File of N employee records with a set K of Keys (4-digit) which
uniquely determine the records in file F. Assume that file F is maintained in
memory by a Hash Table (HT) of m memory locations with L as the set of
memory addresses (2-digit) of locations in HT. Let the keys in K and
addresses in L are Integers.
Develop a Program in C that uses Hash function H: K →L as H(K)=K mod m
(remainder method), and implement hashing technique to map a given key K
to the address space L. Resolve the collision (if any) using linear probing.
#include<stdio.h>
#include<stdlib.h>
int key[20], n, m;
int * ht, index;
int count = 0;
void insert(int key) {
index = key % m;
while (ht[index] != -1) {
index = (index + 1) % m;
}
ht[index] = key;
count++;
}
void display()
{
int i;
if (count == 0) {
printf("\nHash Table is empty");
return;
}
printf("\nHash Table contents are:\n ");
for (i = 0; i < m; i++)
printf("\n T[%d] --> %d ", i, ht[i]);
}
void main() {
int i;
printf("\nEnter the number of employee records (N) :");
scanf("%d", & n);
printf("\nEnter the two digit memory locations (m) for hash table:");
scanf("%d", & m);
ht = (int * ) malloc(m * sizeof(int));
for (i = 0; i < m; i++)
ht[i] = -1;
printf("\nEnter the four digit key values (K) for N Employee Records:\n ");
for (i = 0; i < n; i++)
scanf("%d", & key[i]);
for (i = 0; i < n; i++) {
if (count == m) {
printf("\n~~~Hash table is full. Cannot insert the record %d key~~~", i + 1);
break;
}
insert(key[i]);
}//Displaying Keys inserted into hash table
display();
}
OUTPUT
Enter the number of employee records (N) :10
Enter the two digit memory locations (m) for hash table:15
Enter the four digit key values (K) for N Employee Records:
4020
4560
9908
6785
0423
7890
6547
3342
9043
6754
Hash Table contents are:
T[0] --> 4020
T[1] --> 4560
T[2] --> 7890
T[3] --> 423
T[4] --> 6754
T[5] --> 6785
T[6] --> -1
T[7] --> 6547
T[8] --> 9908
T[9] --> -1
T[10] --> -1
T[11] --> -1
T[12] --> 3342
T[13] --> 9043
T[14] --> -1
Calculation:
Given
Number of employee records N = 10
Hash table size / memory locations m = 15
→ Table indices: 0 to 14
Keys (4-digit):
4020, 4560, 9908, 6785, 0423,
7890, 6547, 3342, 9043, 6754
Hash Function Used
h(K) = K mod 15
Collision resolution: Linear Probing
(If a slot is occupied, move to the next index)
Step-by-Step Insertion
Key (K) K mod 15 Action Final Index
4020 4020 % 15 = 0 Empty T[0] = 4020
4560 4560 % 15 = 0 Collision → T[1] empty T[1] = 4560
9908 9908 % 15 = 8 Empty T[8] = 9908
6785 6785 % 15 = 5 Empty T[5] = 6785
0423 423 % 15 = 3 Empty T[3] = 423
7890 7890 % 15 = 0 Collision at 0,1 → T[2] empty T[2] = 7890
Key (K) K mod 15 Action Final Index
6547 6547 % 15 = 7 Empty T[7] = 6547
3342 3342 % 15 = 12 Empty T[12] = 3342
9043 9043 % 15 = 13 Empty T[13] = 9043
6754 6754 % 15 = 4 Empty T[4] = 6754
Final Hash Table
T[0] --> 4020
T[1] --> 4560
T[2] --> 7890
T[3] --> 423
T[4] --> 6754
T[5] --> 6785
T[6] --> -1
T[7] --> 6547
T[8] --> 9908
T[9] --> -1
T[10] --> -1
T[11] --> -1
T[12] --> 3342
T[13] --> 9043
T[14] --> -1
Hash function: K mod m
Collision handling: Linear Probing
Leading zero in 0423 does not affect calculation
Empty slots marked as -1