//**************************************
//
// Name: An implementation of Hashing
//
// Description:The purpose of this progr
// am is to insert numbers into an hash arr
// ay dynamically.
//
//
// Inputs:Size of hash table and numbers
// to be inserted are the inputs
//
// Returns:Program prints hash table and
// number of probes for each number in orde
// r to insert it into hash table. (Average
// probe number is also printed)
//
//
//
//
//
//
//
// **************************************
//
/*
*/
#include "stdio.h"
#include "conio.h"
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
// defining booleans
#define true 1
#define false 0
// defining size of table, which is a pr
// ime number
#define Prime 11
//***************************
// Prototypes
int HashIndex(int,int);
int HashKey(int, int);
void Initialization(void);
void Presedence(void);
void InsertKey(int,int);
int ComputeNextPotentialAddress(int,int,int);
int Try(int,int,int,int,int);
void InsertAccordingTo(int, int, int, int, int);
void WasteBrent(int);
void PrintHashArray(int,int);
int CalculateRetrieve(int,int);
//***************************
// Global Variables
int hash[15]; // hash table
int pres[2][16]; // array for presedence
int n;// size of table (required for hash and key functions)
int needcheck=true; // a boolean
//***********************************
// THIS FUNCTION PRINTS THE HASH ARRAY W
// ITH NUMBER OF RETRIEVES
void PrintHashArray(int usernumarray[],int numbercounter)
{
int totalprobe=0;
int probe;
int i;
int counter=0;
for(i=0;i<n;i++)
{
if(hash[i]!=-1){
probe=CalculateRetrieve(hash[i],n);
printf("\n|%d\t%d\t|\tÎ\tprobe = %d",i,hash[i],probe);
totalprobe+=probe;
counter++;
}
else
printf("\n|%d\t^\t|\tÎ\tprobe = N/A",i);
}
printf("\nAverage Retrieve Number: %f",float (totalprobe)/counter);
printf("\n\n");
}
// THIS FUNCTION FINDS THE NUMBER OF RET
// RIEVES WITH A GIVEN NUMBER AND SIZE OF H
// ASH ARRAY
int CalculateRetrieve(int num,int n)
{
int index,next,retrieve=1;
index=HashIndex(num,n);
next=HashKey(num,n);
while(hash[index]!=num){
index=(index+next)%n;
retrieve++;
}
return retrieve;
}
// THIS FUNCTION RUNS WHEN THERE IS NO P
// OSSIBLE WAY TO INSERT NUMBER BY BRENT HA
// SHING
// IT PUTS THE NUMBER IN THE ARRAY ACCOR
// DING TO FIRST RETRIEVAL
void WasteBrent(int number)
{
int num[3],index;
num[0]=number;
num[1]=HashIndex(number,n);
num[2]=HashKey(number,n);
index=num[1];
while(hash[index]!=-1){
index=(index+num[2])%n;
}
hash[index]=num[0];
}
// THIS FUNCTION INSERTS THE NUMBER ACCO
// RDING TO;
/*
i = i pair of presedence array
j = j pair of presedence array
num = number to be inserted
index = hash index of the number
key = increment key
*/
void InsertAccordingTo(int i, int j, int num, int index, int key)
{
int m;
int newnum[3],newindex;
for(m=1;m<i;m++){
index=(index+key)%n;
}
newnum[0]=hash[index];
newnum[2]=HashKey(newnum[0],n);
hash[index]=num;
for(m=0;m<j;m++){
index=(index+newnum[2])%n;
}
hash[index]=newnum[0];
}
// IT TRIES TO INSERT NUMBER INTO HASH T
// ABLE ACCORDING TO i AND j VALUES
// IF IT CAN, IT RETURNS 1 ELSE -1
int Try(int i, int j, int num, int index, int key){
int m;
int newnum[3],newindex;
int returnval;
if(needcheck==true){
if((i==1)&&(j==1)){
newnum[0]=hash[index];
newnum[1]=HashIndex(newnum[0],n);
newnum[2]=HashKey(newnum[0],n);
newindex=(newnum[1]+newnum[2])%n;
if((hash[newindex]==-1)&&(newindex!=newnum[1]))
returnval=1;
else
returnval=0;
}
else{
for(m=1;m<i;m++){
index=(index+key)%n;
}
newnum[0]=hash[index];
newnum[1]=HashIndex(newnum[0],n);
newnum[2]=HashKey(newnum[0],n);
newindex=index;
for(m=1;m<=j;m++){
newindex=(newindex+newnum[2])%n;
}
if((hash[newindex]!=-1)||(newindex==index))
returnval=-1;
else returnval=1;
}
}
else{
returnval=-1;
}
return returnval;
}
// THIS FUNCTION RUNS IF THE NUMBER CANN
// OT BE INSERTED AT ONE PROBE
// IT CALCULATES THE NUMBER OF RETRIEVAL
// S ACCORDING TO STATIC HASHING
int ComputeNextPotentialAddress(int num, int index, int key){
int returnval=1;
int storedindex=index;
if (key==0){
returnval=-1;
}
else{
while(hash[index]>=0){
index=(index+key)%n;
if(index==storedindex)
{
printf("Table is Full");
getch();
exit(0);
}
if(hash[index]==num)
{
printf("Duplicate Record");
getch();
exit(0);
}
returnval++;
}
}
return returnval;
}
// INSERTS THE num INTO index INDEX OF H
// ASH TABLE
// <%!--"NOT NECESSARY TO WRITE THIS
// CODE BUT ..."--%>
void InsertKey(int num, int index)
{
hash[index]=num;
}
// CALCULATES THE HASH INDEX OF NUMBER
int HashIndex(int num,int prime){ // number and p prime number
int returnval;
returnval=num%prime;
return returnval;
}
// CALCULATES THE INCREMENT KEY OF NUMBE
// R
int HashKey(int num, int prime){ // number and p prime number
int returnval;
returnval=((num/prime)%prime);
return returnval;
}
// CALCULATE PRESEDENCE ARRAY FOR BRENTS
// HASHING
// 1-1, 1-2, 2-1, 1-3, 2-2, 3-1 .....
void Presedence(void){
int arrindex=0;
for(int k=2; k<7; k++)
for(int l=1; l<k; l++)
{
pres[0][arrindex]=l;
pres[1][arrindex]=k-l;
arrindex++;
}
}
// MAKE ARRAYS -1, (-1 IS A CONTROL NUMB
// ER)
void Initialization(int arr[]){
int count;
for(count=0;count<15;count++){
hash[count]=-1;
arr[count]=-1;
}
}
// MAIN FUNCTION
void main(void){
int ok=true, usernum[3]; // usernum[0]=number, usernum[1]=hashindex usernum[2]=key
int s; // first probe
int i,j; // usual variables
int isfound,totalProbe=0,opdone=false,count=0;
char numstr[5];
int numbers[15];
textmode(C80);
textbackground(3);
textcolor(0);
clrscr();
Initialization(numbers);
Presedence();
n=Prime;
isfound=0;
printf("Enter size of hash table : ");
scanf("%d",&n);
while(ok){
printf("Enter number : ");
scanf("%s",numstr);
if(isalpha(numstr[0])){ // exit command
ok=0;
}
else{ // brent operation starts
usernum[0]=atoi(numstr);// number
usernum[1]=HashIndex(usernum[0],n); // hash index
usernum[2]=HashKey(usernum[0],n); // hash key
numbers[count]=usernum[0];
printf("Hash Index = %d, Hash Increment Key= %d\n",usernum[1],usernum[2]);
count++;
if(hash[usernum[1]]<0){ // if home address is empty
InsertKey(usernum[0],usernum[1]); // insert number into hash table
}
else{ // if home address is not empty
if(hash[usernum[1]]==usernum[0]){
printf("Duplicate number! Press Any key to exit");
getch();
exit(0);
}
s=ComputeNextPotentialAddress(usernum[0],usernum[1],usernum[2]);
if (s<0){
printf("Increment key is zero, infinite loop! Press any key to exit");
getch();
exit(0);
}
else{
i=0;
needcheck=true;
opdone=false;
for(i=0;i<15;i++){
if(Try(pres[0][i],pres[1][i],usernum[0],usernum[1],usernum[2])==1){
needcheck=false;
if((needcheck==false)&&(opdone==false)){
if ((pres[0][i]+pres[1][i])<s){
InsertAccordingTo(pres[0][i],pres[1][i],usernum[0],usernum[1],usernum[2]);
}
if((needcheck==true)&&(opdone==false))
{
WasteBrent(usernum[0]);
}
opdone=true;
}
}
}
}
}
PrintHashArray(numbers,count);
}
}
getch();