Thread: Chained hash tables using an array of lists

  1. #1
    Registered User
    Join Date
    May 2003

    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
    Ontario, Canada
    Try looking at Google for linked list tutorials.

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

    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
    >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.
    #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)
        printf("Enter a name to find: ");
        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