Hashing Using Linear Probing : Java 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, x

Step 2:  let i = 0

Step 3 :compute the index at which the x has to be inserted in hash table

                index = (x+ i) % TABLE_SIZE

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

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

                step 4.1: i = i+1

step 6:  if i < TABLE_SIZE then go to step 3

Algorithm to search a value in linear probing

 

Hashtable is an array of size = TABLE_SIZE

Step 1: Read the value to be searched, x

Step 2:  let i = 0

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

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

Step 5: else

                step 5.1: i = i+1

step 6:  if i < TABLE_SIZE then go to step 3

 

Linear Probing program

import java.util.Scanner;

 

public class LinearProbing

{

      int htable[],tableSize;

      public void insert(int x)

      {

            int i;

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

            {

                  int index=(x+i)%tableSize;

                  if(htable[index] == -1)

                  {

                        htable[index]=x;

                        break;

                  }

            }

            if(i == tableSize)

                  System.out.println("cannot insert as table is full");

      }

      public void display()

      {

            System.out.println("hash table entries are");

            for(int i=0;i<tableSize;i++)

            {

               System.out.println("element at index "+i+" is " +htable[i]);

            }

      }

      public void search(int x)

      {

            int i;

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

            {

                  int index=(x+i)%tableSize;

                  if(htable[index] == x)

                  {

                        System.out.println("Search found at index "+index);

                        break;

                  }

            }

            if(i == tableSize)

                  System.out.println("Search element not found");

      }

      public static void main(String[] args)

      {

            LinearProbing ob =new LinearProbing();

            Scanner sc = new Scanner(System.in);

            System.out.println("enter size of the table");

            ob.tableSize=sc.nextInt();

            ob.htable=new int[ob.tableSize];

            for(int i=0;i<ob.tableSize;i++)

                        ob.htable[i]=-1;

            while(true)

            {

              System.out.println("1. insert 2. display 3. search 4. exit");

                  int choice=sc.nextInt();

                  switch(choice)

                  {

                  case 1:

                        System.out.println("enter key to be inserted");

                        x=sc.nextInt();

                        ob.insert(x);

                        break;

                  case 2:

                        ob.display();

                        break;

                  case 3:

                        System.out.println("enter key to be searched");

                        x=sc.nextInt();

                        ob.search(x);

                        break;

                  case 4: return;

                  default:

                       System.out.println("invalid");

                  }

            }

 

      }

 

}

Output:
enter size of the table
10
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
12
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
13
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
14
press 1. insert 2. display 3. search 4. exit
1
enter key to be inserted
22
press 1. insert 2. display 3. search 4. exit
2
hash table entries are
element at index 0 is -1
element at index 1 is -1
element at index 2 is 12
element at index 3 is 13
element at index 4 is 14
element at index 5 is 22
element at index 6 is -1
element at index 7 is -1
element at index 8 is -1
element at index 9 is -1
press 1. insert 2. display 3. search 4. exit
3
enter key to be searched
22
Search element found at index 5
press 1. insert 2. display 3. search 4. exit

4