Click here to Skip to main content
15,393,377 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
collision in hashing occur in this code I did, how can I resolve it in the code? I only fail to found NG CHEA YEAT's name.

What I have tried:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MNAME 80
#define MDIR 30
#define MBUFF 2916
#define MHASH 521

struct List{
    int studID;
    char name[MNAME];
};

int comparator(const void* p, const void* q){
    return strcmp(((struct List*)p)->name,((struct List*)q)->name);
}

int readData(struct List dir[]);
int hashfunc(char *name);

void hash(struct List dir[], int ndir, int hashtable[]);

int search(char *key, struct List s[], int hashtable[]);

int main(void){
    
    int ndir, result, hashtable[MHASH];

    char query[MNAME];

	struct List s[27];
	int count, i, j;
	char temp[27];
	
	FILE *fptr; //Associate the file pointer to the rec file
	fptr = fopen("rec.txt", "r");
	
    //Check of data file could be opened successfully
  if (fptr == NULL){
    printf("Error opening input file");
    return 1;
  }
  
   for(count = 0; count < 27; count++){
       fscanf(fptr,"%d", &s[count].studID);
       fgets(s[count].name,40,fptr);
   }
	
	//sort
    qsort(s,27,sizeof(struct List),comparator);

    printf("Sorted Names\n");
	for(i=0;i<27;i++){
		printf("%d%s", i+1, s[i].name);
	}

  fclose(fptr);
	
  ndir=readData(s);
  hash(s,ndir,hashtable);
 
  puts("\nName to search>>");
  fgets(query,MNAME-1,stdin);
  query[strlen(query)-1]='\0';

  result=search(query,s,hashtable);  
  if(result==-1) 
    printf("Not Found");
  else 
    printf("%s's id is %d\n",
            s[result].name, s[result].studID);
		
return 0;
}

int readData(struct List dir[]){
  FILE *fdir=fopen("rec.txt","r");
  char buff[MBUFF];
  int i=0;
  
    while(i<MDIR && fgets(buff,MBUFF-1,fdir)){
    dir[i].studID=atol(strtok(buff,":"));
    strcpy(dir[i].name,strtok(NULL,"\n"));
    i++;
 }
 return(i);
}

int hashfunc(char *name){
  long sum=0;
  int k=0;
  while(name[k]){
    sum+=name[k];
    k++;
  }
  return( (int) (sum % MHASH) );
}

void hash(struct List dir[], int ndir, int hashtable[]){
  int k;
  int index;
  for(k=0;k<ndir;k++){
    index = hashfunc(dir[k].name);
    hashtable[index]=k;
  }
}

int search(char *key, struct List dir[], int hashtable[]){
  int index=hashfunc(key);
  int k=hashtable[index];

  if(strcmp(key,dir[k].name)==0)
    return(k);
  else 
    return(-1);
}


Here is the text file:
1171203258:HOSSAIN, MARUF
1181202660:KUHAN RAJ A/L TAMIL CHEL WAM
1181203465:PONG KAI SUN
1191102443:FAIZA OSAMA ABDALLA HASHIM
1201302289:LEE JIA WEI
1201302368:SHEIKH, AHNAF AZMAIN
1201100584:HI CHIA LING
1201101509:NG CHEA YEAT
1191103201:PHUAH CHEE HAOU
1201100879:MOSTAFA ARABY MADBOULY AHMED
1191103215:TONG JUN YANG
1191103119:ANG QIZHENG
1171302286:DARWIN KUMAR A/L MUNIAN
1181101192:HAIZUN NAJWA BINTI MOHD RIFIN
1201100926:NG XUE NIE
1191302417:ALMARHOON, ALI HUSSAIN A
1201100225:HEMAN RAO A/L SUBRAMANIAM
1181100823:LIM ZHEN BANG
1161202587:SOHEIL PRAKASAN SUPPAN
1201100603:AVINASH MURALI
1181101858:CHEAH KOK YEW
1191103071:GAN WEI TONG
1201100301:KEVIN THAM ZHENG YIT
1201100648:LIM CHER AIK
1201302222:SHIVAA RUTRAN A/L NAGATHEESAN
1201100779:TAN WEI XIANG
1191100919:WONG HONG WEI
Posted
Updated 13-Apr-22 1:56am

Each hash item should be a node of a linked list, instead of plain integer, e.g.
C
struct HashItem
{
  int id;
  char * name;
  HashItem * next;
};
See, for instance Hash table - Wikipedia - Collision resolution[^].

If you can, use C++, the standard library containers would make your life easier.
   
v2
Comments
Rick York 13-Apr-22 12:30pm
   
I prefer a more generic hash table organization which for this one means id is replaced with a pointer to this person's "List" structure. The members of the structure would be :
typedef struct _HashItem
{
   char * key;
   void * pData;
   struct _HashItem * pNext;
};
hopefully that resembles C syntax. Anyway, it's essentially the same as what you have but it can work with practically any data.
CPallini 14-Apr-22 1:59am
   
I prefer a std::list in a std::unordered_map ;-)
Or, better, a std::unordered_multimap.
The hash is to weak, so you need some better hashing algorithms, take a lot at these proven hash functions.

At least you will see that your function is way to simple for that problem.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900