Collision

In practical application it is impossible to get perfect hashing at all times. i.e) Collision will occur all time.

Assuming a class of 103 members, Each students has their Roll number in the range from 100001 to 100103. Now you the C Programmer with little knowledge in data structure will plan to collects all the students details using array from array[1] to array[103]. Unfortunately collision will occur between student with Roll Number 100001 and Roll Number 100101 because Roll Number 100101 seeks for the place of array[1] which is already occupied by the Roll Number 100001. Thus Collision algorithm will find some remedy for this problem by checking the next nearest free space to store the student details of Roll Number 100103.

Methods - Collision

• Open Addressing Collision
• Chaining Collision

Advantages - Collision

• Memory spaces are efficienty utilized.
• In best case, the running time for searching an element in an array using linear probing is 0(1)

Disadvantages - Collision

• Although, the Collision algorithm provides good memory caching through good locality of reference, the drawback of this collision algorithm is that it results in clustering when large amount of input data leads to collision.
• In worst case, the running time for searching an element in an array using linear probing is 0 (n). Where n is the number of elements in an array.

C program - Collision

Here is the C program to demonstrate Collision.

#include <stdio.h>
int main()
{
int arry[100], arry1[100], n, result = 0, i, j, count = 0;
printf("Enter the size of an array : ");
scanf("%d",&n);
printf("\nEnter %d elements : \n",n);
for(i=0; i < 10; i++)
arry1[i] = -1;
for(i=0; i < n; i++)
{
scanf("%d",&arry[i]);
}
for(i=0; i < n; i++)
{
result = arry[i] % 10;
if(arry1[result] == -1)
{
arry1[result] = arry[i];
printf("\nlocation = arry1[%d], value = %d ",result, arry1[result]);
}
else
{
j = result + 1;
while(1)
{
if(arry1[j] == -1)
{
arry1[j] = arry[i];
printf("\nlocation = arry1[%d], value = %d ",j, arry1[j]);
break;
}
if(j > 9)
j = 0;
if(count == 10)
break;
count++;
j++;
}
}
result = 0;
}
return 0;
}

Enter the size of an array : 5
Enter 5 elements : 
101 103 104 105 201
location = arry[1], value = 101
location = arry[3], value = 103
location = arry[4], value = 104
location = arry[5], value = 105
location = arry[2], value = 201

Report Us

We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.

Report

Error Line Corrected Line Send