Thread: Hash Table outputting incorrect number

Before we begin, I'll tell you this is for an assignment. I do not expect you to write it all out for me, but to highlight where I have been going wrong.

The program below is reading in an uncompressed .tga file (an example I have uploaded here: http://paul-skinner.com/stuff/uni/da...tures/lena.tga ).

It is then turning the image in to greyscale, and finally putting the data in to a hash table with chaining as its collision detection.

Once this is done, the hash table is printed out along with the total number of unique entries.

This is where it's going wrong.

Data is being inputted in to the hash table, however the amount of unique entries should be 204 (this is based on the tga file referenced to above and has been told to me beforehand by the lecturer).

I cannot for the life of me see why it's outputting incorrectly as 59.


You may want to put a system("pause") or getchar in to make it stop before exiting.

To run the program you must give the full path to the .tga file (possibly in quote marks) as the first argument.

Example:

"C:\assignment.exe" "C:\lena.tga"


Thank you in advanced for any advice.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <cstdlib>
#include <cstdio>

#define HEADERSIZE  18

#define W_LSB       12
#define W_MSB       13
#define H_LSB       14
#define H_MSB       15

#define HASHSIZE    211  //This is the first prime past 204
#define N           230

int T[HASHSIZE];

struct node
{
   int key;
   struct node *next;
};

node * ListStart = NULL;

int storage_attempts = 0, retrieval_attempts = 0;

int hash(unsigned char key, int startnum);
void hashtable(unsigned char *I);
int findData(int key);
int hash(int key);
void addToOverflow(int key);
void printTable();
void printOverflow();
int openTGA(char *arg1);
void loadTGA(int total, unsigned char *I, char *arg1);

int main(int argc, char** argv)
{



   int total = 0;

   total = openTGA(argv[1]); //return MxN

   unsigned char I[total];

   loadTGA(total, I, argv[1]);

   hashtable(I);

   //getchar();


}

    //---------------------End Main---------------------//

int openTGA(char *arg1)
{
   int i; 
   unsigned char header[HEADERSIZE];
   FILE *fp;

   printf("Opening Input Image '%s' ... ", arg1);fflush(stdout);
   fp = fopen(arg1,"rb");
   if(!fp)
   {
      printf("\n\nARGH! File couldn't be opened.\n");fflush(stdout);
   }
   printf("Done.");fflush(stdout);


   printf("\n\nReading %d Byte Header ... ", HEADERSIZE);fflush(stdout);
   fread(header, HEADERSIZE, 1, fp);
   printf("Done.");fflush(stdout);


   printf("\n\nHeader Contents: ");fflush(stdout);
   for(i=1;i<HEADERSIZE;i++)
   {
      printf("|%d|", header[i]);fflush(stdout);
   }

   int m = (header[W_MSB]*256) + header[W_LSB];
   int n = (header[H_MSB]*256) + header[H_LSB];

   printf("\n\nDimensions Extracted: Width=%d, Height=%d.", m, n);
   fflush(stdout);
   fclose(fp);

   return (m*n);
}
void loadTGA(int total, unsigned char *I, char *arg1)
{

   int x = 0;
   unsigned char header[HEADERSIZE];
   unsigned char Rt, Gt, Bt;

   FILE * fp;

   fp = fopen(arg1,"rb");
   if(!fp)
   {
      printf("\n\nARGH! File couldn't be opened.\n");fflush(stdout);
   }
   printf("Done.");fflush(stdout);


   printf("\n\nReading %d Byte Header ... ", HEADERSIZE);fflush(stdout);
   fread(header, HEADERSIZE, 1, fp);
   printf("Done.");fflush(stdout);


   printf("\n\nReading RGB Data & Calculating Greyscale ... ");fflush(stdout);
   for(x=0;x<total;x++)
   {
      fscanf(fp, "%c", &Rt);
      fscanf(fp, "%c", &Gt);
      fscanf(fp, "%c", &Bt);

      I[x] = (Rt+Gt+Bt)/3;
   }
   fclose(fp);
   printf("Done.");fflush(stdout);

   fclose(fp);
}



void hashtable(unsigned char *I)
{
   int table_count = 0, overflow_count = 0, x=0, k = 0;

   for(x=0; x<N; x++)
   {

         k = I[x];

         if(T[hash(k)] == '\0')
         {
            // Empty Space, Insert New Item
            T[hash(k)] = k;
         }
         else if(T[hash(k)] != k)
         {
            // Collision, add item to overflow
            addToOverflow(k);
         }
   }

   // Print hash table
   printf("\nHASH TABLE\n\n");
   printTable();

}



int hash(int key)
{
   int i;

   i = key % HASHSIZE;

   return i;
}

void addToOverflow(int key)
{
   node * temp;

   temp = new node;
   temp->key = key;
   temp->next = NULL;

   if(ListStart == NULL)
   {
      ListStart = temp;
   }
   else
   {
      temp->next = ListStart;

      ListStart = temp;
   }
}

int findData(int key)
{
   retrieval_attempts = 1;

   int i = key % HASHSIZE;

   if(T[i] == key)
   {
      // Hash location is correct, return data
      return T[i];
   }
   else
   {
      // Hash location is incorrect, search linked list
      node * current;

      current = ListStart;

      do
      {
         if(current->key == key)
         {
            retrieval_attempts++;

            return current->key;
         }
         else if(current->next != NULL)
         {
            retrieval_attempts++;

            current = current->next;
         }
         else
         {
            retrieval_attempts++;

            return -1;
         }
      } while(current != NULL);
   }
}

void printTable()
{
   int temp = 0, counter = 0;
   for(int i=0; i<HASHSIZE; i++)
   {
      temp=T[i];
      printf("%7d", temp);
      if (temp!=0)
      {
         counter++;
      }

      if(i%10==0) printf("\n");
   }
   printf("\n\n=%d=\n\n", counter);
}

I'm not quite sure I know what you're seeing and what you want to be seeing. Are things not hashing to the correct place? Are you miscounting how many elements are in your hash table? Something else?

Originally Posted by Salem

> fscanf(fp, "%c", &Rt);
Perhaps use fgetc() instead.
Does this even work for a binary file, in particular something like a \0 ?

In any event, checking the return result of your file reading functions would be a good idea as well.

fscanf(fp, "%c", &Rt); works fine

I found the answer in the end.

#define N was set to too low a number.

I forgot that N needed to be the total POSSIBLE collisions (512*512), not the number I knew it to be.

I've removed N and passed total to hashtable() now, and it's working fine.

Thanks for your help anyway.