Linear probing hash tables

Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location.

Write a program to implement linear probing hash tables

Algorithm Explanation

	Create the hash table and insert the key, values pair into the hash table.
	The new location calculated using newLocation = (startingValue + stepSize) % arraySize formula.
	The linear probing used in open addressed hash table which improve the memory caching. the performance of linear probing is more sensitive to input distribution when compare to double hashing.
	The insert and remove operations uses hash function and resize the table.

Source Code

package com.dsacode.DataStructre.hashtable;
 
public class LinearProbingHashTable {
     private int currentSize, maxSize;      
        private String[] keys;  
        private String[] vals;   
      
        public LinearProbingHashTable(int capacity) {
            currentSize = 0;
            maxSize = capacity;
            keys = new String[maxSize];
            vals = new String[maxSize];
        } 
      
        public void makeEmpty(){
            currentSize = 0;
            keys = new String[maxSize];
            vals = new String[maxSize];
        }
      
        public int getSize() {
            return currentSize;
        }
      
        public boolean isFull() {
            return currentSize == maxSize;
        }
      
        public boolean isEmpty() {
            return getSize() == 0;
        }
      
        public boolean contains(String key) {
            return get(key) !=  null;
        }
      
        private int hash(String key) {
            return key.hashCode() % maxSize;
        }   
      
        public void insert(String key, String val) {               
            int tmp = hash(key);
            int i = tmp;
            do {
                if (keys[i] == null) {
                    keys[i] = key;
                    vals[i] = val;
                    currentSize++;
                    return;
                }
                if (keys[i].equals(key)) {
                    vals[i] = val;
                    return;
                }           
                i = (i + 1) % maxSize;           
            } while (i != tmp);      
        }
      
        public String get(String key) {
            int i = hash(key);
            while (keys[i] != null)
            {
                if (keys[i].equals(key))
                    return vals[i];
                i = (i + 1) % maxSize;
            }           
            return null;
        }
      
        public void remove(String key) {
            if (!contains(key))
                return;
      
            int i = hash(key);
            while (!key.equals(keys[i]))
                i = (i + 1) % maxSize;       
            keys[i] = vals[i] = null;
      
        
            for (i = (i + 1) % maxSize; keys[i] != null; i = (i + 1) % maxSize)  {
                String tmp1 = keys[i], tmp2 = vals[i];
                keys[i] = vals[i] = null;
                currentSize--; 
                insert(tmp1, tmp2);           
            }
            currentSize--;       
        }      
      
 
        public void printHashTable()  {
            for (int i = 0; i < maxSize; i++)
                if (keys[i] != null)
                    System.out.println(keys[i] +" "+ vals[i]);
            System.out.println();
        }  
     
      
      public static void main(String[] args)   {
            LinearProbingHashTable lpht = new LinearProbingHashTable(5 );
            System.out.println("Insert values into Hashtable.\n");
            lpht.insert("a", "1111");
            lpht.insert("b", "2222");
            lpht.insert("c", "3333");
             
            System.out.println("Print values from Hashtable");
            lpht.printHashTable();
             
            System.out.println("Print values from Hashtable after remove the 'b'");
            lpht.remove("b");
            lpht.printHashTable();
             
            System.out.println("Get the value of 'c': "+ lpht.get( "c" ));
             
             
            System.out.println("\nClear the Hashtable.\n");
            lpht.makeEmpty();
             
             
            System.out.println("Size of the Hash table after clear: "+ lpht.getSize() );
             
        }
}

Output

Insert values into Hash table.
 
Print values from Hash table
a 1111
b 2222
c 3333
 
Print values from Hash table after remove the 'b'
a 1111
c 3333
 
Get the value of 'c': 3333
 
Clear the Hash table.
 
Size of the Hash table after clear: 0