Thread: Debugging Hash Table Implementation

Hi, I am having problems with my hash table program. I am implementing it with open addressing. I've been trying to debug it for hours and it is still not fixed. Thanks in advance for helping!

The file input contain names.

When I run my code, the output is:
John
Segmentation fault

The driver:

Code:

int main(void)
{
        HashTable hashtable;
        Entry item,             //item to enter into hash table
              target;           //target to be searched in the hash table
        int flag;
        FILE *fp;
        char file[MAXCHAR];
        int index;              //the index of where the target is located
        char name[MAXCHAR];

        /*  Clear terminal */
        system("clear");

        CreateTable(hashtable);

        printf("\nEnter the filename: ");
        scanf("%s", file);

        if((fp = fopen(file, "r")) == NULL)
                Error("File failed to open.\n");

        else
        {
                flag = fscanf(fp, "%s", &item.key);

                /*  Read file */
                while(flag != EOF)
                {
                        printf("%s\n", &item.key);
                        Insert(hashtable, item);
                        flag = fscanf(fp, "%s", &item.key);
                }
        }

        fclose(fp);

        printf("Enter the name you would like to search: ");
        scanf("%s", target.key);
        index = RetrieveTable(hashtable, target.key);

        strcpy(name, target.key);
        printf("%s is located in %d.\n", name, index);
}

The hash table functions

Code:

#define HASHSIZE 37
#define MAXCHAR 35
#define EQ(a,b) (!strcmp((a),(b)))


typedef char *Key;

typedef struct item {
    Key key;
} Entry;

typedef Entry HashTable[HASHSIZE];



/*=====================================================================*/
/* Insert: insert an item using open addressing and linear probing.
 * Pre:    The hash table H has been created and is not full. H has no
 *         current entry with key equal to that of newitem.
 *         Post:   The item newitem has been inserted into H.
 *         Uses:   Hash.
*/
void Insert(HashTable H, Entry newitem)
{
    int pc = 0;     /* probe count to be sure that table is not full    */
    int probe;      /* position currently probed in H                   */
    int increment = 1;  /* increment used for quadratic probing         */
    probe = Hash(newitem.key);

printf("probe = %d\n", probe);

    while (H[probe].key != NULL &&          /* Is the location empty?   */
      strcmp(newitem.key, H[probe].key) &&  /* Duplicate key present?   */
      pc <= HASHSIZE / 2)                   /* Has overflow occurred?  */
     {
        pc++;
        probe = (probe + increment) % HASHSIZE;
        increment += 2;
     }  /* Prepare increment for next iteration.*/
    if (H[probe].key == NULL)
        H[probe] = newitem;             /* Insert the new entry.    */
    else if (strcmp(newitem.key, H[probe].key) == 0)
        Error("The same key cannot appear twice in the hash table.");
    else Error("Hash table is full; insertion cannot be made.");
}

/*======================================================================*/
/* Hash:  determine the hash value of key s.
 * Pre:    s is a valid key type.
 * Post:   s has been hashed, returning a value between 0 and HASHSIZE -1
 */
int Hash(Key s)
{

    unsigned h = 0;
    while(*s != '\0')
    {
        h += *s;
        *s++;
    }

    return (h % HASHSIZE);
}
/*======================================================================*/
/*  Pre: None.
 *  Post: The hash table H has been created and initialized to be empty.
 *
 * Hash table must be created by setting the key field of each item to NULL
 */
void CreateTable(HashTable H)
{
        int i;

        for(i=0; i < HASHSIZE-1 ; i++)
        {
                H[i].key = NULL;
        }
}

/*====================================================================*/
/*  Pre: The hash table H has been created.
 *  Post: If an entry in H has key equal to target, then the function returns
 *        the index for the entry.  Otherwise, the function returns -1.
 */

int RetrieveTable(HashTable H, Key target)
{
        int location;

        for(location = 0; location < HASHSIZE-1; location++)
                if(EQ(H[location].key, target))
                        return location;
        return -1;
}

Hi, thank you for helping!

Can you please explain why do I need another copy of the key?

Originally Posted by xuftugulus

Code:

                flag = fscanf(fp, "%s", &item.key);

                /*  Read file */
                while(flag != EOF)
                {
                        printf("%s\n", &item.key);
                        Insert(hashtable, item);
                        flag = fscanf(fp, "%s", &item.key);
                }

As you can see this is where you read the new item from the file.

Code:

    if (H[probe].key == NULL)
        H[probe] = newitem;             /* Insert the new entry.    */

And this is where you insert it, ... but if you notice it is the same memory as i noted in the first
part of your code. You would need to make a copy of the key, either in the Insert function or
out of the Insert function.

Hi, thank you for helping.

I allocate the key from fscanf?

Originally Posted by vart

where do you allocate Key?

Code:

flag = fscanf(fp, "%s", &item.key);

                /*  Read file */
                while(flag != EOF)
                {
                        printf("%s\n", &item.key);
                        Insert(hashtable, item);
                        flag = fscanf(fp, "%s", &item.key);
                }

1. .key is char* so you do not need & before it not in scanf and not on printf
2. loop looks better like this:

Code:

                /*  Read file */
                while( fscanf(fp, "%s", item.key) ==1)
                {
                        printf("%s\n", item.key);
                        Insert(hashtable, item);
                }

First of all, thanks for the replies and help!

I added a copy of the key in the Insert function. I have a warning from compliing.
warning: assignment from incompatible pointer type (the line in bold below)

There are more outputs (about 6) when I run this. However, there is still segmentation fault.

Code:

/*=====================================================================*/
/* Insert: insert an item using open addressing and linear probing.
 * Pre:    The hash table H has been created and is not full. H has no
 *         current entry with key equal to that of newitem.
 *         Post:   The item newitem has been inserted into H.
 *         Uses:   Hash.
*/
void Insert(HashTable H, Entry newitem)
{
    int pc = 0;     /* probe count to be sure that table is not full    */
    int probe;      /* position currently probed in H                   */
    int increment = 1;  /* increment used for quadratic probing         */
    Key item;

    item = &newitem.key;
    probe = Hash(item);

    printf("probe = %d\n", probe);

    while (H[probe].key != NULL &&          /* Is the location empty?   */
      strcmp(newitem.key, H[probe].key) &&  /* Duplicate key present?   */
      pc <= HASHSIZE / 2)                   /* Has overflow occurred?  */
     {
        pc++;
        probe = (probe + increment) % HASHSIZE;
        increment += 2;
     }  /* Prepare increment for next iteration.*/

    if(H[probe].key == NULL)
        H[probe] = newitem;             /* Insert the new entry.    */

    else if (strcmp(newitem.key, H[probe].key) == 0)
        Error("The same key cannot appear twice in the hash table.");

    else Error("Hash table is full; insertion cannot be made.");
}

I don't quite understand how to use malloc. I'm not sure if I am doing it right here. Please correct me.

In the driver:

Code:

int main(void)
{
        HashTable hashtable;
        Entry item,             //item to enter into hash table
              target;           //target to be searched in the hash table
        int flag;
        FILE *fp;
        char file[MAXCHAR];
        int index;              //the index of where the target is located
        char name[MAXCHAR];

        /*  Clear terminal */
        system("clear");

        item.key=(Key)malloc(sizeof(Key));

        CreateTable(hashtable);

        printf("\nEnter the filename: ");
        scanf("%s", file);

        if((fp = fopen(file, "r")) == NULL)
                Error("File failed to open.\n");

        else
        {
                flag = fscanf(fp, "%s", &item.key);

                /*  Read file */
                while(flag != EOF)
                {

                        printf("%s\n", &item.key);
                        Insert(hashtable, item);

                        flag = fscanf(fp, "%s", &item.key);

                }
        }        fclose(fp);

        printf("Enter the name you would like to search: ");
        scanf("%s", target.key);

        index = RetrieveTable(hashtable, target.key);

        strcpy(name, target.key);
        printf("%s is located in %d.\n", name, index);
}

Originally Posted by matsp

Code:

item.key=(Key)malloc(sizeof(Key));

is incorrect in three ways:
1. It casts the result of malloc(), which is not needed in C as a "void *" can be automatically converted to any other type of pointer in C. It is bad because it may hide the fact that you haven't included the correct headerfile for malloc [commonly stdlib.h]

2. You are allocating only the size of a pointer - which is usually to short for a decent size string of text.

3. You are only allocating the pointer ONCE, and you are still putting the same old pointer in the hashtable each time you insert something. So when you read the next string in, you are overwriting the same bit of memory that you stored in the hash-table.

Edit: and your warning is probably becasue the function hash has not been prototyped before you call it.
Edit2: Also added 3rd item above.

--
Mats

Referring to #1:
I was looking at other threads, such as:
http://cboard.cprogramming.com/showthread.php?t=100376

it has

Code:

currNode = (fileEntry*)malloc(sizeof(fileEntry));

For #3,
The malloc should be in here?

Code:

int main(void)
{
        HashTable hashtable;
        Entry item,             //item to enter into hash table
              target;           //target to be searched in the hash table
        int flag;
        FILE *fp;
        char file[MAXCHAR];
        int index;              //the index of where the target is located
        char name[MAXCHAR];

        /*  Clear terminal */
        system("clear");

        CreateTable(hashtable);

        printf("\nEnter the filename: ");
        scanf("%s", file);

        if((fp = fopen(file, "r")) == NULL)
                Error("File failed to open.\n");

        else
        {
                flag = fscanf(fp, "%s", &item.key);

                /*  Read file */
                while(flag != EOF)
                {

                        /* malloc? */
                        printf("%s\n", &item.key);
                        Insert(hashtable, item);

                        flag = fscanf(fp, "%s", &item.key);

                }
        }        fclose(fp);

        printf("Enter the name you would like to search: ");
        scanf("%s", target.key);

        index = RetrieveTable(hashtable, target.key);

        strcpy(name, target.key);
        printf("%s is located in %d.\n", name, index);
}