Question

The task of this project is to implement in Java Hash Table structure using Linear Probing Collision Strategy.   You can assume that no duplicates or allowed and perform lazy deletion (similar to BST).

Specification

• Create a generic class called HashTableLinearProbe <K,V>, where K is the key and V is the value.
• It should contain a private static class, HashEntry<K,V>. Use this class to create array to represent Hashtable:

            HashEntry<K,V> hashtable[];

• Implement all methods listed below and test each method through main method.
  • Public Boolean insert (K key, V value)
    • This function inserts entry, rehashes if the table is full, throw error message if the key is invalid or null and return true upon successful insertion or false if duplicate entry
  • Public V find (K key)
    • This function check if the key exists in the table. If yes, true value of the key, or null if not found
  • Public Boolean delete (K key)
    • Performs lazy deleting by marking the entry as deleted. Return true if deleted , false if it not found in the hashtable
  • Public int getHashValue(K key)
    • Returns the hash value for the given key or return -1 if not found
  • Private void rehash()
    • If the table is full, then doubles the hash table size, rehash everything to the new table, ignore items marked deleted.
  • Public static void main(String args[])
    • Methods calls to demonstrate functionality of methods above. Make sure to check with both Integer and String objects
• You may use the pseudocode provide in the text, but make sure to have exception handling for invalid input parameters and method calls.

Please write this in JAVA and provide screenshot of output. Answer question correctly.

Answer 1

ScreenShot:


Code:

/**
*
* Hash table implementation with linear probing.
*
*
* @param <K>
* @param <V>
*/
public class HashTableLinearProbe<K, V> {

   // initial size of array
   private static final int INITIAL_CAPACITY = 3;

   private int capacity = INITIAL_CAPACITY;
   // counts the entries in hashtable
   private int size = 0;

   // This holds actual key value pair
   public static class HashEntry<K, V> {

       private K key;
       private V value;
       // lazy delete
       private boolean deleted;

       public HashEntry(K key, V value) {
           this.key = key;
           this.value = value;
       }

       public K getKey() {
           return key;
       }

       public V getValue() {
           return value;
       }

   }// HashEntry class ends

   // hold the hashtable entries
   private HashEntry<K, V> hashtable[];

   @SuppressWarnings("unchecked")
   // HashTableLinearProbe constructor
   public HashTableLinearProbe() {

       // initialize the hashtable with initial capacity
       this.hashtable = new HashEntry[INITIAL_CAPACITY];

   }// HashTableLinearProbe constructor ends

   // inserts key value in hashtable
   public Boolean insert(K key, V value) {

       if (key == null) {
           throw new IllegalArgumentException("Null key now allowed");
       }

       // check if resize is needed.
       if (size >= capacity) {
           rehash();
       }

       int i;

       // if key passed is equal to hashtable entry key then return false
       for (i = getHashValue(key); hashtable[i] != null; i = (i + 1) % capacity) {

           if (hashtable[i].equals(key)) {
               return false;
           }

       }

       // initialize entry
       HashEntry<K, V> entry = new HashEntry<>(key, value);

       // inserts entry
       hashtable[i] = entry;

       // increase size
       size++;

       // confirm the increament
       return true;

   } // insert() ends

   // find the value by key in hashtable
   public V find(K key) {

       if (key == null) {

           throw new IllegalArgumentException("Key cannot be null");
       }

       // checks passed key is equal to hashtable entry key
       for (int i = getHashValue(key); hashtable[i] != null; i = (i + 1) % capacity) {

           if (hashtable[i].key.equals(key) && !hashtable[i].deleted) {
               // value found
               return hashtable[i].value;
           }

       }

       // confirms no value was found
       return null;

   }// find() ends

   // delete entry by key
   public Boolean delete(K key) {

       if (key == null) {
           throw new IllegalArgumentException("Invalid key");
       }

       int i = getHashValue(key);

       // if entry is null then value doesn't exists
       if (hashtable[i] == null) {
           return false;
       }

       // compares and get index of passed key in hashtable
       while (!key.equals(hashtable[i].key)) {
           i = (i + 1) % capacity;
       }

       hashtable[i].deleted = true;
       size--;

       return true;

   }// delete() ends

   // gets the array index
   public int getHashValue(K key) {

       if (key == null || key.hashCode() == 0) {
           return -1;
       }

       // mod with capacity is done to get the value within length of hashtable
       return key.hashCode() % capacity;

   }// getHashValue() ends

   @SuppressWarnings("unchecked")
   // resizes the hastable to double when it's full
   private void rehash() {

       // tmperory hashtable array
       HashEntry<K, V> tmp[] = new HashEntry[2 * capacity];

       // shifts all value from hashtable to tmp
       for (int i = 0; i < capacity; i++) {

           if (hashtable[i] != null && !hashtable[i].deleted ) {
               tmp[i] = hashtable[i];
           }

       }

       // points hashtable to new hashtable i.e tmp
       hashtable = tmp;

       // marks the increase in capacity by 2
       capacity = 2 * capacity;

   }

   public static void main(String[] args) {

       HashTableLinearProbe<String, String> htlp = new HashTableLinearProbe<>();

       System.out.println("Initial capacity " + htlp.hashtable.length);

       System.out.println("(S1,V1) added " + htlp.insert("S1", "V1"));
       System.out.println("(S2,V2) added " + htlp.insert("S2", "V2"));
       System.out.println("(S3,V3) added " + htlp.insert("S3", "V3"));
       System.out.println("(S4,V4) added " + htlp.insert("S4", "V4"));

       System.out.println("capacity after rehashing " + htlp.hashtable.length);

       System.out.println("Find S1 ->" + htlp.find("S1"));

       System.out.println("Delete S1 ->" + htlp.delete("S1"));
       System.out.println("Find S1 ->" + htlp.find("S1"));

   }

}