Quadratic Probing: C program

Algorithm to insert a value in quadratic probing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be inserted, key

Step 2:  let i = 0

Step 3:  hkey=key%TABLE_SIZE
Step 4: compute the index at which the value has to be inserted in hash table

                index = (hkey+ i * i) % TABLE_SIZE

Step 5: if there is no element at that index then  insert the value at index and STOP

Step 6: If there is already an element at that index

                step 4.1: i = i+1

step 7:  if i < TABLE_SIZE then go to step 4

Algorithm to search a value in quadratic probing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be searched, key

Step 2:  let i = 0

Step 3:  hkey=key%TABLE_SIZE
Step 4: compute the index at which the value can be found

                index = (hkey + i * i) % TABLE_SIZE

Step 5: if the  element at that index is same as the search value then print element found and  STOP

Step 6: else

                step 4.1: i = i+1

step 7:  if i < TABLE_SIZE then go to step 4

 


#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

 int key,index,i,flag=0,hkey;
 printf("\nenter a value to insert into hash table\n");
 scanf("%d",&key);
 hkey=key%TABLE_SIZE;
 for(i=0;i<TABLE_SIZE;i++)
{

     index=(hkey+i*i)%TABLE_SIZE;

     if(h[index] == NULL)
     {
        h[index]=key;
         break;
     }
}
if(i == TABLE_SIZE)
     printf("\nelement cannot be inserted\n");
}
void search()
{

 int key,index,i,flag=0,hkey;
 printf("\nenter search element\n");
 scanf("%d",&key);
 hkey=key%TABLE_SIZE;
 for(i=0;i<TABLE_SIZE; i++)
 {
    index=(hkey+i*i)%TABLE_SIZE;
    if(h[index]==key)
    {
      printf("value is found at index %d",index);
      break;
    }
  }
  if(i == TABLE_SIZE)
    printf("\n value is not found\n");
}
void display()
{
  int i;

  printf("\nelements in the hash table are \n");

  for(i=0;i< TABLE_SIZE; i++)

              printf("\nat index %d \t value =  %d",i,h[i]);

}
main()
{
    int opt,i;
    while(1)
    {
        printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:
                insert();
                break;
            case 2:
                display();
                break;
            case 3:
                search();
                break;
            case 4:exit(0);
        }
    }
}

Output:

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
12

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
22

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
32

Press 1. Insert     2. Display     3. Search     4.Exit
2

elements in the hash table are

at index 0      value =  0
at index 1      value =  0
at index 2      value =  12
at index 3      value =  22
at index 4      value =  0
at index 5      value =  0
at index 6      value =  32
at index 7      value =  0
at index 8      value =  0
at index 9      value =  0
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
22
value is found at index 3
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
123

 value is not found

Press 1. Insert     2. Display     3. Search     4.Exit
4

Double Hashing: C program

Algorithm to insert a value in Double hashing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be inserted,key

Step 2:  let i = 0

Step 3: Let R be the nearest prime < TABLE_SIZE

Step 4:  hkey=key%TABLE_SIZE
Step 5: compute the index at which the value has to be inserted in hash table

                index = (hkey + i * (R- (value % R))% TABLE_SIZE

Step 6: if there is no element at that index then  insert the value at index and STOP

Step 7: If there is already an element at that index

                step 6.1: i = i+1

step 8:  if i < TABLE_SIZE then go to step 5

Algorithm to search a value in Double Hashing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be searched, key

Step 2:  let i = 0

Step 3: Let R be the nearest prime < TABLE_SIZE

Step 4:  hkey=key%TABLE_SIZE
Step 5: compute the index at which the value can be found

                index = (hkey + i * (R- (value % R))% TABLE_SIZE

Step 6: if the  element at that index is same as the search value then print element found and  STOP

Step 7: If there is already an element at that index

                step 6.1: i = i+1

step 8:  if i < TABLE_SIZE then go to step 5

 


#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

 int key,index,i,flag=0,hkey,hash2;
 printf("\nenter a value to insert into hash table\n");
 scanf("%d",&key);
 hkey=key%TABLE_SIZE;
 hash2 = 7-(key %7);
 for(i=0;i<TABLE_SIZE;i++)
 {
    index=(hkey+i*hash2)%TABLE_SIZE;
    if(h[index] == NULL)
    {
        h[index]=key;
        break;
    }
 }
 if(i == TABLE_SIZE)
     printf("\nelement cannot be inserted\n");
}
void search()
{

 int key,index,i,flag=0,hash2,hkey;
 printf("\nenter search element\n");
 scanf("%d",&key);
  hkey=key%TABLE_SIZE;
 hash2 = 7-(key %7);
 for(i=0;i<TABLE_SIZE; i++)
 {
    index=(hkey+i*hash2)%TABLE_SIZE;
    if(h[index]==key)
    {
      printf("value is found at index %d",index);
      break;
    }
  }
  if(i == TABLE_SIZE)
    printf("\n value is not found\n");
}
void display()
{

  int i;
  printf("\nelements in the hash table are \n");
  for(i=0;i< TABLE_SIZE; i++)
    printf("\nat index %d \t value =  %d",i,h[i]);

}
main()
{
    int opt,i;
    while(1)
    {
        printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:
                insert();
                break;
            case 2:
                display();
                break;
            case 3:
                search();
                break;
            case 4:exit(0);
        }
    }
}



Output
Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
12

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
22

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
32

Press 1. Insert     2. Display     3. Search     4.Exit
2

elements in the hash table are

at index 0      value =  0
at index 1      value =  0
at index 2      value =  12
at index 3      value =  0
at index 4      value =  0
at index 5      value =  32
at index 6      value =  0
at index 7      value =  0
at index 8      value =  22
at index 9      value =  0
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
22
value is found at index 8
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
34

 value is not found

Press 1. Insert     2. Display     3. Search     4.Exit
4

Hashing using linear probing : C program

Algorithm to insert a value in linear probing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be inserted, key

Step 2:  let i = 0

Step 3: hkey = key% TABLE_SIZE
Step 4 :compute the index at which the key has to be inserted in hash table

                index = (hkey + i) % TABLE_SIZE

Step 5: if there is no element at that index then  insert the value at index and STOP

Step 6: If there is already an element at that index

                step 4.1: i = i+1

step 7:  if i < TABLE_SIZE then go to step 4

Algorithm to search a value in linear probing

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be searched, key

Step 2:  let i = 0

Step 3: hkey = key% TABLE_SIZE
Step 4: compute the index at which the key can be found
               index = (hkey+ i) % TABLE_SIZE

Step 5: if the  element at that index is same as the search value then print element found and  STOP

Step 6: else

                step 4.1: i = i+1

step 7:  if i < TABLE_SIZE then go to step 4

 

Program:

#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10

int h[TABLE_SIZE]={NULL};

void insert()
{

 int key,index,i,flag=0,hkey;
 printf("\nenter a value to insert into hash table\n");
 scanf("%d",&key);
 hkey=key%TABLE_SIZE;
 for(i=0;i<TABLE_SIZE;i++)
    {

     index=(hkey+i)%TABLE_SIZE;

     if(h[index] == NULL)
     {
        h[index]=key;
         break;
     }

    }

    if(i == TABLE_SIZE)

     printf("\nelement cannot be inserted\n");
}
void search()
{

 int key,index,i,flag=0,hkey;
 printf("\nenter search element\n");
 scanf("%d",&key);
 hkey=key%TABLE_SIZE;
 for(i=0;i<TABLE_SIZE; i++)
 {
    index=(hkey+i)%TABLE_SIZE;
    if(h[index]==key)
    {
      printf("value is found at index %d",index);
      break;
    }
  }
  if(i == TABLE_SIZE)
    printf("\n value is not found\n");
}
void display()
{

  int i;

  printf("\nelements in the hash table are \n");

  for(i=0;i< TABLE_SIZE; i++)

  printf("\nat index %d \t value =  %d",i,h[i]);

}
main()
{
    int opt,i;
    while(1)
    {
        printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:
                insert();
                break;
            case 2:
                display();
                break;
            case 3:
                search();
                break;
            case 4:exit(0);
        }
    }
}

Output

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
12

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
13

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
22

Press 1. Insert     2. Display     3. Search     4.Exit
2

elements in the hash table are

at index 0      value =  0
at index 1      value =  0
at index 2      value =  12
at index 3      value =  13
at index 4      value =  22
at index 5      value =  0
at index 6      value =  0
at index 7      value =  0
at index 8      value =  0
at index 9      value =  0
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter search element
12
value is found at index 2
Press 1. Insert     2. Display     3. Search     4.Exit
2 3

enter search element
23

 value is not found

Press 1. Insert     2. Display     3. Search     4.Exit
4

Hashing with Separate Chaining : C program

Algorithm to insert a value in hash table using separate chaining collision resolution technique

Hashtable is an array of pointers. All pointers are initialized to NULL  ( head[ TABLE_SIZE] = NULL)

Step1: Read the value to be inserted

step 2: create a new node using malloc function

step 3: Assign the value read to the data field of newnode (newnode -> data =value)

step 4: compute the index

                                        index = value % TABLE_SIZE

step 5: if head[ index] is NULL then

                                        step 5.1: attach the newnode as first node

step 6: else

                                        step 6.1 : attach the newnode as lastnode

Program

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 10
struct node
{
               int data;
               struct node *next;
};
struct node *head[TABLE_SIZE]={NULL},*c;
void insert()
{
    int i,key;
    printf("\nenter a value to insert into hash table\n");
    scanf("%d",&key);
    i=key%TABLE_SIZE;
    struct node * newnode=(struct node *)malloc(sizeof(struct node));
    newnode->data=key;
    newnode->next = NULL;
    if(head[i] == NULL)
        head[i] = newnode;
    else
    {
        c=head[i];
        while(c->next != NULL)
        {
           c=c->next;
        }
        c->next=newnode;
    }
}
void search()
{
    int key,index;
    printf("\nenter the element to be searched\n");
    scanf("%d",&key);
    index=key%TABLE_SIZE;
    if(head[index] == NULL)
        printf("\n Search element not found\n");
    else
    {
        for(c=head[index];c!=NULL;c=c->next)
        {
            if(c->data == key)
                {
                    printf("search element found\n");
                    break;
                }
        }
        if(c==NULL)
            printf("\n Search element not found\n");
   
    }
}
void display()
{
    int i;
    for(i=0;i<TABLE_SIZE;i++)
          {
           printf("\nentries at index %d\n",i);
               if(head[i] == NULL)
               {
               printf("No Hash Entry");
               
               }
               else
               {
                              for(c=head[i];c!=NULL;c=c->next)
                              printf("%d->",c->data);
               }
          }
         
}
main()
{
    int opt,key,i;
    while(1)
    {
        printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
        scanf("%d",&opt);
        switch(opt)
        {
            case 1:
                insert();
                break;
            case 2:
                display();
                break;
            case 3:
                search();
                break;
            case 4:exit(0);
                                           
        }
    }
}

Output:

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
12

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
13

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
2

Press 1. Insert     2. Display     3. Search     4.Exit
2

entries at index 0
12->
entries at index 1
13->
entries at index 2
2->
Press 1. Insert     2. Display     3. Search     4.Exit
3

enter the element to be searched
23

 Search element not found

Press 1. Insert     2. Display     3. Search     4.Exit
1

enter a value to insert into hash table
23

Press 1. Insert     2. Display     3. Search     4.Exit
3

enter the element to be searched
23
search element found

Press 1. Insert     2. Display     3. Search     4.Exit
4

Algorithm to search a value in separate chaining

Hashtable is an array of pointers. All pointers are initialized to NULL  ( head[ TABLE_SIZE] = NULL)

Step1: Read the value to be searched

step 2: compute the index

                                        index = value % TABLE_SIZE

step 5: if head[ index] is NULL then print “search element not found” and STOP

step 6: else

                                        step 6.1: store the first node address in pointer c (c = head [ index ])

                                        step 6.2 : if value is equal to data in c then print “search element found” and STOP

                                        step 6.3: else move c to next node ( c = c->next)  and if c != NULL go to step 6.2

step 7: if search element is not found in entire linked list (c is NULL) then print “ search element not found”