Thread: 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;
}