Programming - C Hashtables with Linear Probing

    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!

H2
H3
H4
3 columns
2 columns
1 column
1 Comment