1. ## hashing help

Can somebody help me find the problem with my hash tables program. I have to produce the following output:

% full = 5, % clashes = 5
% full = 10, % clashes = 2
% full = 15, % clashes = 6
% full = 20, % clashes = 7
% full = 25, % clashes = 10
% full = 30, % clashes = 14
% full = 35, % clashes = 17
% full = 40, % clashes = 19
% full = 45, % clashes = 21
% full = 50, % clashes = 27
% full = 55, % clashes = 29
% full = 60, % clashes = 33
% full = 65, % clashes = 34
% full = 70, % clashes = 36
% full = 75, % clashes = 38
% full = 80, % clashes = 42
% full = 85, % clashes = 44
% full = 90, % clashes = 45
% full = 95, % clashes = 48
% full = 100, % clashes = 50

but my program gives the following:

full = 5, clashes = 15
full = 10, clashes = 7
full = 15, clashes = 10
full = 20, clashes = 10
full = 25, clashes = 12
full = 30, clashes = 15
full = 35, clashes = 19
full = 40, clashes = 20
full = 45, clashes = 22
full = 50, clashes = 28
full = 55, clashes = 30
full = 60, clashes = 34
full = 65, clashes = 35
full = 70, clashes = 37
full = 75, clashes = 39
full = 80, clashes = 42
full = 85, clashes = 44
full = 90, clashes = 45
full = 95, clashes = 48
full = 100, clashes = 51

Can somebody help me spot the problem with my code?Please

Code:
```#include <stdio.h>
#include <stdlib.h>

/* Small program to explore using hash tables.

1. The hash table takes up to 400 items
2. The program generates 400 six digit numbers.
3. It uses a hashing routine to place them in the hash table
4. The program prints a report on the percantage of clashes that
occur for every 20 numbers placed in the table
*/

#define EMPTY -1

int main()
{
int count, hash, number;
int clashes, hashTable[400];

/* initialise the random number generator */
srand(1);

/* initialise hash table */
for (count=0; count<400; count++) hashTable[count] = EMPTY;

/* generate 400 six digit numbers and put in hash table */
for (count=0; count<400; count++)
{
number = rand() % 1000000;     /* create 6 digit number */
hash = number % 400;           /* get a hash value of number */

/* determine if we have a clash */
if (hashTable[hash] != EMPTY)
{
clashes++;

/* Find next empty slot in hashTable */
while (hashTable[hash] != EMPTY)
{
hash = (hash + 1) % 400;
}
}
hashTable[hash] = number;

if ((count+1) % 20 == 0)
{
printf(" full  = %d,  clashes = %d\n",
(count+1)*100/400, (clashes)*100/count);
}
}

return 0;
}```

2. I'm not quite sure what you're asking. Since you're using random inputs, there is little chance that you will get an exact same result as what you've typed. Plus, it isn't even random numbers since you seed it with 1, instead of time(NULL) or something.

3. >>it isn't even random numbers since you seed it with 1, instead of time(NULL) or something.
True, but for debugging purposes, seeding srand() with a static number is the way to go.

But of course, your random number list is not the same as mine, so I get different results, hence the test is really invalid across compilers.

To do a proper test, you'll need a list of static input numbers.

>>number = rand() % 1000000;
The 1000000 is probably larger than RAND_MAX anyway, so there's little point in doing the mod.

4. I wanted to know why my numbrer of clashes differ.
My lecturer has an executable that produces the same results every time.
The only difference with my one is the number of clashes and i can figure out why they differ with the lecturers

5. Originally posted by alokin
I wanted to know why my numbrer of clashes differ.
My lecturer has an executable that produces the same results every time.
The only difference with my one is the number of clashes and i can figure out why they differ with the lecturers
See my previous post.

6. ## Re: hashing help

Code:
```   /* generate 400 six digit numbers and put in hash table */
for (count=0; count<400; count++)
{
number = rand() % 1000000;     /* create 6 digit number */```
This doesn't generate a six digit number. It creates a number that MAY BE six digits.

Code:
```for( count = 0; count < 400; count++ )
{
number = 100000 + (rand( ) % 900000);```
That generates a six digit number.

Quzah.

7. They mean binary digits. What else could they mean?
Usually when someone says a 6 digit number they mean
has you have coded it so I think you are correct.

I suspect that you have to set clashes to 0 in the 2nd loop. Can
you give a proper definition of clashes?

Coding it like that might give you an infinite loop if the table is full.
You also shouldn't use so many magic numbers such has 400.

8. Originally posted by Nick
They mean binary digits. What else could they mean?
I just showed you what else it could mean. I'm assuming this is homework. Here, let's assume I'm the teacher, and I say: "Using six digit numbers, populate a hash table until it's full and print the number of clashes."

Now you may assume that I meant "Don't go over 6 digits", when in fact I meant "Use only six digit numbers. Don't use one, two, three, four, five, or seven digit numbers, use ONLY six digit numbers."

Besides, "six binary digits" mean that the number is only a range of zero to 63. Count'm: 000000 to 111111 ... Six binary digits, for a decimal value of 0 to 63.

This is the reason you need to be specific in your requirements.

As for what a clash is, it's obvious if you look at their code:

If the hash bucket isn't empty, that's a clash. IE: Trying to use a bucket that's being used.

Quzah.

9. 000001 could be a 6 digit number. It depends on your interpretation, I suppose.

10. Originally posted by Hammer
000001 could be a 6 digit number. It depends on your interpretation, I suppose.
In mathmatics, you NEVER include preceding zeros before the decimal point. Likewise, you never include extra zeros after the decimal point. 1 is not a six digit number. Period. Anyway, it's like I said: they need to be speficic. But again, if I ask you:

True or false: This always produces three digit numbers:

x = rand() % 1000;

false

If you answer true, your teacher would fail you. 000001 is not a six digit number.

Quzah.

11. thats like saying a six digit number wheras preceeding digits of a digit > 0 are all > 0 or null. in mathematics, your right, but for program purposes, i would say 000001 is a six digit number IMO

12. Originally posted by Cgawd
thats like saying a six digit number wheras preceeding digits of a digit > 0 are all > 0 or null. in mathematics, your right, but for program purposes, i would say 000001 is a six digit number IMO
Well you'd be wrong. If you are given a number and it is converted to a decimal form, which is what is happening here, then it is a single digit number.

x = rand() % 1000000;

Assuming the result of rand is 1, x will store a single digit, decimal value.

If you print this, using standard printing methodology, you will get a single digit number. You can force it to display more, but this is atypicial.

One is not a six digit number. I refuse to argue this point with you because you are flat out wrong.

Quzah.

13. 1 is not a 'Significant' 6 digit figure, but could be a 6 figure digit ::shrugs:: IMO(opinions are never wrong!)

14. Originally posted by Cgawd
1 is not a 'Significant' 6 digit figure, but could be a 6 figure digit ::shrugs:: IMO(opinions are never wrong!)
Of course opinions are wrong. It was the world's opinion that it was flat, until it was proven otherwise. That's like saying "I believe this is the way it is... Beliefs are never wrong." But now we're off topic.

Quzah.

15. One is not a six digit number. I refuse to argue this point with you because you are flat out wrong.
Like I said in the first place, "It depends on your interpretation". My original thoughts were probably outside of the rand() example seen here.

For maths purposes, you are correct, 1 is 1, and is 1 digit long. But for other purposes, 000001 can sometimes be viewed as 6 digits.

Assuming the result of rand is 1, x will store a single digit, decimal value.
Technically not correct, imho. It will store a binary representation of a decimal 1 in an int variable, which will require lots of preceding binary 0's to pad the int. Therefore, we are storing is as 0000000....1 And how many digits is that?!

Anyway, pointless argument really We're both right, in our own way.