Thread: Chained hash tables using an array of lists

  1. #1
    Registered User
    Join Date
    May 2003
    Posts
    7

    Question Chained hash tables using an array of lists

    I know how to use linked lists (is that similar to an array of lists?) and I kind of understand the concept of hash tables. But how would I implement a hash table using an array of lists. Also, how do I XOR characters?

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Try looking at Google for linked list tutorials.

    To XOR two values, use the ^ and ^= operators.

    Code:
    char a, b;
    a = 'a';
    b = 'b';
    
    a ^= b;
    b ^= a;
    a ^= b; // Now a = 'b' and b = 'a'
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >But how would I implement a hash table using an array of lists.
    Play around with this simple hash table with linked list chaining. It's really very simple, you just have to see how things work.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define TABSIZ 200
    
    struct TabRec {
        struct TabRec *next;
        char name[BUFSIZ];
    };
    
    static struct TabRec *htable[TABSIZ];
    
    unsigned hash(char *s)
    {
        unsigned h;
    
        for (h = 0; *s; s++)
            h = *s + 31 * h;
    
        return h % TABSIZ;
    }
    
    struct TabRec *find(char *name)
    {
        struct TabRec *item;
    
        for (item = htable[hash(name)]; item; item = item->next)
        {
            if (strcmp(name, item->name) == 0)
                return item;
        }
    
        return NULL;
    }
    
    struct TabRec *insert(char *name)
    {
        struct TabRec *item;
        unsigned h;
    
        if ((item = find(name)) == NULL)
        {
            /* Not found, add */
            if ((item = malloc(sizeof (*item))) == NULL)
                return NULL;
    
            strcpy(item->name, name);
    
            h = hash(name);
            item->next = htable[h];
            htable[h] = item;
        }
    
        return item;
    }
    
    int main(void)
    {
        char buf[BUFSIZ];
        struct TabRec *item;
    
        while (fgets(buf, sizeof (buf), stdin))
        {
            if (insert(buf) == NULL)
                break;
        }
    
        printf("Enter a name to find: ");
        fflush(stdout);
    
        if (fgets(buf, sizeof (buf), stdin))
        {
            if ((item = find(buf)) != NULL)
                printf("%s", item->name);
        }
    
        return 0;
    }
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How do I utilize an array of linked lists?
    By sharrakor in forum C Programming
    Replies: 7
    Last Post: 02-14-2009, 10:46 AM
  2. Replies: 5
    Last Post: 08-01-2007, 06:17 AM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  4. hash tables
    By ender in forum C++ Programming
    Replies: 0
    Last Post: 05-08-2002, 07:36 AM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM