Write a simple C++ program which will identify how many collisions occur for eac
ID: 3691596 • Letter: W
Question
Write a simple C++ program which will identify how many collisions occur for each of the numbers from 200 thru 600, incremented by 5, when mapping to a hash table array of 100 entries.
Do this by creating a variable and looping to force it to have all values
example: 200, 205, 210… 600.
First use 100 as the divisor and use the modulo function to do mapping. Then use 101 as the divisor with the modulo function to do the mapping.
Separately, set up an array of 100 entries, whose values will be a count of the number of times its index is created. Initialize to zero.
For example: 200 maps to index value ‘i’ = 99. Add 1 to Array[99].
Output the 101 results to see how the distribution would occur.
Explanation / Answer
Program:
#include<iostream.h>
#include<conio.h>
#define Max 100
class hash
{
private:
int arr[Max];
public:
hash();
void insert(int index,int num);
int index(int num);
void display();
}
hash::hash()
{
int i;
for(i=0;i<Max;i++){arr[i]=-1;}
}
int hash::index(int num) //hash key created
{
int index;
index=num%101; // divisor 101 with modulo function to do mapping
return index;
}
void hash::insert(int index,int num)
{
int indexmax=0,flag=0;
int i=0;
if(arr[index]==-1){arr[index]=num;} //if hash table is empty, enter number to location
else
{ while(i<Max) //to check whether hash is full
{
if(arr[i]!=-1)
indexmax++;
i++;
}
if(indexmax==Max)
{
cout<<"Hash Table full";
display();
}
for(i=index+1;i<Max;i++)
{
if(arr[i]==-1) // search for empty location
{
arr[i]=num;
flag=1;
break;
}
}
for(i=0;i<index&&flag==0;i++) //search for empty location in upper part of table
if(arr[i]==-1)
{
arr[i]=num;
flag=1;
break;
}
}
}
void hash::display() //display hash table
{
int i=0;
cout<<" Hash Table is";
for(i=0;i<Max;i++)
cout<<" "<<i<<" "<<arr[i];
}
void main()
{
int num,index,i;
int arr[100];
hash h;
clrscr();
for(i=1;i<=81;i++)
{
arr[0]=195;
arr[i]=arr[i-1]+5;
num=arr[i];
h.index(num);
h.insert(index,num);
}
h.display();
getch();
}
Output
Hash Table is
0 200
1 205
2 210
3 215
4 220
5 225
6 230
7 235
8 240
......
75 575
76 580
77 585
78 590
79 595
80 600
81 -1
82 -1
83 -1
84 -1
85 -1
86 -1
87 -1
88 -1
89 -1
90 -1
91 -1
92 -1
93 -1
94 -1
95 -1
96 -1
97 -1
98 -1
99 -1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.