Solved

Collisions using Hashing

Posted on 1997-04-05
6
356 Views
Last Modified: 2010-04-15
The following code is NEARLY working. My AddHashEntry()
function needs to chain, dynamically, new structures when there is a collision.
I've been using a file containing the reserved words in C
which, in this implementation, are a part of the first
collision occuring in the second location of the array of
structure pointers known as hash_tab, hash_tab[1].

ALL collisions should be handled in this manner so that
a report of C's reserved words will display each of the words
contained at their locations. I FULLY understand that
this makes for a much faster search, especially if an algorithm
to MINIMIZE collisions is applied.


HERE'S MOST OF THE CODE. . . . . .

/*class.h  */

#define HASHSIZE   20

typedef struct node {
        char    *linetext;   /* For variable length lines from any file */
      struct node *next_ptr;   /* For singly linked list. */
} NODE_ENTRY;

typedef NODE_ENTRY *NODE_PTR;

typedef NODE_PTR HASH_TAB[HASHSIZE];

/* Function prototypes. */

#define MAXARRAY   280

int hash(char *);
void InitHashTab(HASH_TAB);
void AddHashEntry(HASH_TAB, NODE_PTR);
void PrintHashEntries(HASH_TAB);
int FindHashEntry(HASH_TAB, char *);

NODE_PTR node_alloc(void);
NODE_PTR makenode(char*);

void process_input_file(char *, HASH_TAB);
char *strdup(char*);
void print_node_entry(NODE_PTR);
void getinputfile(char *);


This program was compiled using Turbo C/C++ 3.0 DOS using the large
memory model
and selecting adherence to ANSI C language compliance.


/* The following function, FindHashEntry(HASH_TAB hash_tab, char *key),
   as yet unfinished and amongst other things, calls the hash(char *key)
   function WITHIN the index brackets [] to create an index value for
   the reserved word PASSED to it. It then assigns the index as part
   of a pre-defined array to a POINTER TO THE ARRAY, as in:
            NODE_PTR node_ptr = hash_tab[hash(key)];
   It compares the value of node_ptr->linetext to the parameter, 'key'.
   So that: If entry exists return 1 else return 0.
*/


int FindHashEntry(HASH_TAB hash_tab, char *key)
  {

  NODE_PTR node_ptr = hash_tab[hash(key)];/*Get hash index from hash
function.*/
  NODE_PTR np = node_ptr;

        /* Traverse the linked list
           until you find it or hit the end of the linked list. */

       /* This cell in the table is already in use. See if the current string
          has already been inserted, and if so, increment its count.
       */

              for ( np = node_ptr; np != NULL; np = np->next_ptr)
       if ( strcmp(node_ptr->linetext,key ) == 0)
       {
       printf("key: %s and node_ptr->linetext: %s are equal. Call AddHash\n",
key, node_ptr->linetext);
       return 1;
       }
                               else
                               node_ptr = node_ptr->next_ptr;

                         /**********************/

return 0;   /* Not found! */
}    /* End FindHashEntry. */



/* The following function, process_input_file, is the "work horse" of
this
   program. It performs MANY duties. It checks to see that a valid
filename
   was passed to this program for processing, stopping execution of this
   program upon encountering an invalid/corrupt file. It uses
   fgets(file_buffer,MAXARRAY, infp) to get EACH line from the input
file.
   It then takes the string in file_buffer and REMOVES the <cr>
(carriage
   return). It then allocates a node, node_ptr (defined within this
function)
   through the use of a call to makenode(char *w) passing it the
modified string
   NOW contained in the variable, file_buffer, as in:
                  makenode(file_buffer);
   Next, it uses an if test to determine if a call to
   FindHashEntry(hash_tab, node_ptr->linetext). If it is FALSE,
   the function AddHashEntry is called passing to it the originally
   initialized hash table(hash_tab) and node_ptr. If it is TRUE,
   then a message stating that that particular string has already been
   entered is outputed.

  ->> Read the reserved words from the input file ( one word / line),
make a
      node for the linked list, add the node to the linked list if the
word
      has not been previously entered.
 */



void process_input_file(char *i_file_name, HASH_TAB hash_tab )
  {
       char file_buffer[MAXARRAY];

       FILE *infp; /* Pointer to input stream of type FILE. */

       NODE_PTR node_ptr;

       /* Open input file. Test for good file name. */

              if ((infp = fopen(i_file_name,"r")) == NULL) {
                          printf("Error in input file name : %s\n",i_file_name);
                          exit(-1); /* Stop processing. */
              }

       /* Read lines from input file, invoke hash function */

              while( fgets(file_buffer,MAXARRAY , infp) != NULL ) {
                          file_buffer[strlen(file_buffer) - 1] = '\0'; /* Replace cr with
null */
                          node_ptr = makenode (file_buffer);
                          /* printf("node_ptr->linetest is %s\n", node_ptr->linetext); */

                        /* If FALSE, call AddHashEntry() */

                        if ( !FindHashEntry(hash_tab, node_ptr->linetext )) {
                        AddHashEntry(hash_tab, node_ptr);
                                    node_ptr = node_ptr->next_ptr; /* Added 3/31/97 */
              }
                                    else
                                    printf("\"%s\" has already been entered into the hash table\n",
                                    node_ptr->linetext);


              } /* End while. */

} /* End process_input_file. */




/* The following function, AddHashEntry, requires that each of the
reserved
   words be entered into their proper place in the hash table. This
needs to
   be accomplished in this fashion:
            1) Go to a cell in the hash table
            2) check to see if anything is there
                  if not, ( if NULL ) then
                        a) add the reserved word to that part of new node
                        b) assign the ADDRESS of the new node to the cell
                           where the node is created.
            3) If there IS a node or there are multiple nodes then
                        a) check to insure that the string is not already
                           there. If it is, insert the NEW node FIRST in the list.
                           This is to defeat duplication of entries.

So,
->> Add an entry to the hash table, if an entry already exists at that
cell,
            then insert the new node first in the list since all reserved words in
            the input file are unique.
*/
/* As of 4/05/97, it is yet unfinished. */



void AddHashEntry(HASH_TAB hash_tab, NODE_PTR node_ptr)
  {
        /* As the name suggests this function adds an entry into the chained
hash
            table.
        Work is needed here to store entries and handle collisions, etc.
        */

       int value = 0;
       NODE_PTR np;
       np = node_ptr;
       value = hash(np->linetext);

       /* NULL means that this cell hasn't been used yet. Space
          needs to be allocated for it and the data put there.
       */
              /* printf("word '%s' has a hash value of %d\n", np->linetext,
value); */


        hash_tab[value] = node_ptr;

               if ( (hash_tab[value]->linetext != NULL ) )

              {
                 hash_tab[value]->linetext = np->linetext;
                 /*printf("linetext = '%s'\n", np->linetext); */

                 np->next_ptr = makenode(hash_tab[value]->linetext);



                 /* printf("index %d contains '%s'\n", value,np->linetext); */
                 np = np->next_ptr;
              }

                 /*else
                 {
                  for ( np = node_ptr; np->linetext != NULL; np = np->next_ptr);

                 } */



  } /* End AddHashEntry. */
0
Comment
Question by:jnowlin
6 Comments
 

Author Comment

by:jnowlin
ID: 1249818
Edited text of question
0
 

Author Comment

by:jnowlin
ID: 1249819
Why is this so straightforward and yet so f*!#% ing difficult?!
0
 
LVL 5

Expert Comment

by:julio011597
ID: 1249820
Couldn't it be a problem of good rating your questions?

Cheers, julio
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Expert Comment

by:dominus
ID: 1249821
Probably nobody wants to help you because
 1. You didn't state clearly what you wanted.
 2. It looks like you're a student trying to cheat on a homework      assignment.
 3. 15 points is not enough to tempt someone to spen their time       debugging your program.

Of course, there might be some other reason, too.
0
 

Author Comment

by:jnowlin
ID: 1249822
1. Why doesn't the function AddHashEntry() work, as written?
    ( A QUESTION )

2. This WAS a homework assignment handed in incomplete some
   3 weeks ago. I was told by management that questions asked
   in Experts Exchange are NOT limited to people poking
   around with a computing problem because it was Tuesday,
   and it was raining that day. Therefore, academically related
   questions are "Okie dokie".

3. I was wrong in the number of points I offered. Let's see if I
   can get jos or someone else in the top 15 experts 'tempted'.
   50

4. I don't know what "some other reason" means or implies.

0
 
LVL 1

Accepted Solution

by:
prc earned 50 total points
ID: 1249823
Well, I'll have a go, although I do so with some trepidation ;-)

It looks to me like (among other things) you have a problem with what you consider to be an empty cell in the hash table.  The obvious thing to do, which you suggest in some of the code is to treat a NULL in the hash table itself as meaning empty.  In AddHashEntry, though, you seem to be assuming that the pointer in hashtab will point to a valid NODE_ENTRY, and are checking whether the linetext is set.  It's not obvious to me how you could ever get a node with linetext = NULL.  There are also various lines in AddHashEntry which make no sense at all, like assigning the hashtab[value] as soon as you get in there - what is going to happen to any existing nodes?

You haven't posted the code for 'makenode'.  I hope it calls strdup, or all your nodes will point to your (temporary) file_buffer which gets overwritten each time.

Can I make a cruel-but-kind suggestion?  Scrap all this and sit down with some pictures of the structure you want, then, as you have started to do, code up each operation you can imagine into a separate function.  Keep in mind all the time what the _meaning_ of a NULL pointer is in each situation, and don't forget that pointers don't copy the data they point to.  I know this sounds a bit condescending, but even experienced programmers make these mistakes.  I can't design a data structure without a picture of it.

I hope this helps.

Cheers

Paul
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

758 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

19 Experts available now in Live!

Get 1:1 Help Now