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!


C Language


Basics


Beginner Codes

C Beginner Codes

Beginner Arrays

C Beginner Arrays

Pointers, Strings and Files

C Pointers, Strings and Files

Dynamic Memory Allocation

C Dynamic Memory Allocation

Structs and Switch Case

C Structs and Switch Case


Datastructures


Recursive Algorithms

C Recursive Algorithms

Linked Lists

C Linked Lists

Binary Trees

C Binary Trees

Queues using Arrays

C Queues using Arrays

Stacks using Arrays

C Stacks using Arrays

Queues using Linked Lists

C Queues using Linked Lists

Stacks using Linked Lists

C Stacks using Linked Lists

Advanced Lists and Queues

C Advanced Lists and Queues

Advanced Trees

C Advanced Trees

Stack-Queue Exercise using Dynamic Arrays

C Stack-Queue Exercise using Dynamic Arrays

Stack-Queue Exercise using Linked Lists

C Stack-Queue Exercise using Linked Lists

Hashtables with Chaining

C Hashtables with Chaining

Hashtables with Linear Probing

C Hashtables with Linear Probing


Other


Can I Run A Dual Monitor Setup

C Can I Run A Dual Monitor Setup

Function Comparison

C Function Comparison