HASHTABLE(SIMPLE CHAINNING)

Hello Friends,

Below I have implemented a Hash Table with simple chaining collision avoidance technique. I have also included Rehash facility if the average number of entries exceeds the size Load factor (a constant, in my case I have considered loadfactor = 10). The implementation is very simple and you can add your suitable hash function as per your application need, just modify the HashFucntion().

//HASHTABLE(SIMPLE CHAINNING) IMPLEMENTATION

#include<stdio.h>
#include<stdlib.h>
#define loadfactor 10
#define SIZE 30

struct listnode{
    int data;
    int key;
    int count;
    struct listnode *next;
};

struct hashnode
{
    int bcount;
    struct listnode *next;
};

struct hashtable
{
    int tsize;
    int count;
    struct hashnode **arr;
};

struct hashtable* createhashtable(int size)
{
    int i;
    struct hashtable *h;
    h = (struct hashtable*)malloc(sizeof(struct hashtable));
    h->tsize = (size/loadfactor)+1;
    h->count = 0;
    h->arr = (struct hashnode**)malloc(sizeof(struct hashnode*)*h->tsize);
    for(i=0;i<h->tsize;i++)
    {
        h->arr[i]= (struct hashnode*)malloc(sizeof(struct hashnode));
        h->arr[i]->next = NULL;
        h->arr[i]->bcount = 0;
    }
    return h;
}

int HashFunction(int tsize,int key)
{
    return(key%tsize);
}

int checkhash(struct hashtable *h, int data)
{
    int index = HashFunction(h->tsize,data);
    struct listnode *tmp;
    tmp = h->arr[index]->next;
    while(tmp)
    {
        if(tmp->data == data)
        {
            tmp->count++;
            return 1;
        }
        tmp = tmp->next;
    }
    return 0;
}

void rehash(struct hashtable *h)
{
    struct listnode *tmp1,*tmp2;
    struct hashnode **old;
    int index,oldsize,i;
    old = h->arr;
    oldsize = h->tsize;
    h->tsize = oldsize*2;
    h->arr = (struct hashnode**)malloc(sizeof(struct hashnode*)*h->tsize);
    for(i=0;i<h->tsize;i++)
    {
        h->arr[i] = (struct hashnode*)malloc(sizeof(struct hashnode));
        h->arr[i]->next = NULL;
    }
    for(i=0;i<oldsize;i++)
    {
        tmp1 = old[i]->next;
        if(tmp1)
        {
            index = HashFunction(h->tsize,tmp1->data);
            h->arr[index]->next= tmp1;
        }
    }
    free(old);
}

int inserthashtable(struct hashtable *h, int data)
{
    struct listnode *newnode;
    int index;
    index = HashFunction(h->tsize,data);
    if(checkhash(h,data))
        return 0;
    newnode = (struct listnode*)malloc(sizeof(struct listnode));
    newnode->data = data;
    newnode->key = index;
    newnode->count = 1;
    newnode->next = h->arr[index]->next;
    h->arr[index]->next = newnode;
    h->count++;
    h->arr[index]->bcount++;
    if((h->count/h->tsize)>=loadfactor)
    {
        printf("total element in hashtable: %d\ntable size: %d\n",h->count,h->tsize);
        rehash(h);
    }
    return 1;
}

int main()
{
    struct hashtable *hash;
    struct listnode *tmp;
    int i,x;
    int arr[SIZE]={10,20,30,40,51,23,44,41,15,25,26,31,46,5,2,4,14,13,27,101,220,32,17,54,29,47,49,19,24,1};
  
    hash = createhashtable(SIZE);
    for(i=0;i<SIZE;i++)
    {
        x = inserthashtable(hash,arr[i]);
        if(x == 0)
        printf("%d already exists in Hashtable\n",arr[i]);
    }
    printf("Hash table:\n");
    printf("total element:%d\ntable size: %d\n",hash->count,hash->tsize);
    for(i=0;i<hash->tsize;i++)
    {
        tmp = hash->arr[i]->next;
        while(tmp)
        {
            printf("%d ",tmp->data);
            tmp = tmp->next;
        }
        printf("\n");
    }
}