Is perfect hash function achieveable?

Question

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;*/

}

You might want to use or look inside [gperf](https://www.gnu.org/software/gperf/) — Basile Starynkevitch, Sep 07 '14 at 16:40
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) — Giulio Franco, Sep 07 '14 at 16:48
Your missing likely useful function definitions and what is the purpose of `(pno/1 != pno) && (pno/pno != 1)`? — uesp, Sep 07 '14 at 16:48
@uesp it is requirement to pick 'p' as a prime number greater then 'm' (table size) — rayan, Sep 07 '14 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. — rayan, Sep 07 '14 at 17:01
@rayan The issue is that both expressions in `(pno/1 != pno) && (pno/pno != 1)` are always false so I'm not sure what you were trying to do. — uesp, Sep 07 '14 at 18:36

score 2 · Answer 1 · edited May 23 '17 at 10:26

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.

Is it possible to map string to int faster than using hashmap?

edited May 23 '17 at 10:26

Community

1
1

answered Sep 07 '14 at 18:30

sehe

374,641
47
450
633

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 ! – rayan Sep 08 '14 at 02:45

Is perfect hash function achieveable?

1 Answers1