Solved

Hash tales: having trouble incrementing through the array

Posted on 2003-12-08
5
396 Views
Last Modified: 2010-04-15
This is a problem with hash funcitons, hash tables , function pointers and arrays.
First two arrays  done and now am onto the hash function portion.
I am able generate the initial hash value, now need to do table 3 which is as follows:

Table 3 is constructed within the function used to make the hashTable. Using the programData array send each word to the hash function for element 0-99. As the index value for each work is returned from the hash function store the word  and its index value in an appropriate data structure. Copy the word into the hashTable element based upon its index value using linear crash resolution where appropriate. Before applying the linear crash resolution, if required, increment a counterArray element by one to track the number of words which initially hashed to that index numer and finally get the next word.

I am confused about where to implement getting the subsequent vlues for the programData array and have been trying to the point of utter frustration...
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define MAXSIZE 139
#define DATA_FILE  "a:\\269data.txt"
#define SIZE 100

void getWords(char programData[][6])
{
    int idx=0;
    char word[7];
    FILE *fptr;
    fptr=fopen(DATA_FILE, "r"); //open file for reading
         if(fptr==NULL)
         {
          printf("file error-end program");
          exit(0);
         }
          while(fgets(word, 7,  fptr))
          {
             word[strlen(word)-1]= '\0';
             strcpy(programData[idx], word);
             idx++;
          }
         fclose(fptr);    //close file
}  //endfunc



void printTable(char array[][6])
{
     int idx=0;
     for(idx=0; idx<100; idx++)
       {
       printf("%-8s", array[idx]);
          if(idx+1 %10==0)
          printf("\n");
      }
}//endfunc


copyArray(char sortedData[][6], char programData[][6])     //copy programData into sortedData array for sorting
{

     int index, i, j,loc, x;
     char min[6];
     index=100;
     i=0;

     while(i<index)
     {
       strcpy(sortedData[i], programData[i]);
       i++;
      }
}//endfunc



int myCompare(const void *a1, const void *a2)
{
       int A;
       int result;
       A=strcmp((char *)a1,(char *)a2);

       if(A > 0)
           result=1;
        else if
          (A < 0)
            result=-1;
        else
            result=0;

        return result;
}


sortProgramData(char sortedData[][6])
{
    int x;
    qsort((void *)sortedData, SIZE, sizeof(char[6]), myCompare);

}


void initHashTable(char hashTable[MAXSIZE][6])
{

  int idx;

  for(idx=0; idx <MAXSIZE;idx++)
  {
    hashTable[idx][6]='\0';
    idx++;
   }

}



int hash1(char *str1)
{

   int sum=0;
   int key=0;
   int x=0;    //hash value count

      if(str1 == NULL) //if string has null value
          key = -1;     //result will be -1

      while(*str1)
       {
           sum += *str1;
           *str1++;
       }

      key=sum % MAXSIZE;
      return key;
}

int insertHashTable(char *hashTable, int key)
  {
     int keyCount=0;
     int idx=0;

       if(hashTable[idx]=='\0')
           hashTable[idx]=key;
       else
         {
            hashTable[idx++];
         }

     return keyCount;

}



/*int findHashEntry(char *hashTable, int key)
{

 }*/

void loadHashTable(char *str1, char *str2, int(*fp)(char *))
{

          int key;
          int keyCount;
          int i;

             key=hash1(str1);
             keyCount=insertHashTable(str2, key);
             printf("%d\n",key);

}


int main()
{
       int x;
       char programData[100][6]={'\0'};
       char sortedData[100][6]={'\0'};
       char hashTable[MAXSIZE][6];
       int(*fp)(char*)=(hash1);


        //read data file and print table 1
        getWords(programData);
        printf("\nTABLE 1 Initial Program Data as Read from 269data.txt\n");
        printTable(programData);//table1

        system("PAUSE");

       //create the sorted array to be used for table 5 and print table 2
        copyArray(sortedData,programData); //copy the array read from the file
        sortProgramData(sortedData);       //sort the array using "c" qsort)
        printTable(sortedData);            //print table 2

        system("PAUSE");

        //process the 4 hash functions
        for(x=0; x < 5; x++)
          {
           initHashTable(hashTable); //initialize hashTable to "empty state"
           loadHashTable(*programData, *hashTable, *fp);  //load the hash table and output Table 3

          }


           system("PAUSE");


return 0;

}



 
0
Comment
Question by:closet
  • 3
  • 2
5 Comments
 
LVL 45

Accepted Solution

by:
Kdo earned 400 total points
ID: 9898490

Hi closet,

There are some pretty big pieces of your design missing.  Even so, I think that I can shed some light here.

The purpose of a hash table is to mathematically reduce sparce keys so that they are nearly consecutive.  When a key is reduced, it may be unique within the set of known keys or it might be a duplicate.  If it is a duplicate it might be the first duplicate or just 1 of any number of duplicates.

What I don't see in your solution is a way to resolve duplicates.  And because your design isn't shown, let me demonstrate two "general" way to solve this.


The first is with a linked list.  Each node contains a pointer to another node.  The hashtable contains the address of the first node in the chain with a given key.  The chain contains the rest of the nodes with the same key.

#define TableSize 100

typedef struct
{
  char NodeName[24];                   /*  This is the value to hash  */
  /*  User data  */
  node_t  *Next;
}  node_t;

node_t *HashTable[TableSize];

int GenerateHash (char *string)
{
  int KeyValue;                             /*  Compute a generic value based on the passed string  */
  return (KeyValue % TableSize);  /*  Reduce to a value that will fit into the table  */
}

int AddItem (node_t *Node)
{
  node_t *TmpNode;
  int       Index;

  Index = GenerateHash (Node->NodeName);
  if (HashTable[Index])                          /*  A node with this key is already saved  */
  {
    TmpNode = HashTable[Index];
    while (TmpNode->Next)                    /*  Find last node on this chain  */
      TmpNode = TmpNode->Next;
    TmpNode->Next = Node;                  /*  Add the new node to the end of the chain  */
  }
  else
    HashTable[Index] = Node;


The second solution requires a bit more effort and code.  The hash table points to a buffer that contains some number of nodes and some control information.  Instead of a linked list of nodes, you maintain a linked list of buffers.  The advantage here is that searaching and maintaining a linked list of buffers can more efficiently utilize system resources than a linked list of nodes.  The disadvantage is that maintaining a linked list of nodes is easier to code and maintain.

If this doesn't point you in the right direction, just give me a little more detail on what you need and I'll give you some more feedback.

Good Luck,
Kent

0
 

Author Comment

by:closet
ID: 9899307
Kent
This is the part of the problem that is confusing me,
Copy the word into the hashtable element based upon its index value using linear crash resolution.

I originally thought this would be your second solution, but now I am not sure. What do you think?
Thanks
Closet
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9899509

Hi closet,

Here's the AddItem() function that I included earlier:

1>  int AddItem (node_t *Node)
2>  {
3>    node_t *TmpNode;
4>    int       Index;
5>  
6>    Index = GenerateHash (Node->NodeName);
7>  if (HashTable[Index])                          /*  A node with this key is already saved  */
8>    {
9>       TmpNode = HashTable[Index];
10>      while (TmpNode->Next)                    /*  Find last node on this chain  */
11>      TmpNode = TmpNode->Next;
12>      TmpNode->Next = Node;                  /*  Add the new node to the end of the chain  */
13>    }
14>    else
15>      HashTable[Index] = Node;

Lines 6 and 15 do what the instructions say:  Line 15:  "Copy the word into the hashtable element", Line 6:  "based upon its index value using linear crash resolution."

GenerateHash() performs the calculations that reduce the key field to an index into the Table.  Once the index is derived, it's either placed directly into the table, or append to the chain as an overflow item.  Note that the code inserts the item as the last item on the chain.  If the order isn't important, you can put it on the front of the chain by replacing lines 7-15 with these two lines:

Node->Next = HashTable[Index];
HashTable[Index] = Node;

In either case, you will have saved the node as an element that can be later retrieved by it's hash key.


Kent
0
 

Author Comment

by:closet
ID: 9900069
Okay, good.
I was working on that solution while waiting for your reply. I have one more question though.
My prof hated using typedefs for structs so I am not great at using them for structures. Usually I declare the struct node *whatever, then when I send the parameter to a function I send the address of the link (&head) list. I am not sure what to send the add item using the typedef structure. Can you tell me? Thanks Closet.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9900124
Sure.

You don't have to typedef the struct.  I do simply out of habit.

struct node_t;

struct
{
  char NodeName[24];                   /*  This is the value to hash  */
  /*  User data  */
  struct node_t  *Next;
}  node_t;

struct node_t *HashTable[TableSize];

int AddItem (struct node_t *Node);


That's the same thing, but the structs aren't typedef'd.

Kent
0

Featured Post

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Retrun object in plist format 5 50
Is string constant address ? 10 189
Which checksum is this? 7 136
convert char array to number in c 5 77
Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.

705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now