-2

I am working on a universal hash function h(k)=((a*k+b)mod p)mod m, by picking a and b randomly using boost library so that a perfect hash function may achieve. I am using chaining technique to detect number of collisions using array of singly linked lists. Loop will keep on going as it will not get count_collisions=0;. Here is the piece of code: 

void hashFunction() { long long int m=0; long long int val=0; cout<<"Enter table size: "; cin>>m; m=m*m; long long int *p=generateDistinctRandomKeys(m); long long int pno=generateSingleRandomNo(); // prime No 'P' while((pno/1!=pno) && (pno/pno!=1) && (pno<m)) { if((pno/1==pno) && (pno/pno==1) && (pno>m)) break; else pno=generateSingleRandomNo(); } //intializing linked list ! int cc=0; startt_: LinkedList **l=new LinkedList*[m]; for(int i=0;i<m;i++) { l[i]=new LinkedList; //l[i]=NULL; } cc++; int count_collisions=0; long long int a=generateSingleRandomNo(1,pno-1); long long int b=generateSingleRandomNo(0,pno-1); for(int j=0;j<m;j++) { //applying hash function !!! val=(((a*p[j])+b)%(pno))%(m); if(val<0) val=val*(-1); bool f=l[val]->insert(p[j]); //cout<<val<<endl; //cc=j; } for(int s=0;s<m;s++) { //l[s]->display(); count_collisions=count_collisions+l[s]->countCollisions(); } if(count_collisions==0) { cout<<"Perfect function achieved after "<<cc<<" Iterations!"<<endl; cout<<"Values of a and b are: "<<a<<" and "<<b<<endl; exit(0); } else {/* if(cc==5) { cout<<"STOP!!!!!!!!!!!!!"<<endl; exit(0); }*/ //j=0; for(int n=0;n<m;n++) { l[n]->~LinkedList(); } delete [] l; l=0; goto startt_ ; } /*cout<<"Collisions are:"<<count_collisions<<endl;*/

}

Improve this question
6
  • 1
    You might want to use or look inside gperf Commented Sep 7, 2014 at 16:40
  • 1
    You might also want to think twice about the tradeoff between making a perfect hash function and tolerating the cost of some collisions. If the number of actual collisions is sufficiently small, the cost of dealing with them will be probably lower than the cost of having a slower hash function (which you need to compute for every access) Commented Sep 7, 2014 at 16:48
  • Your missing likely useful function definitions and what is the purpose of (pno/1 != pno) && (pno/pno != 1)? Commented Sep 7, 2014 at 16:48
  • @uesp it is requirement to pick 'p' as a prime number greater then 'm' (table size) Commented Sep 7, 2014 at 16:57
  • @GiulioFranco and i have tried a lot and debug a lot to find perfect function. I know i am doing wrong somewhere but not getting it properly . Kindly help me out.Thanks. Commented Sep 7, 2014 at 17:01

1 Answer 1

Reset to default
2

Perect hash functions are usually constructed, not "discovered by chance".

Only few things lend themselves for the "Monte Carlo" approach (which means, rolling the dice often enough to arrive at a good approximation).

The suggestion to use gperf is excellent, see e.g.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

appreciate your answer. I have a little short time to submit my work. can you please give me some code or some solution to my code so that it can may work. because i have adopted this way it will very difficult for a beginner to re-write it from scratch. I hope you understand. Kind regards !

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.