Thread: 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.

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

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.

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.

This is a wonderful tutorial and has several examples (including using a hashtable with lists).

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