By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,605 Members | 1,473 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,605 IT Pros & Developers. It's quick & easy.

Help with double hashing table

P: 69
I need to write a program that will determine the number of duplicates in a table of integers by using ordinary double hashing with initialization, I need to use double hashing with each entry in the hash table initialized to indicate that it is unused.
Nov 10 '06 #1
Share this Question
Share on Google+
7 Replies


sicarie
Expert Mod 2.5K+
P: 4,677
I need to write a program that will determine the number of duplicates in a table of integers by using ordinary double hashing with initialization, I need to use double hashing with each entry in the hash table initialized to indicate that it is unused.
And did you have a question for us? Were you wondering the best way to go about this, was there a question with the hashing itself...?
Nov 10 '06 #2

P: 69
yes the best way to do it example code maybe thanks
Nov 10 '06 #3

sicarie
Expert Mod 2.5K+
P: 4,677
yes the best way to do it example code maybe thanks
Cna you tell me how you'd do it, in a few sentences?

(Sorry, but I'm not going to give you the code... not only would that defeat the purpose of you learning it, but I am also too busy, though I will be more than happy to help you with it.)
Nov 10 '06 #4

P: 69
I have this hash but dont know how to make it a double hash
dont know how

main()
{
char str[81];
int hash,i;

while (1)
{
scanf("%s",str);
hash=0;
for (i=0;
str[i]!=0;
i++)
hash=(hash*10+str[i])%1005;
printf("%s => %d\n",str,hash);
}
Nov 10 '06 #5

P: 69
when I use the qsort I get some duplicates and I'm trying to do the same thing with double hashing but I get no duplicates what I'm doing wrong?
void duplicates_Dhashing(int seed,int n)
{
int *table,i,duplicates,key;
unsigned h,h2;
n=nextPrime(n);
table=(int*) malloc(n*sizeof(int));
if (table==NULL)
{
printf("choked in duplicates_qsort()\n");
exit(0);
}
for (i=0;i<n;i++)
table[i]=-1;
srandom(seed);
for (i=0;i<n;i++)
{
key=abs(random());
printf("%d \n",key);
h=(key % n);
h2=(( key % ( n - 1 )) + 1);
while (table[h]!=-1)
h = ( h + h2 ) % n;
table[h] = key;
}
duplicates=0;
for (i=1;i<n;i++)
if (table[i-1]==table[i])
duplicates++;
printf("%d duplicates \n",duplicates);

}
Nov 14 '06 #6

P: 69
I still need help with this double hashing table when I do a qsort() I get some duplicates but with the double hashing I get 0 duplicates
Nov 17 '06 #7

P: 69
can somebody help me ? my double hashing loop is not working it looks like should be working but I dont know
for(i=0;i<m;i++)
{
key=abs(random());
h=((key+i)%m);
h2=(1+(key%(m-1)));
h=((h+(i*h2))%m);
if(table[h]==-1)
table[h]=key;
}
Nov 20 '06 #8

Post your reply

Sign in to post your reply or Sign up for a free account.