Thread: I need help Hashing!!

Hello everybody:

I am doing a lab for school and need major help. I am trying to read in names and phonenumbers from a text file, and put this information into a hash table. I am using lastnames for the key values. The Insert function, which inserts records(structs) into the hash table uses open addressing with linear probing. The hash table itself is simply an array of structs. The frustrating thing is that the code I have below works perfectly if I enter string literals, but when I pull in the information from a file it isn't stored properly in the table. It only seems to store the last entry read from the file. Also whe I try to print the table using the PrintTable function I created for testing purposes I get segmentation faults

Thanks...
Tim.

Code:

#define HASHSIZE 53

typedef char *Key;

typedef struct item{
	Key key;
	char *number;
}Entry;

typedef Entry HashTable[HASHSIZE];

main()
{
	char *name, *phone, *inputString;
	FILE *fp;
	Entry newEntry;
	HashTable H;
	CreateTable(H);

	inputString = (char *)malloc(50*sizeof(char));

	if((fp = fopen("phone.txt", "r")) != NULL)
	{

		while(!feof(fp))
		{
			fgets(inputString, 50, fp);
			name = (char *)strtok(inputString, "; ");
			phone = (char *)strtok(NULL, ";");
			newEntry.key = name;
			newEntry.number = phone;
			Insert(H, newEntry);
		}

	}
	else
		printf("Error in opening file.\n");


	PrintTable(H);
}

int Hash(Key s)
{
	unsigned h = 0;
	while(*s)
		h+=*s++;
	return h%HASHSIZE;
}

void CreateTable(HashTable H)
{
	int i;
	for(i=0; i<HASHSIZE; i++)
		H[i].key = NULL;
}

void Insert(HashTable H, Entry newitem)
{
		int pc = 0;
		int increment = 1;
		int probe = 0;
		
		probe = Hash(newitem.key);


		while(H[probe].key != NULL && strcmp(newitem.key, H[probe].key) && pc <= HASHSIZE)
		{
			pc++;
			probe = (probe + increment)%HASHSIZE;
			increment++;
		}

		if(H[probe].key == NULL)
			H[probe] = newitem;
		else if (strcmp(newitem.key, H[probe].key) == 0)
			printf("Same key cannot appear twice in the hash table.\n");
		else
			printf("Hash table is full.\n");
}

void PrintTable(HashTable H)
{
	int i;

	for(i=0; i<HASHSIZE; i++)
	{
		if(H[i].key)
			printf("At index: %d  Key: %s value: %s\n", i, H[i].key, H[i].number);
	}
}

Tow points :

1) Dont test with feof because fgets miget turn on end of file and u still try to prccess the line. change it to :

Code:

while ( fgets(inputString, 50, fp) != NULL)
        {
        /* add line to hash table */
        }

2) U malloc only the first string, the others are Invalid. change it to :

Code:

while ( fgets(inputString, 50, fp) != NULL)
        {
         if ( (inputString = (char *)malloc(50*sizeof(char))) == NULL )
               {
               printf("malloc %s\n", strerror(errno));
               /* do something with error */
               }
        /* add line to hash table */
        }

3) like fopen() might fail. fgets too might fail. Use ferror(FILE *fp) to check this.

Originally Posted by dude543

Tow points :

1) Dont test with feof because fgets miget turn on end of file and u still try to prccess the line.

2) U malloc only the first string, the others are Invalid.

Thank you...point 1 helped solve a different issue. I am not sure about point 2, since it seems when I malloc space of inputString, I will be overwriting the value I got for inputString from the fgets call.

I am still having problems though. The file input works fine. The hashing algorithm works fine. I have a line in the Insert function that prints out the key, value pair as well as the index of the table where the key, value pair is stored. So I can see that the correct values are available to the insert function. However when I print the HashTable, using the PrintTable() funciton, I get garbage values...almost as if it isn't able to store the values(which are strings). The code does work for literal strings hard-coded....

Code:

void Insert(HashTable H, Entry newitem)
{
		int pc = 0;
		int increment = 1;
		int probe = 0;
		
		probe = Hash(newitem.key);


		while(H[probe].key != NULL && strcmp(newitem.key, H[probe].key) && pc <= HASHSIZE)
		{
			pc++;
			probe = (probe + increment)%HASHSIZE;
			increment++;
		}

		if(H[probe].key == NULL)
			H[probe] = newitem;
		else if (strcmp(newitem.key, H[probe].key) == 0)
			printf("Same key cannot appear twice in the hash table.\n");
		else
			printf("Hash table is full.\n");
}

void PrintTable(HashTable H)
{
	int i;

	for(i=0; i<HASHSIZE; i++)
	{
		if(H[i].key)
			printf("At index: %d  Key: %s value: %s\n", i, H[i].key, H[i].number);
	}
}

Curious....
tim