need help with hash tables with direct chaining

This is a discussion on need help with hash tables with direct chaining within the C Programming forums, part of the General Programming Boards category; ok i need to design a hash tables that uses direct chaining as a collision resolution method. my program needs ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    67

    need help with hash tables with direct chaining

    ok i need to design a hash tables that uses direct chaining as a collision resolution method.
    my program needs to read in a .txt file and insert words into a hash table. i know who to make it read in and stuff and i got the basic hash function. I am stuck on how to actually write a function that installs words into a table and if the word is already there it uses linked list to put another one in. as far as i understand install function needs to use lookup function to check if the word is already there. is that correct? here is what i got so far:
    Code:
    typedef struct nlist { char k[40]; struct nlist *next; } ;
    
    #define HASHSIZE 101
    
    static struct nlist *hashtab[HASHSIZE];
    
    unsigned hash (char *s)
    {
    	unsigned hashval;
    	
    	for (hashval = 0; *s != '\0'; s++)
    		hashval = *s + 31 * hashval;
    	return hashval % HASHSIZE;
    }
    this is the a basic hash func i am testing. here is the lookup function i got from a book and hoped to modify to match my requirements:
    Code:
    struct nlist *lookup (char *s)
    {	
    	struct nlist *np;
    	
    	for (np = hashtab[hash(s)]; np != NULL; np = np -> next)
    		if (strcmp(s, np -> k) == 0)
    			return np;
    	return NULL;
    }
    and this is the install func, but this one instead of adding another word to the list, it replaces it which is something i don't want it to do:
    Code:
    struct nlist *install (char *name)
    {
    	struct nlist *np;
    	unsigned hashval;
    	
    	if ((np = lookup (name)) == NULL){
    		np = (struct nlist *) malloc (sizeof (*np));
    		if (np == NULL || (np -> name = strdup (name)) == NULL)
    			return NULL;
    		hashval = hash (name);
    		np -> next = hashtab[hashval];
    		hashtab[hashval] = np;
    	}else
    		free ((void *) np -> name);
    	if (( np -> name = strdup(name)) == NULL)
    		return NULL;
    	return np;
    }
    so to summarize i am confused as to how to implement the install func so when the slot in the hashtable is free it inserts the word, and if it is occupied it simply adds another one in there.

  2. #2
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    what are you hashing onto a structure with what inside? Basically if the spot is free you allocate room for it and assign, but if not you use a linked lists implementation to add another one to the same spot. I am confused on what you want to do though so I may be misunderstanding

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    67
    my program needs to read in a .txt file word by word and place those words into a hash table. i know how the hash table and hashing work in theory it's the coding bit that throws me off. i want it to read in a string(which is a word) and put it into a hash table. if there is already another word in there then it needs to use the linked list to put another one in.

  4. #4
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    At first glance, i couldn't say why it's not inserting the new data correctly (at least, when the data isn't already in the table). It looks like you are linking correctly. Note that your code is rather on the poor side.

    Also, there's some "errors" in it.

    Code:
    typedef struct nlist
    {
        char k[40];
        struct nlist *next;
    };
    
    // In code, we see...
    struct nlist *np = malloc(...);
    np->name = strdup(name);    // + it's wrong since k is a static array
    So maybe you should look two times before posting code. Give us an up to date version of your work and we might help you (at least, we'll be able to).

    Beside that, i didn't even know that
    Code:
    unsigned hashval;
    was a valid declaration of variable. Guess it's equal to "unsigned int hashval;", right ?

    By the way, i think strdup() isn't a standard C function.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    This is a wonderful tutorial and has several examples (including using a hashtable with lists).

    http://eternallyconfuzzled.com/tuts/...hashtable.aspx

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. developing hash tables in the C Programming language
    By w108dab in forum C Programming
    Replies: 1
    Last Post: 05-20-2008, 12:20 PM
  2. Hash tables - chaining
    By cosmo1996 in forum C Programming
    Replies: 2
    Last Post: 08-15-2007, 12:53 AM
  3. Group Project Help/Volunteer
    By DarkDot in forum C++ Programming
    Replies: 3
    Last Post: 04-25-2007, 12:36 AM
  4. Chaining Hash Tables (in C)
    By sql.scripter in forum C Programming
    Replies: 18
    Last Post: 09-25-2006, 02:05 AM
  5. Problems with Hash Tables
    By Zildjian in forum C Programming
    Replies: 6
    Last Post: 11-06-2003, 08:53 PM

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