I need help Hashing!!

This is a discussion on I need help Hashing!! within the C Programming forums, part of the General Programming Boards category; Hello everybody: I am doing a lab for school and need major help. I am trying to read in names ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    5

    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);
    	}
    }

  2. #2
    Registered User
    Join Date
    Nov 2005
    Posts
    95
    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.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Or just check the return values of fopen and fgets.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Nov 2005
    Posts
    5
    Quote 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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Creating Linked List Using Hashing and Stack
    By m0ntana in forum C Programming
    Replies: 2
    Last Post: 04-07-2007, 07:11 AM
  2. Hashing, indexing and phonetic normalization for approximate str matching...
    By biterman in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 11-21-2006, 08:42 AM
  3. Replies: 8
    Last Post: 09-11-2006, 11:26 AM
  4. Doubt about Hashing
    By louis_mine in forum C Programming
    Replies: 1
    Last Post: 11-10-2005, 11:00 PM
  5. Double Hashing
    By carrja99 in forum C++ Programming
    Replies: 1
    Last Post: 03-28-2003, 07:36 AM

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