Hash table construction,searching and printing example.

You, may be, imagined that when you try to do Hashing at an array throught a Hash function the job will be much more easier when you have your Hash function first ! and after it to construct the array where you will place your data.
Now we will do Hashing to an array of Linked Lists and our keys will be strings (names of people at the example).
Each one node of the linked lists will include the name of the people and his age.


 struct  node  {
char far data [20];
int age;
struct node far *next;
} s;


We will begin with a "good" Hash function first !
One is the:

/* treat strings as base-256 integers */
/* with digits in the range 1 to 255 */
//#define BASE (256)

unsigned long hash (const char *s )
{
    unsigned long m=5;
    unsigned long h;
    unsigned const char *us;

    /* cast s to unsigned const char * */
    /* this ensures that elements of s will be treated as having values >= 0 */
    us = (unsigned const char *) s;

     h = 0;
    while(*us != '\0') {
        h = (h * BASE + *us) % m;
        us++;
    }

    return h;
}


This function accepts a string and returns an integer. For example accepting "John" returns 4.
It is  "good"  when unsigned long m  integer is a long prime number and you have and some luck also. Then this function returns none or a few amount of collisions. Here we don't worry about collisions because we put our data as nodes of linked lists of an array and "on the fly".
There is a version of this function including multyplication instead of division, included at the C code.

Next we put our data as nodes at an array of linked lists using AppendNode() function
struct node far * AppendNode(struct node far **headRef, char* num , int w )

example: AppendNode(a[hash("John")],"John",20)  ;

saves person John having age 20  at linked list  a[hash("John")] of the array of linked lists.

In reverse, searching the list with search_in_list() function.
void  search_in_list(char* num, struct node **prev)

example:  search_in_list("John", a[hash("John")  ]);

At the end we print the linked list with  printlist()  function.
 void printlist( struct node **head )

 example: printlist (a[hash("John") ]);

Functions that we used are the functions of article No 34. Functions calls that are not in use are left as comments.

The C code                           Result at Hyperterminal



ps: No way to find the end of ...Hashing !!!