Debugging Hash Table Implementation

This is a discussion on Debugging Hash Table Implementation within the C Programming forums, part of the General Programming Boards category; Hi, I am having problems with my hash table program. I am implementing it with open addressing. I've been trying ...

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    27

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

  2. #2
    uint64_t...think positive xuftugulus's Avatar
    Join Date
    Feb 2008
    Location
    Pacem
    Posts
    355
    Code:
                    flag = fscanf(fp, "&#37;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.
    Code:
    ...
        goto johny_walker_red_label;
    johny_walker_blue_label: exit(-149$);
    johny_walker_red_label : exit( -22$);
    A typical example of ...cheap programming practices.

  3. #3
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,456
    where do you allocate Key?

    Code:
    flag = fscanf(fp, "&#37;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);
                    }
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    Hi, thank you for helping!

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



    Quote Originally Posted by xuftugulus View Post
    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.

  5. #5
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    Hi, thank you for helping.

    I allocate the key from fscanf?


    Quote Originally Posted by vart View Post
    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);
                    }

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So, "Item" is of the type Entry, which holds "key" which is a pointer to char. The pointer to char is never actually allocated to point to some memory, so that will fail in itself.

    Also, when you store a pointer to char, you need to make sure that EACH stored item is unique - you mustn't re-use the same memory for multiple entries.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,456
    I allocate the key from fscanf?
    scanf will fill the buffer with the data read from file
    buffer should be reeady before that and big enough to store the data

    you can allocate it using malloc

    regular technic will be read into static buffer
    char buffer[1024];
    and if read successful use strlen (or return value of fscanf) to determine required key len,
    allocate that number of bytes (not forgetting about nul-character) and copy strint read into the allcocated buffer
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  8. #8
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    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 = &#37;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);
    }

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Last edited by matsp; 03-14-2008 at 05:50 AM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Mar 2008
    Posts
    27
    Quote Originally Posted by matsp View Post
    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:
    Link List help please

    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);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Writing array, to file
    By zootreeves in forum C Programming
    Replies: 9
    Last Post: 09-08-2007, 05:06 PM
  2. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-24-2007, 11:36 PM
  3. Hash table creation and insertion
    By tgshah in forum C Programming
    Replies: 1
    Last Post: 01-23-2006, 06:54 PM
  4. Hash Table implementation
    By supaben34 in forum C++ Programming
    Replies: 6
    Last Post: 09-26-2003, 12:48 PM
  5. hash table data structure implementation
    By sanju in forum C Programming
    Replies: 1
    Last Post: 09-27-2002, 05:06 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21