Beginner Codes
C Beginner Codes
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 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