It's me again with the second part for Hashing! The last part is here and you should read it first to understand some things better, cause here I will only implement Linear Probing in C. I will also explain what needs to be changed to implement another Open Address Method directly! So, let's get started!

Linear Probing Implementation:

    It's pretty easy to implement this type of a Hashtable. It's a simple Array of specific "prime" size and we will insert the values in the hashindex or the next available space if a collision happens. I think the Code will explain itself!

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 53

#define h(x) (x % m) //h(x) = x mod m

// function declarations

void fill_array(int *A, int table_range, int number);

void insert_table(int *table, int table_range, int hash_index, int val);

void print_table(int*table, int table_range);

int search_table(int *table, int table_range, int val);

void delete(int *table, int table_range, int val);

int main(){

    int *table; // hashtable

    int i, j, n, choice, index;

    int search, val;

    int num = 0; // insert count (I don't check deletions)

    printf("--h(x) = xmod%d--\n", N);

    printf("\n\n");

    table = (int*)malloc(N*sizeof(int));

    // initialize to -1, value that represents emptyness

    for(i = 0; i < N; i++){

     table[i] = -1; 

    }

    while(1){

 printf("1.Insert random numbers\n");

 printf("2.Delete a number\n");

 printf("3.Search a number\n");

 printf("4.Show Hash Table\n");

 printf("0.Exit Programm\n");        

 printf("\n--------\n");

 printf("Choice: ");

 scanf("%d", &choice);

 switch(choice){

     case 0: exit(0);        

     case 1:

         // insert random numbers

         do{

             printf("Lot to insert(<%d): ", N-num);

             scanf("%d", &n);

         }while(N - num < n);

         num += n;

         fill_array(table, N, n);

         printf("Filled Array with %d random values\n", n);

         printf("\n--------\n");

         break;

     case 2:

         // delete a number

         printf("Give a value you want to delete: ");

         scanf("%d",&search);

         delete(table, N, search);

         printf("\n--------\n");

         break;

     case 3: 

         // search for a number

         printf("Search for a value: ");

         scanf("%d",&search);

         index=search_table(table, N, search); 

         if(index == -1){

             printf("This value doesn't exist on HashTable!\n");

         }

         else{

             printf("Value was found at table[%d]\n", index);

         }

         printf("\n--------\n");

         break;

     case 4:

         //print hashtable

         printf("-HASHTABLE-\n\n");  

         print_table(table, N);

         printf("\n--------\n");

         break;

              }

    }

    return 0;

}

// FUNCTIONS

void fill_array(int *A, int table_range, int number){

    int i;

    int num;

    for(i=0; i<number; i++){

 num = rand()%1000; // random number from 0 to 999

 insert_table(A, table_range, num % table_range, num);

    }

}

void insert_table(int *table, int table_range, int hash_index, int val){

    if(table[hash_index] == -1 && hash_index < table_range){

     table[hash_index] = val;

     return;

    }

    // go to the next index using modulo when it is outside of the array

    hash_index = (hash_index+1) % table_range;

    if(hash_index == val % table_range){

 printf("Hashtable is full!\n");

 return;

    }

    insert_table(table, table_range, hash_index, val);   

}

void print_table(int *table, int table_range){

    int i;

    for(i=0;i<table_range;i++){

 printf("%d ",table[i]);

    }

}

int search_table(int *table, int table_range, int val){

    int i;

    i = val % table_range;

    // we search the whole array starting from the hashindex

    // cause some value in between could have been deleted

    // and we then would have false results

    do{

 if(table[i] == val){

     return i;

 }

 i = (i+1) % table_range;

    }while(i != val % table_range);  

    return -1;

}

void delete(int *table, int table_range, int val){

    int index;

    // we call the search function to get the index

    index = search_table(table, table_range, val);

    if(index == -1){

     printf("Value %d doesn't exist on HashTable!\n", val);

 return;

    }

    table[index] = -1;

    printf("Value %d was found at table[%d] and was deleted!\n", val, index);

}

An example run would look like this:

How to implement the other Methods:

    To implement the others we only have to change this one line!

    hash_index = (hash_index+1) % table_range;

When quadratic probing we will have to put it inside of a for loop and starting going in quadratic steps like that:

hash_index = ((hash_index) + i^2 ) % table_range;

    Because my function is recursive I would have to put the i value as a parameter, starting it out with 0 so that we check the normal hash_index first!

So, the insertion using Quadratic Probing would look like this:

void insert_table(int *table, int table_range, int hash_index, int val, int i){

 if(table[hash_index] == -1 && hash_index < table_range){

     table[hash_index] = val;

     return;

 }

 hash_index = ((hash_index) + i^2 ) % table_range;

 if(hash_index == val % table_range){

     printf("Hashtable is full!\n");

     return;

 }

 insert_table(table, table_range, hash_index, val);  

}

    Double Hashing is easy! We will have to put not i^2 but i*the second hashfunction. That way we end up with Double Hashing.

The Insertion Function for Double hashing looks like this:

void insert_table(int *table, int table_range, int hash_index, int val, int i){

 if(table[hash_index] == -1 && hash_index < table_range){

     table[hash_index] = val;

     return;

 }

     hash_index = (hash_index + i*(val % H)) % table_range;

 if(hash_index == val % table_range){

     printf("Hashtable is full!\n");

     return;

 }

 insert_table(table, table_range, hash_index, val);  

}

Where H should be another value like N, that is smaller than N, but again a prime number!

This is actually it! Hope you enjoyed all that Hashing stuff!

Next time in Programming we will get into Graphs in Java Implementation!

Bye!